A two-level genetic algorithm for scheduling in assembly islands with fixed-position layouts

Abstract

This paper focuses on the scheduling problem in assembly islands environment with fixed-position layouts. In such configuration, the product normally remains in one location for its entire manufacturing period while machines, materials and workers are moved to an assembly site called an assembly island. This production layout has some unique features such as moving assembly workers, tools and materials; limited space at assembly site; considerable distance between islands. The authors first give the definition and mathematical model for the scheduling problem and then propose a two-level genetic algorithm to obtain a near optimal solution to minimize the makespan. Experimental results show that this algorithm is effective. The performance analysis of the proposed algorithm indicates that it is more efficient in the airline or shipbuilding industry than in the machine or tool final assembly companies.

Keywords

Assembly islands / scheduling / genetic algorithm

References

[1] Bonny M.C., Gundry S.W.. Solution to the constrained flowshop sequencing problem. Operational Research Quarterly, 1976, 24: 869-883.

[2] Cheng T.C.. A review of flowshop scheduling research with setup times. Operations Management, 2000, 9(3): 262-282.

[3] Cheng R.. A tutorial survey of job-shop scheduling problems using genetic algorithms-II: hybrid genetic search strategies. Computers & Industrial Engineering, 1999, 36: 343-364.

[4] Cheng R.. A tutorial survey of job-shop scheduling problems using genetic algorithms-I: representation. Computers & Industrial Engineering, 1996, 30(4): 983-997.

[5] Gilmore P.C., Gomory R.E.. Sequencing a one state-variable machine: a solvable case of the traveling salesman problem. Operational Research, 1964, 12: 655-679.

[6] Goldberg D.E.. Genetic Algorithms in Search, Optimization and Machine Learning, 1989, Reading, Mass: Addison-Wesley.

[7] Hall N.G., Sriskandarajah C.. A survey of machine scheduling problems with blocking and no-wait in process. Operations Research, 1996, 44(3): 510-525.

[8] Ho N.B.. An effective architecture for learning and evolving flexible job-shop schedules. European Journal of Operational Research, 2007, 179: 316-333.

[9] Holland J.H.. Adaptation in Natural and Artificial Systems, 1975, Ann Arbor: The University of Michigan Press

[10] Huang G.Q.. RFID-based wireless manufacturing for walking-worker assembly islands with fixed-position layouts. Robotics and Computer-Integrated Manufacturing, 2007, 23: 469-477.

[11] Lee Y.H., Pinedo M.. Scheduling jobs on parallel machines with sequence-dependent setup times. European Journal of Operational Research, 1997, 100: 464-474.

[12] Luh P.B.. Job shop scheduling with group-dependent setups, finite buffers, and long time horizon. Annals of Operations Research, 1998, 76: 233-259.

[13] Michalewicz Z.. Genetic Algorithms + Data Structures = Evolution Programs, 1997, Berlin: Springer

[14] Rajendran C., Chaudhuri D.. Heuristic algorithm for continuous flow-shop problem. Naval Research Logistics, 1990, 37: 695-705.

[15] Rechberg, I. (1973). Opimierung Technicher Systeme Nach Prinzipien der Biologischen Evolution. Problemate, Frommann-Holzboog

[16] Schwefel H.P.. Numerische Optimierung von Computer-Modellen Mittels del Evolutionsstrategie, 1977, Basel: Birkhauser

[17] Trostmann, E. (1993). Cybernetic modeling and control in integrated production systems — a project review. In: Proceedings of the Eighth IPS Research Seminar, 213–225, Denmark, March 22–24, 1993

[18] Wagneur E., Sriskandarajah C.. The two-machine permutation flow shop with state dependent processing times. Naval Research Logistics, 1993, 40: 697-717.

[19] Wang Q.. Comparison between fixed- and walking-worker assembly lines. Proc IMechE Part B: J. Engineering Manufacturing, 2005, 219: 845-848.