This paper presents a genetic algorithm for generalized job-shop problem solving. The generalization includes feeding times, sequences of set-up dependent operations and jobs with different routings among workcentres including ‘multi-identical’ machines. A formulation as an optimization problem with an original chromosome coding and tailored genetic operators are proposed. The algorithm has been tested with benchmarks given in the literature, and bounds for the minimum completion time are reported in order to evaluate the performance in both generalized job-shop and flexible manufacturing system (FMS) scheduling.
IwataK.MurotsuY.ObaF.Solution to large-scale scheduling problems for job shop type machining system with alternative machine tools. Ann. CIRP, 1980, 29, 65–79.
2.
NasrN.ElsayedE. A.Job shop scheduling with alternative machines. Int. J. Prod. Res., 1990, 28, 1595–1609.
3.
HutchisonJ.LeongK.SynderD.WardP.Scheduling approach for random job shop flexible manufacturing systems. Int. J. Prod. Res., 1991, 29, 1053–1067.
4.
AhnJ.HeW.KusiakA.Scheduling with alternative operations. IEEE Trans. Robotics and Automn, 1993, 9, 297–303.
FrenchS.Sequencing and Scheduling—An Introduction to the Mathematics of the Job-Shop, 1982 (John Wiley, New York).
7.
GareyM. R.JohnsonD. S.Computer and Intractability: A Guide to the Theory of NP Completeness, 1979 (W. H. Freeman, San Francisco, California).
8.
BrandimarteP.UkovichW.VillaA.Continuous flow models for batch manufacturing: A basis for a hierarchical approach. Int. J. Prod. Res., 1995, 33, 1635–1660.
9.
JainA. S.MeeranS.Job shop scheduling using neural networks. Int. J. Prod. Res., 1998, 36, 1249–1272.
10.
WangL. C.Intelligent scheduling of FMSs with inductive learning capability using neural networks. Int. J. Flexible Mfg Syst., 1995, 7, 147–175.
11.
IshiiN.TalavageJ. J.A transient-based real-time scheduling algorithm in FMS. Int. J. Prod. Res., 1991, 29, 2501–2520.
12.
PerroneG.La CommareU.Lo NigroG.NuccioC.Dynamic scheduling in a multiple objective production environment using a fuzzy adaptive controller. In Proceedings of 11th International Conference on Computer Aided Production Engineering, London, 1995, pp. 143–148.
13.
LogendranR.SonthinenA.A Tabu search-based approach for scheduling job-shop type flexible manufacturing systems. J. Operation Res. Soc., 1997, 48, 264–277.
14.
JainA. S.MeeranS.Deterministic job shop scheduling; past, present and future. Eur. J. Operation Res., 1999, 113, 390–434.
15.
HollandJ. H.Adaptation in Natural and Artificial Systems, 1975 (University of Michigan Press, Ann Arbor, Michigan).
16.
KennethA.De JongK. A.SpearsW. M.Using genetic algorithm to solve NP-complete problem. In Proceedings of 3rd International Conference on Genetic Algorithms (Ed. SchafferJ. D.), 1989, pp. 124–132 (Morgan Kaufmann, San Mateo, California).
17.
SyswerdaG.Schedule optimization using genetic algorithms. In Handbook of Genetic Algorithms (Ed. DavisL.), 1991, pp. 332–349 (Van Nostrand Reinhold, New York).
18.
ParkL.ParkC. H.Application of genetic algorithm to job-shop scheduling problems with active schedule constructive crossover. In Proceedings of IEEE International Conference on Systems, Man and Cybernetics, Vancouver, British Columbia, 1995, Vol. 1, pp. 530–535.
19.
GenM.TsujimuraY.KubotaE.Solving job-shop scheduling problems by genetic algorithm. In Proceedings of IEEE International Conference on Systems, Man and Cybernetics, San Antonio, Texas, 1994, Vol. 2, pp. 1577–1582.
20.
NakanoR.Conventional genetic algorithm for job shop problems. In Proceedings of 4th International Conference on Genetic Algorithms (Eds BelewR. K.BookerL. B.), 1991, pp. 124–132 (Morgan Kaufmann, San Mateo, California).
21.
FangH. L.RossP.CorneD.A promising genetic algorithm approach to job-shop scheduling, rescheduling and open-shop scheduling problems. In Proceedings of 5th Conference on Genetic Algorithms(Ed. ForrestS.), 1993, pp. 375–382 (Morgan Kaufmann, San Mateo, California).
CarlierJ.PinsonE.An algorithm for solving the job-shop problem. Managmt Sci., 1989, 35, 164–176.
24.
ApplegateD.CookW.A computational study of the job-shop scheduling problem. ORSA J. Computing, 1991, 3, 149–156.
25.
RossiA.DiniG.Dynamic scheduling of FMS using a real-time genetic algorithm. Int. J. Prod. Res., 2000, 38, 1–20.
26.
GoldbergD. E.Genetic Algorithms in Search, Optimization and Machine Learning, 1989 (Addison-Wesley, Reading, Massachusetts).
27.
BookerL. B.GoldbergD. E.HollandJ. H.Classifier systems and genetic algorithms. Artif. Intell., 1989, 40, 235–282.
28.
MattfeldD. C.VaessensR. J. M.OR-Library. FTP site o.rlibrary@ic.ac.uk.
29.
LawrenceS.Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques. Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1984.
30.
Van LaarhovenP. J. M.AartsE. H. L.LenstraJ. K.Job shop scheduling with simulated annealing. Operation Res., 1992, 40, 113–125.
31.
MatsuoH.SuhC. J.SullivanR. S.A controlled search simulated annealing method for the general jobshop scheduling problem. Working paper 03-04-88, Graduate School of Business, University of Texas, Austin, Texas, 1988.
