Search

Abstract: This paper explores the simultaneous batch splitting and scheduling problem for identical parallel production lines, which is different from the parallel machine scheduling in that the processing time of a batch on parallel production lines is not fully proportional to that of a product. To solve the problem, a formula is derived to determine the processing time of a batch on a production line which is not taken as a single machine for each item in the batch. A lower bound is provided for the starting time of a batch production, which overlaps the previous one. A sufficient condition for guaranteeing the constant availability of the end buffer is given and proven mathematically with respect to a continuously delivered batch. Based on the above, an algorithm whose complexity is unrelated to the batch size is proposed to obtain the starting time of a batch production. Finally, a heuristic method based on genetic algorithm is constructed to solve the splitting and scheduling problems simultaneously. Numerical experiments show that this method functions well to balance the loads of the production lines. In fact, the proposed approach is significantly more effective than the existing methods for production planning and scheduling on production lines (each of which is considered as a single machine for both batch and item). [Copyright &y& Elsevier]

Abstract: In this paper, we investigate a time-dependent learning effect in a flowshop scheduling problem. We assume that the time-dependent learning effect of a job was a function of the total normal processing time of jobs scheduled before the job. The following objective functions are explored: the makespan, the total flowtime, the sum of weighted completion times, the sum of the kth power of completion times, and the maximum lateness. Some heuristic algorithms with worst-case analysis for the objective functions are given. Moreover, a polynomial algorithm is proposed for the special case with identical processing time on each machine and that with an increasing series of dominating machines, respectively. Finally, the computational results to evaluate the performance of the heuristics are provided. [Copyright &y& Elsevier]

Abstract: Model checkers for systems represented by labelled transition systems are not as extensively used as those for systems represented by Kripke structures. This is partially due to the lack of an elegant formal language for property specification which would not be as raw as, for example, HML yet also not as complex as, for example, -calculus. This paper proposes a new action-based propositional branching-time temporal logic ACTLW, which enhances popular computation tree logic (CTL) with the notion of actions in a similar but more comprehensive way than action-based CTL introduced by De Nicola and Vaandrager [R. De Nicola, F.W. Vaandrager, Action versus logics for transition systems, in: Semantics of Systems of Concurrent Processes, Proceedings LITP Spring School on Theoretical Computer Science, LNCS 469, 1990, pp. 407–419]. ACTLW is defined by using temporal operators until and unless only, whereas all other temporal operators are derived from them. Fixed-point characterisation of the operators together with symbolic algorithms for global model checking are shown. Usage of this new logic is illustrated by an example of verification of mutual-exclusion algorithms. [Copyright &y& Elsevier]