Job shop scheduling problem with alternative machines using genetic algorithms

Abstract

The classical job shop scheduling problem (JSP) is the most popular machine scheduling model in practice and is known as NP-hard. The formulation of the JSP is based on the assumption that for each part type or job there is only one process plan that prescribes the sequence of operations and the machine on which each operation has to be performed. However, JSP with alternative machines for various operations is an extension of the classical JSP, which allows an operation to be processed by any machine from a given set of machines. Since this problem requires an additional decision of machine allocation during scheduling, it is much more complex than JSP. We present a domain independent genetic algorithm (GA) approach for the job shop scheduling problem with alternative machines. The GA is implemented in a spreadsheet environment. The performance of the proposed GA is analyzed by comparing with various problem instances taken from the literatures. The result shows that the proposed GA is competitive with the existing approaches. A simplified approach that would be beneficial to both practitioners and researchers is presented for solving scheduling problems with alternative machines.

Keywords

alternative machine / genetic algorithm (GA) / job shop / scheduling / spreadsheet

References

[1] NasrN., ElsayedE. A.. Job shop scheduling with alternative machines [J]. International Journal of Production Research, 1990, 28(9): 1595-1609

[2] NSAR N. Scheduling of production systems with flexible routings [C]// Proceedings of the Second Industrial Engineering Research Conference. Los Angeles, CA, USA, 1992: 487–492.

[3] WilhelmW., ShinH.. Effectiveness of alternative operations in a flexible manufacturing system [J]. International Journal of Production Research, 1985, 23(1): 65-79

[4] HankinsS. L., WyskR. A., FoxK. R.. Using a CATS database for alternative machine loading [J]. Journal of Manufacturing Systems, 1984, 3: 115-120

[5] AhnJ., HeW., KusiakA.. Scheduling with alternative operations [J]. IEEE Transactions on Robotics & Automation, 1993, 9(3): 297-303

[6] KimK. H., EgbeluP. J.. Scheduling in a production environment with multiple process plans per job [J]. International Journal of Production Research, 1999, 37(12): 2725-2753

[7] RajamaniD., SinghN., AnejaY. P.. Integrated design of cellular manufacturing systems in the presence of alternative process plans [J]. International Journal of Production Research, 1990, 28(8): 1541-1554

[8] JiangJ., HsiaoW.. Mathematical programming for the scheduling problem with alternative process plans in FMS [J]. Computer & Industrial Engineering, 1994, 27(1–4): 15-18

[9] KimK. H., EgbeluP. J.. A mathematical model for job shop scheduling with multiple process plan consideration per job [J]. Production Planning & Control, 1998, 9: 250-259

[10] ChoiI. C., ChoiD. S.. A local search algorithm for job shop scheduling problems with alternative operations and sequence-dependent setups [J]. Computers & Industrial Engineering, 2002, 42(1): 43-58

[11] ChenJ. S., PanJ. C. H.. Minimising mean tardiness with alternative operations in two-machine flow-shop scheduling [J]. International Journal of Systems Science, 2005, 36(12): 757-766

[12] ThomallaC. S.. Job shop scheduling with alternative process plans [J]. International Journal of Production Economics, 2001, 74(1): 125-134

[13] Dauzère-PérèsS., PaulliJ.. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling [J]. Annals of Operations Research, 1997, 70(3): 281-306

[14] LogendranR., SonthinenA.. A Tabu search-based approach for scheduling job-shop type flexible manufacturing systems [J]. Journal of Operational Research Society, 1997, 48(3): 264-277

[15] Bilge, KiraçF., KurtulanM., PekgünP.. A tabu search algorithm for parallel machine total tardiness problem [J]. Computers & Operations Research, 2004, 31(3): 397-414

[16] ScrichC. R., ArmentanoV. A., LagunaM.. Tardiness minimization in a flexible job shop: A tabu search approach [J]. Journal of Intelligent Manufacturing, 2004, 15(1): 103-115

[17] CaoD., ChenM., WanG.. Parallel machine selection and job scheduling to minimize machine cost and job tardiness [J]. Computers & Operations Research, 2005, 32(8): 1995-2012

[18] MehrabadM. S., FattahiP.. Flexible job shop scheduling with tabu search algorithms [J]. International Journal of Advanced Manufacturing Technology, 2007, 32(5/6): 563-570

[19] CandidoM. A. B., KhatorS. K., BarciaR. M.. A genetic algorithm based procedure for more realistic job shop scheduling problems [J]. International Journal of Production Research, 1998, 36(12): 3437-3457

[20] ZhaoC., WuZ.. A genetic algorithm approach to the scheduling of FMSs with multiple routes [J]. International Journal of Flexible Manufacturing Systems, 2001, 13(1): 71-88

[21] RossiA., DiniG.. An evolutionary approach to complex job-shop and flexible manufacturing system scheduling [J]. Journal of Engineering Manufacture, 2001, 215(2): 233-245

[22] KimY. K., ParkK., KoJ.. A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling [J]. Computers & Operations Research, 2003, 30(8): 1151-1171

[23] Tavakkoli-MoghaddamR., KhodadadeghanY., HaghnevisM.. Efficient algorithm for a multi-criteria parallel machine scheduling problem with sequence-dependent setup times [C]. Proceedings of 5th International Symposium on Intelligent Manufacturing Systems, 2006Sakarya, TurkeySakarya University159-167

[24] BASKAK M, EROL V A. Genetic algorithm approach for solving flexible job-shop scheduling problem [C]// Proceedings of 35th International Conference on Computers & Industrial Engineering. Istanbul, Turkey, 2005: 245–250.

[25] HUSSAIN M F, JOSHI S B. A genetic algorithm for job shop scheduling problems with alternate routing [C]// IEEE International Conference on Systems, Man and Cybernetics. San Diego, CA, USA, 1998: 2225–2230.

[26] JawaharN., AravindanP., PonnambalamS. G.. A genetic algorithm for scheduling flexible manufacturing systems [J]. International Journal of Advanced Manufacturing Technology, 1998, 14(8): 588-607

[27] BeckJ. C., FoxM. S.. Constraint-directed techniques for scheduling alternative activities [J]. Artificial Intelligence, 2000, 121(1/2): 211-250

[28] FerreiraJ. C. E., WyskR. A.. On the efficiency of alternatives in process plans [J]. Journal of Brazilian Society of Mechanical Sciences, 2001, 23(3): 303-319

[29] SayginC., ChenF. F., SinghJ.. Real-time manipulation of alternative routings in flexible manufacturing systems: A simulation study [J]. International Journal of Advanced Manufacturing Technology, 2001, 18(10): 755-763

[30] DemirH. I.. Scheduling with alternative routes [C]. Proceedings of 5th International Symposium on Intelligent Manufacturing Systems, 2006Sakarya, TurkeySakarya University1323-1338

[31] RossiA., DiniG.. Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method [J]. Robotics & Computer Integrated Manufacturing, 2007, 23(5): 503-516

[32] LowC., HsuC. J., SuC. T.. A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines [J]. Computers & Operations Research, 2008, 35(3): 845-853

[33] HollandJ.Adaptation in natural and artificial systems [M], 1975Ann ArborUniversity of Michigan Press

[34] GoldbergD. E.Genetic algorithms in search, optimization and machine learning [M], 1989New YorkAddison-Wesley Publishing Company

[35] DavisL.GrefenstetteJ. J.. Job shop scheduling with genetic algorithms [C]. Proceedings of the 1st International Conference on Genetic Algorithms, 1985Hillsdale, NJLawrence Erlbaum136-140

[36] ChaudhryI. A., DrakeP. R.. Minimizing flow time variance in a single machine system using genetic algorithms [J]. International Journal of Advanced Manufacturing Technology, 2008, 39(3/4): 355-366

[37] ChaudhryI. A., DrakeP. R.. Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms [J]. International Journal of Advanced Manufacturing Technology, 2009, 42(5/6): 581-594

[38] ChaudhryI. A.. Minimizing flow time for the worker assignment problem in identical parallel machine models using GA [J]. International Journal of Advanced Manufacturing Technology, 2009, 48(5–8): 747-760

[39] Palisade Corp.Genetic algorithm solver for Microsoft Excel: Guide to evolver [M], 1998New YorkPalisade corporation

[40] DavisL.Handbook of genetic algorithms [M], 1991New YorkVan Nostrand Reinhold332-349

[41] MuellerK.Development, implementation and test of a heuristic branch-and-bound procedure for machine assignment in flexible manufacturing system [D], 1992DiplomarbeitUniversitat Karlsruhe, Fakultat fur Informatik

[42] SundaramR. M., FuS. S.. Process planning and scheduling-A method of integration for productivity improvement [J]. Computers & Industrial Engineering, 1998, 15(1–4): 296-301

[43] MoradN., ZalzalaA. M. S.. Genetic algorithms in integrated process planning and scheduling [J]. Journal of Intelligent Manufacturing, 1999, 10(2): 169-179

[44] PalmerG. J.. A simulated annealing approach to integrated production scheduling [J]. Journal of Intelligent Manufacturing, 1996, 7(3): 163-176

[45] KacemI., HammadiS., BorneP.. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems [J]. IEEE Transactions on Systems, Man & Cybernetics, Part C, 2002, 32(1): 1-13

[46] XingL. N., ChenY. W., YangK. W.. Multi-objective flexible job shop schedule: Design and evaluation by simulation modelling [J]. Applied Soft Computing, 2009, 9(1): 362-376

[47] XiaW., WuZ.. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems [J]. Computers & Industrial Engineering, 2005, 48(3): 409-425

[48] ZhangH., GenM.. Multistage-based genetic algorithm for flexible job-shop scheduling problem [J]. Journal of Complexity International, 2005, 11: 223-232