Scheduling hybrid flowshops in printed circuit board assembly lines

Production and Operations Management, Summer 2002 by Jin, Z H, Ohno, K, Ito, T, Elmaghraby, S E

SCHEDULING HYBRID FLOWSHOPS IN PRINTED CIRCUIT BOARD ASSEMBLY LINES*

We treat a three-stage hybrid flowshop for the production of printed circuit boards (PcB), suggested to us by a real-life production situation. The problem is to determine a schedule that minimizes the makespan for a given demand profile over a finite planning horizon. We propose a global procedure that utilizes genetic algorithms and three subproblems. The performance of the procedure is evaluated via experimentation over thousands of problem realizations that are randomly generated. The experimental results show the efficiency of the global procedure and provides qualitative answers to the allocation of machines to the various stages.

(HYBRID FLOWSHOPS; SCHEDULING; PRINTED CIRCUIT BOARD ASSEMBLY; HEURISTICS)

1. Introduction

We consider a scheduling problem in a printed circuit board (Pcs) assembly line for inserting electronic components to produce a variety of PCB types. A typical PCB assembly line consists of several stages, and each stage consists of several insertion machines in parallel. Usually, each type of insertion machine is specialized with regard to certain types of components that it can handle; for example, axial leaded, radial leaded, etc. Such an assembly line is typically required to produce the different types of PCBS in lots of different sizes. Each type of PCB consists of hundreds of electronic devices such as resistors, capacitors, diodes, transistors, transformers, and connectors.

In this paper, the assembly environment that we consider is a multi-stage hybrid flowshop (MHFS), alternatively known as flexible flowshop, multi-processor flowshop, series-parallel shop, among others. The PCBS move unidirectionally through the various stages of assembly, and the insertion machines at each stage insert a subset of the electronic components required. The flow order is determined by assembly technological constraints.

Figure 1 illustrates the layout of the PCB assembly line in the factory that motivated this study and provided the data for its initial trials.

This assembly line scheduling problem is defined more precisely as follows. The line consists of three consecutive assembly stages. In stage s there are m^sub s^ >= 1 parallel identical insertion machines for s = 1, 2, 3. Therefore this problem may be viewed as a three-stage MHFS scheduling problem. There are n types of PCBS to be scheduled without preemption; each type has to be assembled serially through the three stages. The setup between different types of PCBS is conducted off-line, and the setup time can be neglected. Finally, the objective is to find an optimal schedule that minimizes the makespan.

* Received March 1999; revisions received January 2000 and April 2001; accepted April 2001.

References

ARTHANARY, T. S. AND K. G. RAMASWAMY (1971), "An Extension of Two Machine Sequencing Problem," Opsearch, 8, 1, 10-22.

BEN-ARIEH, D. AND 0. MAIMON (1992), "Annealing Method for PCB Assembly Scheduling on Two Sequential Machines," International Journal of Computer Integrated Manufacturing, 5, 6, 361-367.

CARLIER, J. (1987), "Scheduling Jobs with Release Dates and Tails on Identical Machines to Minimize the Makespan," European Journal of Operational Research, 29, 3, 298-306.

CHEN, B., C. A. GLASS, C. N. POTTS, AND V. A. STRUSEVICH (1996), "A New Heuristic for Three-Machine Flowshop Scheduling," Operations Research, 44, 6, 891-898.

DEAL, D. E. AND J. L. HUNSUCKER (1991), "The Two-Stage Flowshop Scheduling Problem with m Machines at Each Stage," Journal of the Information and Optimization Sciences, 12, 3, 407-417.

FEo, T. A., J. F. BARD, AND S. D. HOLLAND (1996), "A GRASP for Scheduling Printed Wiring Board Assembly," IIE Transactions, 28, 2, 155-165.

GOLDBERG, D. E. (1989), Genetic Algorithm in Search, Optimization, and Machine Learning, Addison-Wesley, Menlo Park, CA.

GUINET, A., M. M. SOLOMON, P. K. KEDIA, AND A. DUSSAUCHOY (1996), "A Computational Study of Heuristics for Two-Stage Flexible Flowshop," International Journal of Production Research, 34, 5, 1399-1415.

GUPTA, J. N. D., A. M. A. HARIRI, AND C. N. PoTTs (1997), "Scheduling a Two-Stage Hybrid Flow Shop with Parallel Machines at the First Stage," Annals of Operations Research, 69, 171-191.

AND E. A. TUNC (1991), "Schedules for a Two-Stage Hybrid Flowshop with Parallel Machine at the Second Stage," International Journal of Production Research, 29, 7, 1489-1502.

HAOUARI, H. AND R. M'HALLAH (1997), "Heuristic Algorithms for the Two-Stage Hybrid Flowshop Problem," Operations Research Letters, 21, 1, 43-53.

JACKSON, J. R. (1955), Scheduling a Production Line to Minimize Maximum Tardiness, Research No. 43, Management Science Research Project, University of California, Los Angeles, CA.

JOHNSON, S. M. (1954), "Optimal Two- and Three-Stage Production Schedules with Setup Times Included," Naval Research Logistics Quarterly, 1, 1, 61-68.

LANGSTON, M. A. (1987), "Interstage Transportation Planning in the Deterministic Flow-Shop Environment," Operations Research, 35, 4, 556-564.

LAWLER, E. L., K. L. JAN, H. G. R. K. ALEXANDER, AND B. S. DAVID (1993), "Sequencing and Scheduling: Algorithms and Complexity," in Handbooks in Operations Research and Management Science, Logistics of Production and Inventory, S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin (eds.), North Holland, Amsterdam, New York, 4, 445-522.