Minimizing makespan in re-entrant permutation flow-shops
- PDF / 194,048 Bytes
- 12 Pages / 595 x 794 pts Page_size
- 33 Downloads / 200 Views
r 2003 Operational Research Society Ltd. All rights reserved. 0160-5682/03 $25.00 www.palgrave-journals.com/jors
Minimizing makespan in re-entrant permutation flow-shops JC-H Pan1* and J-S Chen2 1
National Taiwan University of Science and Technology, Taipei, Taiwan; and 2Far East College, Tainan, Taiwan
A re-entrant flow-shop (RFS) describes situations in which every job must be processed on machines in the order of M1, M2, y, Mm, M1, M2, y,Mm, y, and M1, M2, y,Mm. In this case, every job can be decomposed into L levels and each level starts on M1, and finishes on Mm. In a RFS case, if the job ordering is the same on any machine at each level, then it is said that no passing is allowed since any job is not allowed to pass any previous job. The RFS scheduling problem where no passing is allowed is called the re-entrant permutation flow-shop (RPFS) problem. This paper proposes three extended mixed BIP formulations and six extended effective heuristics for solving RPFS scheduling problems to minimize makespan. Journal of the Operational Research Society (2003) 54, 642–653. doi:10.1057/palgrave.jors.2601556 Keywords: scheduling; re-entrant permutation flow-shops; integer programming
Introduction In contrast to the classical scheduling assumption that each job visits each machine at most once, the re-entrant shop is common in practice. In a re-entrant shop, a job may be processed by a certain machine many times. Such a shop can be found in high-tech industries and certain manufacturing production systems. In signal processing, a signal is preprocessed by a computer before going through sensing and command system for transmission and retrieval, and then back to the computer for postprocessing.1 The machines used in semiconductor manufacturing are extremely expensive and comprise 75% of the total cost of a wafer fabrication plant. Consequently, each wafer revisits the same machine for multiple processing steps.2 The wafers traverse flow lines several times to produce the different levels that comprise each circuit.3,4 Printed circuit boards (PCBs) are assembled on a wide variety of automated machines and manual workstations. The arrival process of PCB is just-in-time (JIT), and each card is placed in a workholder that travels through the system. Electronic components (chips, transistors, resistors) are inserted automatically at the automated component insertion machine cells (namely, surface-mounted devices) and then inserted manually at the manual insertion workcells (namely, pinthrough-hole devices).5 To reduce the dimensions of PCB, components are often placed on both its top and bottom. Therefore, PCBs are manufactured following the sequence of first attaching surface-mounted devices and then inserting *Correspondence: JC-H Pan, Department of Industrial Management, National Taiwan University of Science and Technology, Taipei, Taiwan. E-mail: [email protected]
pin-through-hole devices on different machines for the uppersides, and then the lowersides.6 In the classical flow-shop scheduling problem, if the job ordering is
Data Loading...
