Minimizing total completion time in a no-wait flowshop with sequence-dependent additive changeover times
- PDF / 206,399 Bytes
- 14 Pages / 595 x 842 pts (A4) Page_size
- 5 Downloads / 192 Views
#2001 Operational Research Society Ltd. All rights reserved. 0160-5682/01 $15.00 www.palgrave.com/jors
Minimizing total completion time in a no-wait ¯owshop with sequence-dependent additive changeover times A Allahverdi* and T Aldowaisan Kuwait University, Safat, Kuwait This paper addresses the problem of minimizing total completion time in a two-machine no-wait ¯owshop where setup times of the jobs are sequence-dependent. Optimal solutions are obtained for two special ¯owshops and a dominance relation is developed for the general problem. Several heuristic algorithms with the computational complexity of O(n2) and O(n3) are constructed. The heuristics consist of two phases: in the ®rst phase a starting list is developed and in the second a repeated insertion technique is applied. Computational experience demonstrates that the concept of repeated insertion application is quite useful for any starting list and that solutions for all starting lists converge to about the same value of less than 1% after a few iterations. Keywords: two-machine ¯owshop; setup time; no-wait; completion time; heuristics
Introduction In many ¯owshop environments, a job needs to go through a sequence of machines without any delay between successive operations of the job. This means the difference between the completion time of a job's last operation and the starting time of its ®rst operation is equal to the sum of its operation times on all machines. There are several industries where the no-wait ¯owshop problem applies. Examples include the metal (eg manufacturing of aluminum beverage cans and manufacturing of cables and wires), plastic, and chemical industries. For instance, in the case of steel production, the heated metal must continuously go through a sequence of operations before it is cooled in order to prevent defects in the composition of the material. The no-wait problem has been extensively studied in the scheduling literature and a survey is given by Hall and Sriskandarajah.1 Some of the work on the no-wait problem with the objective of minimizing total ¯owtime includes Adiri and Pohoryles,2 Rajendran and Chaudhuri,3 and van der Veen and van Dal.4 Adiri and Pohoryles2 and van der Veen and van Dal4 provided polynomial time algorithms to special no-wait ¯owshops while Rajendran and Chaudhuri3 established two heuristic algorithms for the generic no-wait ¯owshops. Another area of research in ¯owshop scheduling involves separating setup time from processing time. For a separable
*Correspondence: A Allahverdi, Department of Mechanical and Industrial Engineering, College of Engineering and Petroleum, Kuwait University, PO Box 5969, Safat Kuwait. E-mail: [email protected]
setup, two problem types exist. In the ®rst, setup depends only on the job to be processed, and hence is called sequence-independent. In the second, setup depends on both the job to be processed and the immediately preceding job, which is hence called sequence-dependent. A recent survey on scheduling problems involving setup times is given by Allahverdi
Data Loading...
