Nothing Special   »   [go: up one dir, main page]

skip to main content
article

A research survey: review of AI solution strategies of job shop scheduling problem

Published: 01 October 2015 Publication History

Abstract

This paper focus on artificial intelligence approaches to NP-hard job shop scheduling (JSS) problem. In the literature successful approaches of artificial intelligence techniques such as neural network, genetic algorithm, multi agent systems, simulating annealing, bee colony optimization, ant colony optimization, particle swarm algorithm, etc. are presented as solution approaches to job shop scheduling problem. These studies are surveyed and their successes are listed in this article.

References

[1]
Akyol, D. E., & Bayhan, G. M. (2007). A review on evolution of production scheduling with neural networks. Computers and Industrial Engineering, 53, 95-122.
[2]
Asadzadeh, L., & Zamanifar, K. (2010). An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Mathematical and Computer Modelling, 52, 1957-1965.
[3]
Aydin, M. E., & Oztemel, E. (2000). Dynamic job-shop scheduling using reinforcement learning agents. Robotics and Autonomous Systems, 33, 169-178.
[4]
Aydin, E., & Fogarty, T. C. (2004). A simulated annealing algorithm for multi-agent systems: A job shop scheduling application. Journal of Intelligent Manufacturing, 15, 805-814.
[5]
Bierwirth, C., & Mattfeld, D. C. (1999). Production scheduling and rescheduling with genetic algorithms. Evolutionary Computation, 7(1), 1-17.
[6]
Bilkay, O., Anlagan, O., & Kilic, S. (2004). Job shop scheduling using fuzzy logic. International Journal of Advanced Manufacturing Technology, 23(7-8), 606-619.
[7]
Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3), 157-183.
[8]
Buchanan, G. G. (2005). A (very) brief history of artificial intelligence. In 25th Anniversary Issue, AI Magazine winter (pp. 53-60).
[9]
Canbolat, Y. B., & Gundo¿ar, E. (2004). Fuzzy priority rule for job shop scheduling. Journal of Intelligent Manufacturing, 15, 527-533.
[10]
Cao, Y., Yang, Y., Wang, H., & Yang, L. (2009). Intelligent job shop scheduling based on MAS and integrated routing wasp algorithm and scheduling wasp algorithm. Journal of Software, 4(5), 487-494.
[11]
Cha, Y., & Jung, M. (2003). Satisfaction assessment of multi-objective schedules using neural fuzzy methodology. International Journal of Production Research, 41(8), 1831-1849.
[12]
Chambers, L. (2001). Practical handbook of genetic algorithms: Applications (Vol. I). Boca Raton, Florida: CRC Press.
[13]
Chan, F. T. S., Chung, S. H., & Chan, P. L. Y. (2005). An adaptive genetic algorithm with dominated genes for distributed scheduling problems. Expert Systems with Applications, 29, 364-371.
[14]
Chan, F. T. S., Wong, T. C., & Chan, L. Y. (2008). Lot streaming for product assembly in job shop environment. Robotics and Computer-Integrated Manufacturing, 24, 321-331.
[15]
Chan, F. T. S., Wong, T. C., & Chan, L. Y. (2009). The application of genetic algorithms to lot streaming in a job-shop scheduling problem. International Journal of Production Research, 47(12), 3387-3412.
[16]
Chan, F. T. S., Choy, K. L., & Bibhushan, (2011). A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop. Expert Systems with Applications, 38(7), 8703-8715.
[17]
Chen, M., & Dong, Y. (1999). Applications of neural networks to solving SMT scheduling problems--A case study. International Journal of Production Research, 37(17), 4007-4020.
[18]
Chen, J. C., Chen, K. H., Wu, J. J., & Chen, C. W. (2008). A study of fexible job shop scheduling problem with parallel machine and reentrant process. International Journal of Advanced Manufacturing Technology, 39(3/4), 344-354.
[19]
Chen, J. C., Wu, C.-C., Chen, C.-W., & Chen, K.-H. (2012). Flexible job shop scheduling with parallel machines using genetic algorithm and grouping genetic algorithm. Expert Systems with Applications, 39, 10016-10021.
[20]
Cheung, W., & Zhou, H. (2001). Using genetic algorithms and heuristics for job shop scheduling with sequence-dependent setup times. Annals of Operations Research, 107, 65-81.
[21]
Chong C. S., Low M.Y.H., Sivakumar, A. I., & Gay, K. L. (2006). A bee colony optimization algorithm to job shop scheduling. In Proceeding WSC'06 proceedings of the 38th conference on Winter, simulation (pp. 1954-1961).
[22]
Chryssolouris, G., & Subramaniam, V. (2001). Dynamic scheduling of manufacturing job shops using genetic algorithms. Journal of Intelligent Manufacturing, 12(3), 281-293.
[23]
Cleveland, G. A. & Smith, S. F. (1989). Using genetic algorithms to schedule flow shop releases. In Proceedings of the 3rd international conference on genetic algorithms (pp. 160-169).
[24]
Colorni, A., Dorigo, M., & Maniezzo, V. (1991). Distributed optimization by ant colonies. In Actes de la première conférence européenne sur la vie artificielle (pp. 134-142). Elsevier Publishing, Paris, France
[25]
Crevier, D. (1993). AI: The tumultuous search for artificial intelligence. New York, NY: Basic Books.
[26]
Davis, L. (1985). Job shop scheduling with genetic algorithms. In Proceedings of the 1st international conference on genetic algorithms (pp. 136-140).
[27]
Davis, L. (1991). Handbook of genetic algorithms. New York: Van Nostrand Reinhold.
[28]
Dorigo, M. (1992). Optimization, learning and natural algorithms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy.
[29]
Feng, S., Li, L., Cen, L., & Huang, J. (2003). Using MLP networks to design a production scheduling system. Computers and Operations Research, 30, 821-832.
[30]
Fonseca, D. J., & Navaresse, D. (2002). Artificial neural networks for job shop simulation. Advanced Engineering Informatics, 16, 241- 246.
[31]
Gabel, T. & Riedmiller, M. (2007). Scaling adaptive agent-based reactive job-shop scheduling to large-scale problems. In Proceedings of the 2007 IEEE symposium on computational intelligence in scheduling.
[32]
Ge, H., Du, W., & Qian, F. (2007). A hybrid algorithm based on particle swarm optimization and simulated annealing for job shop scheduling. In Proceedings of the third international conference on natural computation, vol. 3 (pp. 715-719).
[33]
Geneste, L., & Grabot, B. (1997). Implicit versus explicit knowledge representation in a job shop scheduling decision support system. International Journal of Expert Systems, 10(1), 37-52.
[34]
Geyik, F., & Cedimoglu, I. H. (2004). The Strategies and parameters of tabu search for job-shop scheduling. Journal of Intelligent Manufacturing, 15, 439-448.
[35]
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13, 533- 549.
[36]
Glover, F. (1989). Tabu search-part I. ORSA Journal on Computing, 1, 190-206.
[37]
Gonçalves, J. F., Mendes, J. J. de M., Resende, M. G. C., (2005). A hybrid genetic algorithm for the job shop scheduling problem. AT & T Labs Research Technical Report TD-5EAL6J.
[38]
Goss, S., Aron, S., Deneubourg, J.-L., & Pasteels, J.-M. (1989). Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 76, 579-581.
[39]
Hansen, P., & Mladenovi'c, N., Perez, J. A. M. (2008). Variable neighbourhood search: methods and applications. Annals of Operations Research 6, 319-360.
[40]
Heinonen, J., & Pettersson, F. (2007). Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem. Applied Mathematics and Computation, 187, 989-998.
[41]
Holland, J. H. (1975). Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor: Michigan; re-issued by MIT Press, (1992).
[42]
Holland, J. H., & Miller, J. H. (1991). Artificial adaptive agents in economic theory. American Economic Review, 81(2), 365-371.
[43]
Huang, Y. M., & Chen, R. M. (1999). Scheduling multiprocessor job with resource and timing constraints using neural networks. IEEE Transactions on Systems, Man and Cybernetics-Part B: Cybernetics, 29(4), 490-502.
[44]
Huang, K. L., & Liao, C. J. (2008). Ant colony optimization combined with taboo search for the job shop scheduling problem. Computers and Operations Research, 35, 1030-1046.
[45]
Huang, R. H. (2010). Multi-objective job-shop scheduling with lot-splitting production. International Journal of Production Economics, 124, 206-213.
[46]
Huang, J., Süer, G. A., & Urs, S. B. R. (2012). Genetic algorithm for rotary machine scheduling with dependent processing times. Journal of Intelligent Manufacturing, 23, 1931-1948.
[47]
Jain, A. S., & Meeran, S. (1998). Job shop scheduling using neural networks. International Journal of Production Research, 36(5), 1249-1272.
[48]
Kacem. I, & Hammadi, S., (2002b). Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions On Systems, Man, And Cybernetics-Part C: Applications And Reviews, 32(1), 1-13.
[49]
Kacem, I., Hammadi, S., & Borne, P. (2002a). Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation, 60(3-5), 245-276.
[50]
Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department.
[51]
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks, 4, 1942-1948.
[52]
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671-680.
[53]
Kreipl, S. (2000). A large step random walk for minimizing total weighted tardiness in a job shop. Journal of Scheduling, 3, 125-138.
[54]
Lei, D. (2012a). Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling. Applied Soft Computing, 12, 2237-2245.
[55]
Lei, D. (2012b). Minimizing makespan for scheduling stochastic job shop with random breakdown. Applied Mathematics and Computation, 218, 11851-11858.
[56]
Lenstra, J. K., Kan, A. H. G. R., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343-362.
[57]
Lian, Z. G., Jiao, B., & Gu, X. S. (2006). A similar particle swarm optimization for job-shop scheduling to minimize makespan. Applied Mathematics and Computation, 183, 1008-1017.
[58]
Liepins, G. E. & Hilliard, M.R. (1987). Greedy genetics. In Proceedings of the 2nd international conference on genetic algorithms (pp. 90-99).
[59]
Lin, T.-L., Horng, S.-J., Kao, T.-W., Chen, Y.-H., Run, R.-S., Chen, R.- J., et al. (2010). An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Systems with Applications, 37, 2629-2636.
[60]
Liu, M., Sun, Z. J., Yan, J. W., & Kang, J. S. (2011). An adaptive annealing genetic algorithm for the job-shop planning and scheduling problem. Expert Systems with Applications, 38(8), 9248-9255.
[61]
Lowerre, B. T., (1976). The HARPY speech recognition system. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA.
[62]
Mattfeld, D. C., & Bierwirth, C. (2004). An efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research, 155(3), 616-630.
[63]
Mehrabad, M. S., & Fattahi, P. (2007). Flexible job shop scheduling with tabu search algorithms. The International Journal of Advanced Manufacturing Technology, 32, 563-570.
[64]
Mladenovi'c, N., & Hansen, P. (1997). Variable neighborhood search. Computers and Operations Research, 24(11), 1097-1100.
[65]
NaitTahar, D., Yalaoui, F., Amodeo, L., & Chu, C. (2005). An ant colony system minimizing total tardiness for hybrid job shop scheduling problem with sequence dependent setup times and release dates. In International Conference on Industrial Engineering and Systems Management, (No. 10).
[66]
Nakano, R. & Yamada, T. (1991). Conventional genetic algorithms for job shop problems. In Proceedings of the 4th international conference on genetic algorithms (pp. 474-479).
[67]
Ombuki, B. M., & Ventresca, M. (2004). Local search genetic algorithms for the job shop scheduling problem. Applied Intelligence, 21, 99-109.
[68]
Ow, P. S., & Morton, T. E. (1988). Filtered beam search in scheduling. International Journal of Production Research, 26, 297-307.
[69]
Pendharkar, P. C. (1999). A computational study on design and performance issues of multi-agent intelligent systems for dynamic scheduling environments. Expert Systems with Applications, 16(2), 121- 133.
[70]
Peres, S. D., & Paulli, J. (1997). An integrated approach for modeling and solving the general multiprocessor job-shopscheduling problem using tabu search. Annals of Operations Research, 70, 281-306.
[71]
Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers and Operations Research, 35, 3202-3212.
[72]
Pham, D. T., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S., & Zaidi, M. (2005). The Bees Algorithm. Technical Note: Manufacturing Engineering Centre, Cardiff University, UK.
[73]
Qing-dao-er-ji, R., & Wang, Y. (2012). A new hybrid genetic algorithm for job shop scheduling problem. Computers and Operations Research, 39, 2291-2299.
[74]
Rebai, M., Kacem, I., & Adjallah, K. H. (2012). Earliness-tardiness minimization on a single machine to schedule preventive maintenance tasks: Metaheuristic and exact methods. Journal of Intelligent Manufacturing, 23, 1207-1224.
[75]
Roshanaei, V., Naderi, B., Jolai, F., & Khalili, M. (2009). A variable neighborhood search for job shop scheduling with set-up times to minimize makespan. <Future Generation Computer Systems, 25, 654- 661.
[76]
Ross, E. H. P., & Corne, D. (2005). Evolutionary scheduling: A review. Genetic Programming and Evolvable Machines, 6, 191-220.
[77]
Rossi, A., & Dini, G. (2007). Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method. Robotics and Computer-Integrated Manufacturing, 23, 503-516.
[78]
Russell, Stuart J., & Norvig, Peter. (2003). Artificial intelligence: A modern approach (2nd ed.). Upper Saddle River, New Jersey: Prentice Hall.
[79]
Sabuncuoglu, I., & Gurgun, B. (1996). A neural network model for scheduling problems. European Journal of Operational Research, 93(2), 288-299.
[80]
Sabuncuoglu, I., & Bayiz, M. (1999). Job shop scheduling with beam search. European Journal of Operational Research, 118(2), 390- 412.
[81]
Sabuncuoglu, I., & Touhami, S. (2002). Simulation metamodelling with neural networks: An experimental investigation. International Journal of Production Research, 40(11), 2483-2505.
[82]
Sakawa, M., & Kubota, R. (2000). Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy due-date through genetic algorithms. European Journal of Operational Research, 120, 393-407.
[83]
Scheduling, Pinedo M. (1995). Theory, algorithms, and systems. Englewood Cliffs: Prentice-Hall.
[84]
Spyropoulos, C. D. (2000). AI planning and scheduling in the medical hospital environment. Artificial Intelligence in Medicine, 20, 101- 111.
[85]
Surekha, P., & Sumathi, S. (2010). Solving fuzzy based job shop scheduling problems using Ga and ACO. Journal of Emerging Trends in Computing and Information Sciences, 1(2), 95-102.
[86]
Surekha, P., & Sumathi, S. (2011). Solution to the job shop scheduling problem using hybrid genetic swarm optimization based on (¿, 1)-interval fuzzy processing time. European Journal of Scientific Research, 64(2), 168-188.
[87]
Usher, J. M. (2003). Negotiation-based routing in job shops via collaborative agents. Journal of Intelligent Manufacturing, 14(5), 485-499.
[88]
Varthanan, P. A., Murugan, N., & Kumar, G. M. (2012). A simulation based heuristic discrete particle swarm algorithm for generating integrated production-distribution plan. Apllied Soft Computing, 12(9), 3034-3050.
[89]
Wang, L., & Zheng, D. (2001). An effective hybrid optimisation strategy for job-shop scheduling problems. Computers and Operations Research, 28(6), 585-596.
[90]
Wang, L., Zhou, G., Xu, Y., Wang, S., & Liu, M. (2012). An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 60, 303-315.
[91]
Watanabe, M., Ida, K., & Gen, M. (2005). A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Computers and Industrial Engineering, 48, 743-752.
[92]
Weckman, G. R., Ganduri C, V., & Koonce, D. A. (2008). A neural network job-shop scheduler. Journal of Intelligent Manufacturing, 19, 191-201.
[93]
Wiers, V. (1997). A review of the applicability of OR and AI scheduling techniques in practice. Omega, International Journal of Management Science, 25(2), 145-153.
[94]
Wong, T. C., Chan, F. T. S., & Chan, L. Y. (2009). A resource constrained assembly job shop scheduling problem with lot streaming technique. Computers and Industrial Engineering, 57, 983-995.
[95]
Wu, S. D., Storer, R. H., & Chang, P. C. (1991). A rescheduling procedure for manufacturing systems under random disruptions. In Proceedings joint USA/German conference on new directions for operations research in manufacturing (pp. 292-306).
[96]
Wu, S.D., Storer, R.H., & Chang, P. C. (1993). One machine rescheduling heuristics with efficiency and stability as criteria. Computers and Operations Research, 20(1), 1-14.
[97]
Xing, L. N., Chen, Y. W., Wang, P., Zhao, Q. S., & Xiong, J. (2010). A knowledge-based ant colony optimization for flexible job shop scheduling problems. Applied Soft Computing, 10, 888-896.
[98]
Yang, J., Sun, L., Lee, H. P., Qian, Y., & Liang, Y.-C. (2008). Clonal selection based memetic algorithm for job shop scheduling problems. Journal of Bionic Engineering, 5, 111-119.
[99]
Yazdani, M., Amiri, M., & Zandieh, M. (2010). Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Systems with Applications, 37(1), 678-687.
[100]
Yen, J., & Langari, R. (1999). Fuzzy Logic: Intelligence, Control, and Information. Englewood Cliffs: Prentice Hall.
[101]
Zadeh, L. A. (1965). Fuzzy sets. Information and Control, 8(3), 338- 353.
[102]
Zandieh, M., & Adibi, M. A. (2010). Dynamic job shop scheduling using variable neighbourhood search. International Journal of Production Research, 48, 2449-2458.
[103]
Zhang, H. C., & Huang, S. H. (1995). Applications of neural networks in manufacturing: A state of the art survey. International Journal of Production Research, 33, 705-728.
[104]
Zhang, G., Shao, X., Li, P., & Gao, L. (2009). An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers and Industrial Engineering, 56, 1309-1318.
[105]
Zhang, R. (2011). An artificial bee colony algorithm based on problem data properties for scheduling job shops. Procedia Engineering, 23, 131-136.
[106]
Zhang, R., Song, S., & Wu, C. (2013). A hybrid artificial bee colony algorithm for the job shop scheduling problem. International Journal of Production Economics, 141, 167-178.
[107]
Zhou, H., Cheung, W., & Leung, L. C. (2009). Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm European Journal of Operational Research. Vol., 194, 637-649.
[108]
Zurada, J. M. (1992). Introduction to Artificial Neural Systems. New York: West Publishing Company.

Cited By

View all
  • (2024)Survey on Genetic Programming and Machine Learning Techniques for Heuristic Design in Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325524628:1(147-167)Online publication date: 1-Feb-2024
  • (2024)Dynamic flexible scheduling with transportation constraints by multi-agent reinforcement learningEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108699134:COnline publication date: 1-Aug-2024
  • (2024)A hybrid evolution strategies-simulated annealing algorithm for job shop scheduling problemsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108016133:PAOnline publication date: 1-Jul-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Intelligent Manufacturing
Journal of Intelligent Manufacturing  Volume 26, Issue 5
October 2015
216 pages

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 October 2015

Author Tags

  1. Artificial intelligence
  2. Metaheuristic
  3. Scheduling

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 02 Oct 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Survey on Genetic Programming and Machine Learning Techniques for Heuristic Design in Job Shop SchedulingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325524628:1(147-167)Online publication date: 1-Feb-2024
  • (2024)Dynamic flexible scheduling with transportation constraints by multi-agent reinforcement learningEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108699134:COnline publication date: 1-Aug-2024
  • (2024)A hybrid evolution strategies-simulated annealing algorithm for job shop scheduling problemsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108016133:PAOnline publication date: 1-Jul-2024
  • (2024)Two-machine job-shop scheduling with one joint jobDiscrete Applied Mathematics10.1016/j.dam.2023.11.037346:C(30-43)Online publication date: 31-Mar-2024
  • (2024)An improved MOEA/D for low-carbon many-objective flexible job shop scheduling problemComputers and Industrial Engineering10.1016/j.cie.2024.109926188:COnline publication date: 17-Apr-2024
  • (2023)A generic enhanced search framework based on genetic algorithmJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-23007645:4(7095-7111)Online publication date: 1-Jan-2023
  • (2023)A Taxonomy and Archetypes of Business Analytics in Smart ManufacturingACM SIGMIS Database: the DATABASE for Advances in Information Systems10.1145/3583581.358358454:1(11-45)Online publication date: 7-Feb-2023
  • (2023)DeepMAGKnowledge-Based Systems10.1016/j.knosys.2022.110083259:COnline publication date: 10-Jan-2023
  • (2023)Maximizing the service level on the makespan in the stochastic flexible job-shop scheduling problemComputers and Operations Research10.1016/j.cor.2023.106237157:COnline publication date: 1-Sep-2023
  • (2023)Neighbourhood search for energy minimisation in flexible job shops under fuzzinessNatural Computing: an international journal10.1007/s11047-023-09967-w22:4(685-704)Online publication date: 18-Oct-2023
  • Show More Cited By

View Options

View options

Get Access

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media