Graph Modeling of Shop Schedulings: Comparison
View Latest Version
Please note this is a comparison between Version 2 by Conner Chen and Version 1 by Golshan Madraki.

Graphs are powerful tools to model manufacturing systems and scheduling problems. The complexity of these systems and their scheduling problems has been substantially increased by the ongoing technological development. Thus, it is essential to generate sustainable graph-based modeling approaches to deal with these excessive complexities. Graphs employ nodes and edges to represent the relationships between jobs, machines, operations, etc. Despite the significant volume of publications applying graphs to shop scheduling problems, the literature lacks a comprehensive survey study. We proposed the first comprehensive review paper which 1) systematically studies the overview and the perspective of this field, 2) highlights the gaps and potential hotspots of the literature, and 3) suggests future research directions towards sustainable graphs modeling the new intelligent/complex systems. We carefully examined 143 peer-reviewed journal papers published from 2015 to 2020. About 70% of our dataset were published in top-ranked journals which confirms the validity of our data and can imply the importance of this field. After discussing our generic data collection methodology, we proposed categorizations over the properties of the scheduling problems and their solutions. Then, we discussed our novel categorization over the variety of graphs modeling scheduling problems. Finally, as the most important contribution, we generated a creative graph-based model from scratch to represent the gaps and hotspots of the literature accompanied with statistical analysis on our dataset. Our analysis showed a significant attention towards job shop systems (56%) and Un/Directed Graphs (52%) where edges can be either directed, or undirected, or both. Whereas 14% of our dataset applied only Undirected Graphs, and 11% targeted hybrid systems, e.g., mixed shop, flexible and cellular manufacturing systems which shows potential future research directions.

  • graph theory
  • shop scheduling problem
  • Modeling
  • Manufacturing systems
  • A systematic review and categorization methodology
Please wait, diff process is still running!

References

  1. Trudeau, R.J. Introduction to Graph. Theory; Courier Corporation: North Chelmsford, MA, USA, 2013.
  2. Carlson, S.C. Königsberg Bridge Problem, in Encyclopedia Britannica. 2010. Available online: (accessed on 16 May 2021).
  3. Mehrani, R.; Sharma, S. Behavior of water confined between hydrophobic surfaces with grafted segments. Colloid Interface Sci. Commun. 2021, 40, 100355.
  4. Madraki, Y.; Oakley, A.; Le, A.N.; Colin, A.; Ovarlez, G.; Hormozi, S. Shear thickening in dense non-Brownian suspensions: Viscous to inertial transition. J. Rheol. 2020, 64, 227–238.
  5. Riaz, F.; Ali, K.M. Applications of Graph Theory in Computer Science. In Proceedings of the 2011 Third International Conference on Computational Intelligence, Communication Systems and Networks, Bali, Indonesia, 26–28 July 2011; pp. 142–145.
  6. Madraki, G.; Grasso, I.; Otala, J.; Liu, Y.; Matthews, J. Characterizing and Comparing COVID-19 Misinformation Across Languages, Countries and Platforms. arXiv 2020, arXiv:2010.06455.
  7. Amato, F.; Castiglione, A.; De Santo, A.; Moscato, V.; Picariello, A.; Persia, F.; Sperlí, G. Recognizing human behaviours in online social networks. Comput. Secur. 2018, 74, 355–370.
  8. Amato, F.; Moscato, V.; Picariello, A.; Sperli, G. Multimedia Social Network Modeling: A Proposal. In Proceedings of the 2016 IEEE Tenth International Conference on Semantic Computing (ICSC), Laguna Hills, CA, USA, 4–6 February 2016; pp. 448–453.
  9. Otala, J.M.; Kurtic, G.; Grasso, I.; Liu, Y.; Matthews, J.; Madraki, G. 2021. Political Polarization and Platform Migration: A Study of Parler and Twitter Usage by United States of America Congress Members. In Companion Proceedings of the Web Conference 2021 (WWW ’21 Companion), April 19–23, 2021, Ljubljana, Slovenia; ACM: New York, NY, USA, 2021; p. 10.
  10. La Gatta, V.; Moscato, V.; Postiglione, M.; Sperlì, G. CASTLE: Cluster-aided space transformation for local explanations. Expert Syst. Appl. 2021, 179, 115045.
  11. Djakbarova, U.; Madraki, Y.; Chan, E.T.; Kural, C. Dynamic interplay between cell membrane tension and clathrin-mediated endocytosis. Biol. Cell 2021.
  12. Mehrdad, S.; Mousavian, S.; Madraki, G.; Dvorkin, Y. Cyber-Physical Resilience of Electrical Power Systems Against Malicious Attacks: A Review. Curr. Sustain. Energy Rep. 2018, 5, 14–22.
  13. Mousavian, S.; Conejo, A.J.; Sioshansi, R. Equilibria in investment and spot electricity markets: A conjectural-variations approach. Eur. J. Oper. Res. 2020, 281, 129–140.
  14. Mousavian, S.; Erol-Kantarci, M.; Mouftah, H.T. Cyber-Security and Resiliency of Transportation and Power Systems in Smart Cities. In Transportation and Power Grid in Smart Cities; Wiley: Hoboken, NJ, USA, 2018; pp. 507–527.
  15. Hosseini, S.; Ivanov, D. Bayesian networks for supply chain risk, resilience and ripple effect analysis: A literature review. Expert Syst. Appl. 2020, 161, 113649.
  16. Salmani, Y.; Partovi, F.Y.; Banerjee, A. Customer-driven investment decisions in existing multiple sales channels: A downstream supply chain analysis. Int. J. Prod. Econ. 2018, 204, 44–58.
  17. La Gatta, V.; Moscato, V.; Postiglione, M.; Sperli, G. An Epidemiological Neural Network Exploiting Dynamic Graph Structured Data Applied to the COVID-19 Outbreak. IEEE Trans. Big Data 2021, 7, 45–55.
  18. Caggiano, A. Manufacturing System. In CIRP Encyclopedia of Production Engineering; Laperrière, L., Reinhart, G., Eds.; Springer: Berlin/Heidelberg, Germany, 2014; pp. 830–836.
  19. Fan, K.; Zhai, Y.; Li, X.; Wang, M. Review and classification of hybrid shop scheduling. Prod. Eng. 2018, 12, 597–609.
  20. Lamorgese, L.; Mannino, C. A Noncompact Formulation for Job-Shop Scheduling Problems in Traffic Management. Oper. Res. 2019, 67, 1586–1609.
  21. Sobeyko, O.; Mönch, L. Heuristic approaches for scheduling jobs in large-scale flexible job shops. Comput. Oper. Res. 2016, 68, 97–109.
  22. Madraki, G.; Bahalkeh, E.; Judd, R. Efficient Algorithm to Find Makespan under Perturbation in Operation Times. In Proceedings of the IIE Annual Conference, Institute of Industrial and Systems Engineers (IISE), Nashville, TN, USA, 30 May–2 June 2015; Institute of Industrial and Systems Engineers (IISE): Norcross, GA, USA, 2015.
  23. Mei, Y.; Nguyen, S.; Xue, B.; Zhang, M. An Efficient Feature Selection Algorithm for Evolving Job Shop Scheduling Rules With Genetic Programming. IEEE Trans. Emerg. Top. Comput. Intell. 2017, 1, 339–353.
  24. Nip, K.; Wang, Z.; Xing, W. A study on several combination problems of classic shop scheduling and shortest path. Theor. Comput. Sci. 2016, 654, 175–187.
  25. Panwalkar, S.S.; Koulamas, C. The evolution of schematic representations of flow shop scheduling problems. J. Sched. 2018, 22, 379–391.
  26. Zhang, J.; Ding, G.; Zou, Y.; Qin, S.; Fu, J. Review of job shop scheduling research and its new perspectives under Industry 4. J. Intell. Manuf. 2019, 30, 1809–1830.
  27. Cao, Z.; Zhou, L.; Hu, B.; Lin, C. An Adaptive Scheduling Algorithm for Dynamic Jobs for Dealing with the Flexible Job Shop Scheduling Problem. Bus. Inf. Syst. Eng. 2019, 61, 299–309.
  28. El-Desoky, I.; El-Shorbagy, M.A.; Nasr, S.M.; Hedaqy, Z.M.; Mousa, A.A. A hybrid genetic algorithm for job shop scheduling problems. Int. J. Adv. Eng. Technol. Comput. Sci. 2016, 3, 6–17.
  29. Pinedo, M. Planning and Scheduling in Manufacturing and Services; Springer: Berlin/Heidelberg, Germany, 2005.
  30. Clewett, A.J.; Baker, K.R. Introduction to Sequencing and Scheduling. Oper. Res. Q. 1977, 28, 352.
  31. Wan, G.; Yen, B.P.-C. Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. Eur. J. Oper. Res. 2002, 142, 271–281.
  32. Guan, L.; Li, J.; Li, W.; Lichen, J. Improved approximation algorithms for the combination problem of parallel machine scheduling and path. J. Comb. Optim. 2019, 38, 689–697.
  33. Behnamian, J. Graph colouring-based algorithm to parallel jobs scheduling on parallel factories. Int. J. Comput. Integr. Manuf. 2015, 29, 622–635.
  34. Zabihzadeh, S.S.; Rezaeian, J. Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time. Appl. Soft Comput. 2016, 40, 319–330.
  35. Mati, Y.; Dauzère-Pérès, S.; Lahlou, C. A general approach for optimizing regular criteria in the job-shop scheduling problem. Eur. J. Oper. Res. 2011, 212, 33–42.
  36. Dabah, A.; Bendjoudi, A.; AitZai, A.; Taboudjemat, N.N. Efficient parallel tabu search for the blocking job shop scheduling problem. Soft Comput. 2019, 23, 13283–13295.
  37. Pranzo, M.; Pacciarelli, D. An iterated greedy metaheuristic for the blocking job shop scheduling problem. J. Heuristics 2015, 22, 587–611.
  38. Lange, J.; Werner, F. Approaches to modeling train scheduling problems as job-shop problems with blocking constraints. J. Sched. 2017, 21, 191–207.
  39. Chaouch, I.; Driss, O.B.; Ghedira, K. A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithm. Appl. Intell. 2019, 49, 1903–1924.
  40. AitZai, A.; Benmedjdoub, B.; Boudhar, M. Branch-and-bound and PSO algorithms for no-wait job shop scheduling. J. Intell. Manuf. 2014, 27, 679–688.
  41. El Khoukhi, F.; Boukachour, J.; Alaoui, A.E.H. The “Dual-Ants Colony”: A novel hybrid approach for the flexible job shop scheduling problem with preventive maintenance. Comput. Ind. Eng. 2017, 106, 236–255.
  42. Xie, J.; Gao, L.; Peng, K.; Li, X.; Li, H. Review on flexible job shop scheduling. IET Collab. Intell. Manuf. 2019, 1, 67–77.
  43. Wu, J.; Wu, G.D.; Wang, J.J. Flexible Job-Shop Scheduling Problem Based on Hybrid ACO Algorithm. Int. J. Simul. Model. 2017, 16, 497–505.
  44. Chen, J.C.; Wu, C.-C.; Chen, C.-W.; Chen, K.-H. Flexible job shop scheduling with parallel machines using Genetic Algorithm and Grouping Genetic Algorithm. Expert Syst. Appl. 2012, 39, 10016–10021.
  45. Brucker, P.; Schlie, R. Job-shop scheduling with multi-purpose machines. Comput. 1990, 45, 369–375.
  46. 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. Ann. Oper. Res. 1997, 70, 281–306.
  47. Zhao, B.; Gao, J.; Chen, K.; Guo, K. Two-generation Pareto ant colony algorithm for multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines. J. Intell. Manuf. 2018, 29, 93–108.
  48. Prakash, A.; Chan, F.T.; Deshmukh, S. FMS scheduling with knowledge based genetic algorithm approach. Expert Syst. Appl. 2011, 38, 3161–3171.
  49. Chan, F.T.S.; Chan, H.K. A comprehensive survey and future trend of simulation study on FMS scheduling. J. Intell. Manuf. 2004, 15, 87–102.
  50. Błażewicz, J.; Ecker, K.H.; Pesch, E.; Schmidt, G.; Węglarz, J. Scheduling in Flexible Manufacturing Systems. In Scheduling Computer and Manufacturing Processes; Springer Science and Business Media LLC: Berlin/Heidelberg, Germany, 1996; pp. 369–421.
  51. Baruwa, O.T.; Piera, M.A. A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles. Int. J. Prod. Res. 2016, 54, 4773–4792.
  52. Gupta, J.N.; Stafford, E.F. Flowshop scheduling research after five decades. Eur. J. Oper. Res. 2006, 169, 699–711.
  53. Ravindran, D.; Selvakumar, S.; Sivaraman, R.; Haq, A.N. Flow shop scheduling with multiple objective of minimizing makespan and total flow time. Int. J. Adv. Manuf. Technol. 2004, 25, 1007–1012.
  54. Belabid, J.; Aqil, S.; Allali, K. Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time. J. Appl. Math. 2020, 2020, 1–11.
  55. Motlagh, M.M.; Azimi, P.; Amiri, M.; Madraki, G. An efficient simulation optimization methodology to solve a multi-objective problem in unreliable unbalanced production lines. Expert Syst. Appl. 2019, 138, 112836.
  56. Dallery, Y.; Gershwin, S. Manufacturing flow line systems: A review of models and analytical results. Queueing Syst. 1992, 12, 3–94.
  57. Lee, C.-Y.; Cheng, T.C.E.; Lin, B.M.T. Minimizing the Makespan in the 3-Machine Assembly-Type Flowshop Scheduling Problem. Manag. Sci. 1993, 39, 616–625.
  58. Wang, S.-Y.; Wang, L. An Estimation of Distribution Algorithm-Based Memetic Algorithm for the Distributed Assembly Permutation Flow-Shop Scheduling Problem. IEEE Trans. Syst. Man Cybern. Syst. 2016, 46, 139–149.
  59. Gmys, J.; Mezmaz, M.; Melab, N.; Tuyttens, D. A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem. Eur. J. Oper. Res. 2020, 284, 814–833.
  60. Qian, B.; Li, Z.-C.; Hu, R. A copula-based hybrid estimation of distribution algorithm for m-machine reentrant permutation flow-shop scheduling problem. Appl. Soft Comput. 2017, 61, 921–934.
  61. Ashrafi, M.; Davoudpour, H.; Abbassi, M. Investigating the efficiency of GRASP for the SDST HFS with controllable processing times and assignable due dates. In Handbook of Research on Novel Soft Computing Intelligent Algorithms: Theory and Practical Applications; IGI Global: Hershey, PA, USA, 2014; pp. 538–567.
  62. Lee, T.-S.; Loong, Y.-T. A review of scheduling problem and resolution methods in flexible flow shop. Int. J. Ind. Eng. Comput. 2019, 10, 67–88.
  63. Dorndorf, U.; Pesch, E. Solving the open shop scheduling problem. J. Sched. 2001, 4, 157–174.
  64. Tellache, N.E.H.; Boudhar, M.; Yalaoui, F. Two-machine open shop problem with agreement graph. Theor. Comput. Sci. 2019, 796, 154–168.
  65. Tellache, N.E.H.; Boudhar, M. Open shop scheduling problems with conflict graphs. Discret. Appl. Math. 2017, 227, 103–120.
  66. Pempera, J.; Smutnicki, C. Open shop cyclic scheduling. Eur. J. Oper. Res. 2018, 269, 773–781.
  67. Shakhlevich, N.V.; Sotskov, Y.N.; Werner, F. Complexity of mixed shop scheduling problems: A survey. Eur. J. Oper. Res. 2000, 120, 343–351.
  68. Wang, M.; Zhong, R.Y.; Dai, Q.; Huang, G.Q. A MPN-based scheduling model for IoT-enabled hybrid flow shop manufacturing. Adv. Eng. Inf. 2016, 30, 728–736.
  69. Pasupuleti, V. Scheduling in Cellular Manufacturing Systems. Iberoam. J. Ind. Eng. 2012, 4, 231–243.
  70. Zeng, C.; Tang, J.; Yan, C. Job-shop cell-scheduling problem with inter-cell moves and automated guided vehicles. J. Intell. Manuf. 2015, 26, 845–859.
  71. Neufeld, J.S.; Gupta, J.N.; Buscher, U. A comprehensive review of flowshop group scheduling literature. Comput. Oper. Res. 2016, 70, 56–74.
  72. Yang, Y.; Chen, Y.; Long, C. Flexible robotic manufacturing cell scheduling problem with multiple robots. Int. J. Prod. Res. 2016, 54, 6768–6781.
  73. Liu, C.; Wang, J.; Leung, J.Y.-T.; Li, K. Solving cell formation and task scheduling in cellular manufacturing system by discrete bacteria foraging algorithm. Int. J. Prod. Res. 2016, 54, 923–944.
  74. Pinedo, M.; Hadavi, K. Scheduling: Theory, Algorithms and Systems Development. In Proceedings of the Operations Research Proceedings 1991; Springer Science and Business Media LLC: Berlin/Heidelberg, Germany, 1992; pp. 35–42.
  75. Chen, B.; Potts, C.N.; Woeginger, G.J. A Review of Machine Scheduling: Complexity, Algorithms and Approximability. Handb. Comb. Optim. 1998, 1493–1641.
  76. Stoop, P.P.; Wiers, V.C. The complexity of scheduling in practice. Int. J. Oper. Prod. Manag. 1996, 16, 37–53.
  77. Lin, L.; Gen, M.; Liang, Y.; Ohno, K. A Hybrid EA for Reactive Flexible Job-shop Scheduling. Procedia Comput. Sci. 2012, 12, 110–115.
  78. Amjad, M.K.; Butt, S.I.; Kousar, R.; Ahmad, R.; Agha, M.H.; Faping, Z.; Anjum, N.; Asgher, U. Recent Research Trends in Genetic Algorithm Based Flexible Job Shop Scheduling Problems. Math. Probl. Eng. 2018, 2018, 1–32.
  79. Mokotoff, E. Parallel machine scheduling problems: A survey. Asia Pacif. J. Oper. Res. 2001, 18, 193.
  80. Martí, R.; Reinelt, G. The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization; Springer Science & Business Media: Berlin/Heidelberg, Germany, 2011; Volume 175.
  81. Kemmoé, S.; Lamy, D.; Tchernev, N. A Job-shop with an Energy Threshold Issue Considering Operations with Consumption Peaks. IFAC PapersOnLine 2015, 48, 788–793.
  82. Sawik, T. Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers. Math. Comput. Model. 2000, 31, 39–52.
  83. Jourdan, L.; Basseur, M.; Talbi, E.-G. Hybridizing exact methods and metaheuristics: A taxonomy. Eur. J. Oper. Res. 2009, 199, 620–629.
  84. Büyüktahtakin, I.E. Dynamic Programming Via Linear Programming. Wiley Encyclop. Oper. Res. Manag. Sci. 2010.
  85. Williamson, D.P.; Shmoys, D.B. The Design of Approximation Algorithms. Design Approxim. Algorith. 2009.
  86. Bianchi, L.; Dorigo, M.; Gambardella, L.M.; Gutjahr, W.J. A survey on metaheuristics for stochastic combinatorial optimization. Nat. Comput. 2009, 8, 239–287.
  87. Framinan, J.M.; Leisten, R.; Ruiz-Usano, R. Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation. Eur. J. Oper. Res. 2002, 141, 559–569.
  88. Lunardi, W.T.; Birgin, E.G.; Ronconi, D.P.; Voos, H. Metaheuristics for the online printing shop scheduling problem. Eur. J. Oper. Res. 2020.
  89. Afsar, H.; Lacomme, P.; Ren, L.; Prodhon, C.; Vigo, D. Resolution of a Job-Shop problem with transportation constraints: A master/slave approach. IFAC PapersOnLine 2016, 49, 898–903.
  90. Mencía, R.; Sierra, M.R.; Mencía, C.; Varela, R. Memetic algorithms for the job shop scheduling problem with operators. Appl. Soft Comput. 2015, 34, 94–105.
  91. Shi, F.; Zhao, S.; Meng, Y. Hybrid algorithm based on improved extended shifting bottleneck procedure and GA for assembly job shop scheduling problem. Int. J. Prod. Res. 2020, 58, 2604–2625.
  92. Choo, W.M.; Wong, L.-P.; Khader, A.T. A modified bee colony optimization with local search approach for job shop scheduling problems relevant to bottleneck machines. Int. J. Adv. Soft Comput. Appl. 2016, 8, 52–78.
  93. Abdel-Kader, R.F. An improved PSO algorithm with genetic and neighborhood-based diversity operators for the job shop scheduling problem. Appl. Artif. Intell. 2018, 32, 433–462.
  94. Nasiri, M.M. A modified ABC algorithm for the stage shop scheduling problem. Appl. Soft Comput. 2015, 28, 81–89.
  95. Bahalkeh, E.; Madraki, G.; Judd, R. Efficient system matrix calculation for manufacturing systems. In Proceedings of the IIE Annual Conference, Nashville, TN, USA, 30 May–2 June 2015; Institute of Industrial and Systems Engineers (IISE): Norcross, GA, USA, 2015.
  96. Weise, J.; Benkhardt, S.; Mostaghim, S. A Survey on Graph-based Systems in Manufacturing Processes. In Proceedings of the 2018 IEEE Symposium Series on Computational Intelligence (SSCI), Bangalore, India, 18–21 November 2018; Institute of Electrical and Electronics Engineers (IEEE): Piscataway, NJ, USA, 2018; pp. 112–119.
  97. Sotskov, Y.N. Mixed Graph Colorings: A Historical Review. Mathematics 2020, 8, 385.
  98. Moon, J.W.; Moser, L. On cliques in graphs. Isr. J. Math. 1965, 3, 23–28.
  99. Prosser, P. Exact Algorithms for Maximum Clique: A Computational Study. Algorithms 2012, 5, 545–587.
  100. Mohabeddine, A.; Boudhar, M. New results in two identical machines scheduling with agreement graphs. Theor. Comput. Sci. 2019, 779, 37–46.
  101. Even, G.; Halldórsson, M.M.; Kaplan, L.; Ron, D. Scheduling with conflicts: Online and offline algorithms. J. Sched. 2008, 12, 199–224.
  102. Halldórsson, M.M.; Kortsarz, G. Multicoloring: Problems and Techniques. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science, Prague, Czech Republic, 22–27 August 2004; Springer: Berlin/Heidelberg, Germany, 2004; Volume 3153, pp. 25–41.
  103. Furmańczyk, H.; Kubale, M. Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines. Discret. Appl. Math. 2018, 234, 210–217.
  104. Thevenin, S.; Zufferey, N.; Potvin, J.-Y. Graph multi-coloring for a job scheduling application. Discret. Appl. Math. 2018, 234, 218–235.
  105. Furmańczyk, H.; Kubale, M. The complexity of equitable vertex coloring of graphs. J. Appl. Comput. Sci. 2005, 13, 95–106.
  106. Ganguli, R.; Roy, S. A study on course timetable scheduling using graph coloring approach. Int. J. Comput. Appl. Math. 2017, 12, 469–485.
  107. Reddy, M.S.; Ratnam, C.; Agrawal, R.; Varela, M.; Sharma, I.; Manupati, V. Investigation of reconfiguration effect on makespan with social network method for flexible job shop scheduling problem. Comput. Ind. Eng. 2017, 110, 231–241.
  108. Bendraouche, M.; Boudhar, M. Scheduling with agreements: New results. Int. J. Prod. Res. 2015, 54, 1–15.
  109. Bendraouche, M.; Boudhar, M.; Oulamara, A. Scheduling: Agreement graph vs resource constraints. Eur. J. Oper. Res. 2015, 240, 355–360.
  110. Sun, L.; Lin, L.; Li, H.; Gen, M. Cooperative Co-Evolution Algorithm with an MRF-Based Decomposition Strategy for Stochastic Flexible Job Shop Scheduling. Mathematics 2019, 7, 318.
  111. Rosenkrantz, D.J.; Stearns, R.E.; Lewis, P.M. Approximate algorithms for the traveling salesperson problem. 15th Ann. Sympos. Switch. Automata Theory 1974.
  112. Bożejko, W.; Uchroński, M.; Wodecki, M. Block approach to the cyclic flow shop scheduling. Comput. Ind. Eng. 2015, 81, 158–166.
  113. Bożejko, W.; Gnatowski, A.; Pempera, J.; Wodecki, M. Parallel tabu search for the cyclic job shop scheduling problem. Comput. Ind. Eng. 2017, 113, 512–524.
  114. Madraki, G.; Judd, R. Accelerating the calculation of makespan used in scheduling improvement heuristics. Comput. Oper. Res. 2021, 130, 105233.
  115. González, M.A.; Vela, M.D.C.R.; Varela, R. Scatter search with path relinking for the flexible job shop scheduling problem. Eur. J. Oper. Res. 2015, 245, 35–45.
  116. Kahn, A.B. Topological sorting of large networks. Commun. ACM 1962, 5, 558–562.
  117. Selvakumar, S.; Murthy, C.S.R. Scheduling precedence constrained task graphs with non-negligible intertask communication onto multiprocessors. IEEE Trans. Parallel Distrib. Syst. 1994, 5, 328–336.
  118. Katriel, I.; Michel, L.; Van Hentenryck, P. Maintaining Longest Paths Incrementally. Constraints 2005, 10, 159–183.
  119. Chen, Y.; Goebel, R.; Lin, G.; Su, B.; Zhang, A. Open-shop scheduling for unit jobs under precedence constraints. Theor. Comput. Sci. 2020, 803, 144–151.
  120. Birgin, E.; Ferreira, J.; Ronconi, D. List scheduling and beam search methods for the flexible job shop scheduling problem with sequencing flexibility. Eur. J. Oper. Res. 2015, 247, 421–440.
  121. Lunardi, W.T.; Birgin, E.G.; Laborie, P.; Ronconi, D.P.; Voos, H. Mixed Integer linear programming and constraint programming models for the online printing shop scheduling problem. Comput. Oper. Res. 2020, 123, 105020.
  122. Tellache, N.E.H.; Boudhar, M. Flow shop scheduling problem with conflict graphs. Ann. Oper. Res. 2017, 261, 339–363.
  123. Leake, C.; Baccelli, F.; Cohen, G.; Olsder, G.J.; Quadrat, J.-P. Synchronization and Linearity: An Algebra for Discrete Event Systems. J. Oper. Res. Soc. 1994, 45, 118.
  124. Lee, T.-E.; Park, S.-H. An Extended Event Graph With Negative Places and Tokens for Time Window Constraints. IEEE Trans. Autom. Sci. Eng. 2005, 2, 319–332.
  125. Cohen, G.; Gaubert, S.; Quadrat, J.-P. Max-plus algebra and system theory: Where we are and where to go now. Annu. Rev. Control. 1999, 23, 207–219.
  126. Zhou, M.; Venkatesh, K. Modeling, Simulation, and Control. of Flexible Manufacturing Systems; World Scientific Pub Co Pte Lt: Singapore, 1999.
  127. Zhou, M.; Dicesare, F.; DesRochers, A. A hybrid methodology for synthesis of Petri net models for manufacturing systems. IEEE Trans. Robot. Autom. 1992, 8, 350–361.
  128. Lusby, R.M.; Larsen, J.; Ehrgott, M.; Ryan, D. Railway track allocation: Models and methods. OR Spectr. 2011, 33, 843–883.
  129. Dabah, A.; Bendjoudi, A.; AitZai, A.; El-Baz, D.; Taboudjemat, N.N. Hybrid multi-core CPU and GPU-based B&B approaches for the blocking job shop scheduling problem. J. Parallel Distrib. Comput. 2018, 117, 73–86.
  130. Gholami, O.; Krasemann, J.T. A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time. Algorithms 2018, 11, 55.
  131. Corominas, A.; García-Villoria, A.; González, N.-A.; Pastor, R. A multistage graph-based procedure for solving a just-in-time flexible job-shop scheduling problem with machine and time-dependent processing costs. J. Oper. Res. Soc. 2018, 70, 620–633.
  132. Wang, S.; Liu, M.; Chu, C. A branch-and-bound algorithm for two-stage no-wait hybrid flow-shop scheduling. Int. J. Prod. Res. 2014, 53, 1143–1167.
  133. Nip, K.; Wang, Z.; Nobibon, F.T.; Leus, R. A combination of flow shop scheduling and the shortest path problem. J. Combin. Optim. 2015, 29, 36–52.
  134. Bierwirth, C.; Kuhpfahl, J. Extended GRASP for the job shop scheduling problem with total weighted tardiness objective. Eur. J. Oper. Res. 2017, 261, 835–848.
  135. Kim, H.-J.; Lee, J.-H. Three-machine flow shop scheduling with overlapping waiting time constraints. Comput. Oper. Res. 2019, 101, 93–102.
  136. Zhang, F.; Mei, Y.; Nguyen, S.; Zhang, M. Evolving Scheduling Heuristics via Genetic Programming With Feature Selection in Dynamic Flexible Job-Shop Scheduling. IEEE Trans. Cybern. 2021, 51, 1797–1811.
  137. Zhou, Y.; Yang, J.-J.; Zheng, L.-Y. Hyper-Heuristic Coevolution of Machine Assignment and Job Sequencing Rules for Multi-Objective Dynamic Flexible Job Shop Scheduling. IEEE Access 2018, 7, 68–88.
  138. Hart, E.; Sim, K. A hyper-heuristic ensemble method for static job-shop scheduling. Evolut. Comput. 2016, 24, 609–635.
  139. Zhang, S.; Wang, S. Flexible Assembly Job-Shop Scheduling With Sequence-Dependent Setup Times and Part Sharing in a Dynamic Environment: Constraint Programming Model, Mixed-Integer Programming Model, and Dispatching Rules. IEEE Trans. Eng. Manag. 2018, 65, 487–504.
  140. Rossi, A.; Lanzetta, M. Integration of hybrid additive/subtractive manufacturing planning and scheduling by metaheuristics. Comput. Ind. Eng. 2020, 144, 106428.
  141. Liu, Q.; Li, X.; Gao, L.; Li, Y. A Modified Genetic Algorithm With New Encoding and Decoding Methods for Integrated Process Planning and Scheduling Problem. IEEE Trans. Cybern. 2020, 1–10.
  142. Zhang, S.; Wong, T.N. Flexible job-shop scheduling/rescheduling in dynamic environment: A hybrid MAS/ACO approach. Int. J. Prod. Res. 2016, 55, 3173–3196.
  143. Zhang, Y.; Wang, J.; Liu, Y. Game theory based real-time multi-objective flexible job shop scheduling considering environmental impact. J. Clean. Prod. 2017, 167, 665–679.
  144. Rivest, R.L. Game tree searching by min/max approximation. Artif. Intell. 1987, 34, 77–96.
  145. Lei, Q.; Guo, W.; Song, Y. Integrated scheduling algorithm based on an operation relationship matrix table for tree-structured products. Int. J. Prod. Res. 2018, 56, 5437–5456.
  146. Zhu, Z.; Zhou, X.; Shao, K. A novel approach based on Neo4j for multi-constrained flexible job shop scheduling problem. Comput. Ind. Eng. 2019, 130, 671–686.
  147. Grimes, D.; Hebrard, E. Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search. INFORMS J. Comput. 2015, 27, 268–284.
  148. Wang, L.; Cai, J.; Li, M.; Liu, Z. Flexible Job Shop Scheduling Problem Using an Improved Ant Colony Optimization. Sci. Program. 2017, 2017, 1–11.
  149. Qin, W.; Zhuang, Z.; Liu, Y.; Tang, O. A two-stage ant colony algorithm for hybrid flow shop scheduling with lot sizing and calendar constraints in printed circuit board assembly. Comput. Ind. Eng. 2019, 138, 106115.
  150. Ciro, G.C.; Dugardin, F.; Yalaoui, F.; Kelly, R. Open shop scheduling problem with a multi-skills resource constraint: A genetic algorithm and an ant colony optimisation approach. Int. J. Prod. Res. 2015, 54, 4854–4881.
  151. Riahi, V.; Kazemi, M. A new hybrid ant colony algorithm for scheduling of no-wait flowshop. Oper. Res. 2016, 18, 55–74.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/)
Video Production Service
Feedback