×

An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. (English) Zbl 1177.90195

Summary: The Distributed and Flexible Job-shop Scheduling problem (DFJS) considers the scheduling of distributed manufacturing environments, where jobs are processed by a system of several Flexible Manufacturing Units (FMUs). Distributed scheduling problems deal with the assignment of jobs to FMUs and with determining the scheduling of each FMU, in terms of assignment of each job operation to one of the machines able to work it (job-routing flexibility) and sequence of operations on each machine. The objective is to minimize the global makespan over all the FMUs. This paper proposes an Improved Genetic Algorithm to solve the Distributed and Flexible Job-shop Scheduling problem. With respect to the solution representation for non-distributed job-shop scheduling, gene encoding is extended to include information on job-to-FMU assignment, and a greedy decoding procedure exploits flexibility and determines the job routings. Besides traditional crossover and mutation operators, a new local search based operator is used to improve available solutions by refining the most promising individuals of each generation. The proposed approach has been compared with other algorithms for distributed scheduling and evaluated with satisfactory results on a large set of distributed-and-flexible scheduling problems derived from classical job-shop scheduling benchmarks.

MSC:

90B35 Deterministic scheduling theory in operations research
90B30 Production models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, J. E., Adaptive selection methods for genetic algorithms, (Proceedings of the 1st International Conference on Genetic Algorithms (Mahwah, NJ, USA) (1985), Lawrence Erlbaum Associates, Inc.), 101-111
[2] J.W. Barnes, J.B. Chambers, Flexible job shop scheduling by tabu search, Graduate Program in Operations Research and Industrial Engineering, Technical Report Series ORP96-09, The University of Texas at Austin, 1996.; J.W. Barnes, J.B. Chambers, Flexible job shop scheduling by tabu search, Graduate Program in Operations Research and Industrial Engineering, Technical Report Series ORP96-09, The University of Texas at Austin, 1996.
[3] A.M. Barroso, J.R.A. Torreau, J.C.B. Leite, O.G. Loques, J.S. Fraga, A new technique for task allocation in real-time distributed systems, in: Proceedings of the 7th Brasilian Symposium of Fault Tolerant Computers, Campina Grande, Brazil, 1997, pp. 269-278.; A.M. Barroso, J.R.A. Torreau, J.C.B. Leite, O.G. Loques, J.S. Fraga, A new technique for task allocation in real-time distributed systems, in: Proceedings of the 7th Brasilian Symposium of Fault Tolerant Computers, Campina Grande, Brazil, 1997, pp. 269-278.
[4] Baykasoglu, A., Linguistic-based meta-heuristic optimization model for flexible job shop scheduling, International Journal of Production Research, 40, 17, 4523-4543 (2002) · Zbl 1064.90541
[5] Beasley, D.; Bull, D.; Martin, R. R., An overview of genetic algorithms: Part 1, Fundamentals, University Computing, 15, 2, 58-69 (1993)
[6] Brandimarte, P., Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research, 22, 158-183 (1993) · Zbl 0775.90227
[7] Chan, F. T.S.; Chung, S. H.; Chan, L. Y.; Finke, G.; Tiwari, M. K., Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach, Robotics and Computer-Integrated Manufacturing, 22, 493-504 (2006)
[8] Chan, F. T.S.; Chung, S. H.; Chan, P. L.Y., An adaptive genetic algorithm with dominated genes for distributed scheduling problems, Expert Systems with Applications, 29, 364-371 (2005)
[9] Chan, F. T.S.; Chung, S. H.; Chan, P. L.Y., Application of genetic algorithms with dominated genes in a distributed scheduling problem in flexible manufacturing, International Journal of Production Research, 44, 3, 523-543 (2006)
[10] H. Chen, J. Ihlow, C. Lehmann, A genetic algorithm for flexible job-shop scheduling, in: IEEE International Conference on Robotics and Automation, Detroit, Michigan, 1999, pp. 1120-1125.; H. Chen, J. Ihlow, C. Lehmann, A genetic algorithm for flexible job-shop scheduling, in: IEEE International Conference on Robotics and Automation, Detroit, Michigan, 1999, pp. 1120-1125.
[11] Choi, I. C.; Choi, D. S., A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups, Computers and Industrial Engineering Archive, 42, 1, 43-58 (2002)
[12] Cicirello, V. A.; Smith, F. S., Wasp-like agents for distributed factory coordination, Autonomous Agents and Multi-Agent Systems, 8, 237-266 (2004)
[13] Dauzère-Pérès, S.; Paulli, J., An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search, Annals of Operations Research, 70, 281-306 (1997) · Zbl 0890.90097
[14] M. Di Natale, J.A. Stankovic, Applicability of simulated annealing methods to real time scheduling and jitter control, in: Proceedings of the 16th IEEE Real-Time Systems Symposium, Pisa, Italy, 1995, pp. 190-199.; M. Di Natale, J.A. Stankovic, Applicability of simulated annealing methods to real time scheduling and jitter control, in: Proceedings of the 16th IEEE Real-Time Systems Symposium, Pisa, Italy, 1995, pp. 190-199.
[15] Fisher, H.; Thompson, G. L., Probabilistic learning combinations of local job shop scheduling rules, (Muth, J. F.; Thompson, G. L., Industrial Scheduling (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ), 225-251
[16] Garey, M. R.; Johnson, D. S.; Sethi, R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117-129 (1976) · Zbl 0396.90041
[17] N.B. Ho, J.C. Tay, GENACE: An efficient cultural algorithm for solving the flexible job-shop problem, in: Proceedings of the IEEE Congress on Evolutionary Computation, 2004, pp. 1759-1766.; N.B. Ho, J.C. Tay, GENACE: An efficient cultural algorithm for solving the flexible job-shop problem, in: Proceedings of the IEEE Congress on Evolutionary Computation, 2004, pp. 1759-1766.
[18] Hurink, E.; Jurisch, B.; Thole, M., Tabu search for the job shop scheduling problem with multi-purpose machines, Operations Research Spektrum, 15, 205-215 (1994) · Zbl 0798.90086
[19] Jia, H. Z.; Fuh, J. Y.H.; Nee, A. Y.C.; Zhang, Y. F., A modified genetic algorithm for distributed scheduling problems, Journal of Intelligent Manufacturing, 15, 351-362 (2003)
[20] Kacem, I.; Hammadi, S.; Borne, P., Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems, IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, 32, 1, 1-13 (2002)
[21] S. Lawrence, Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques, Tech. Report, GSIA, Carnegie Mellon University, Pittsburgh, PA, 1984.; S. Lawrence, Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques, Tech. Report, GSIA, Carnegie Mellon University, Pittsburgh, PA, 1984.
[22] Lee, D. Y.; Di Cesare, F., Scheduling flexible manufacturing systems using Petri nets and heuristic search, IEEE Transactions on Robotics and Automation, 10, 2, 123-132 (1994)
[23] M. Mastrolilli, <http://www.idsia.ch/ monaldo/fjsp.html>; M. Mastrolilli, <http://www.idsia.ch/ monaldo/fjsp.html>
[24] Mastrolilli, M.; Gambardella, L. M., Effective neighbourhood functions for the flexible job shop problem, Journal of Scheduling, 3, 3-20 (2000) · Zbl 1028.90018
[25] M. Mastrolilli, L.M. Gambardella, Effective neighbourhood functions for the flexible job shop problem: Appendix, Technical Report, IDSIA - Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, 2000. Electronic version available at: <http://www.idsia.ch/ monaldo/fjsp.html>; M. Mastrolilli, L.M. Gambardella, Effective neighbourhood functions for the flexible job shop problem: Appendix, Technical Report, IDSIA - Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, 2000. Electronic version available at: <http://www.idsia.ch/ monaldo/fjsp.html> · Zbl 1028.90018
[26] Pezzella, F.; Morganti, G.; Ciaschetti, G., A genetic algorithm for the flexible job-shop scheduling problem, Computers and Operations Research, 35, 3202-3212 (2008) · Zbl 1162.90014
[27] Santos, J.; Ferro, E.; Orozco, J.; Cayssials, R., A realistic approach to the multitask-multiprocessor assignment problem using the empty-slots method and rate-monotonic scheduling, Journal of Real-time Systems, 13, 167-199 (1997)
[28] M.J. Schniederjans, International Facility Acquisition and Location Analysis, Quorum Books, Westport, 1999.; M.J. Schniederjans, International Facility Acquisition and Location Analysis, Quorum Books, Westport, 1999.
[29] Sule, D. R., Logistics of Facility Location and Allocation (1999), Marcel Dekker Inc.: Marcel Dekker Inc. New York, NY
[30] Tay, J. C.; Wibowo, D., An effective chromosome representation for evolving flexible job shop schedules, (GECCO. GECCO, LNCS, vol. 3103 (2004), Springer Verlag: Springer Verlag Berlin), 210-221
[31] Tindell, K. W.; Burns, A.; Wellings, A. J., Allocating hard realtime tasks: A NP-hard problem made easy, Journal of Real-time Systems, 4, 145-165 (1992)
[32] R.J.M. Vaessens, E.H.L. Aarts, J. Lenstra, Job shop Scheduling by Local Search, COSOR Memorandum 94-05, Eindhoven University of Technology, 1994.; R.J.M. Vaessens, E.H.L. Aarts, J. Lenstra, Job shop Scheduling by Local Search, COSOR Memorandum 94-05, Eindhoven University of Technology, 1994. · Zbl 0863.90094
[33] Xia, W.; Wu, Z., An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Computers and Industrial Engineering Archive, 48, 2, 409-425 (2005)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.