Skip to main content
Top
Published in: Journal of Scheduling 2/2021

19-08-2020

Multiple dispatching rules allocation in real time using data mining, genetic algorithms, and simulation

Authors: Mohamed Habib Zahmani, Baghdad Atmani

Published in: Journal of Scheduling | Issue 2/2021

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In production planning and scheduling, data mining methods can be applied to transform the scheduling data into useful knowledge that can be used to improve planning/scheduling by enabling real-time decision-making. In this paper, a novel approach combining dispatching rules, a genetic algorithm, data mining, and simulation is proposed. The genetic algorithm (i) is used to solve scheduling problems, and the obtained solutions (ii) are analyzed in order to extract knowledge, which is then used (iii) to automatically assign in real-time different dispatching rules to machines based on the jobs in their respective queues. The experiments are conducted on a job shop scheduling problem with a makespan criterion. The obtained results from the computational study show that the proposed approach is a viable and effective approach for solving the job shop scheduling problem in real time.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Literature
go back to reference Baykasoğlu, A., Göçken, M., Özbakır, L., & Kulluk, S. (2008). Composite dispatching rule generation through data mining in a simulated job shop. Modelling, computation and optimization in information systems and management sciences (pp. 389–398). New York: Springer. Baykasoğlu, A., Göçken, M., Özbakır, L., & Kulluk, S. (2008). Composite dispatching rule generation through data mining in a simulated job shop. Modelling, computation and optimization in information systems and management sciences (pp. 389–398). New York: Springer.
go back to reference Beasley, J. E. (1990). Or-library: Distributing test problems by electronic mail. The Journal of the Operational Research Society, 41(11), 1069. Beasley, J. E. (1990). Or-library: Distributing test problems by electronic mail. The Journal of the Operational Research Society, 41(11), 1069.
go back to reference Bülbül, K., & Kaminsky, P. (2013). A linear programming-based method for job shop scheduling. Journal of Scheduling, 16(2), 161–183. Bülbül, K., & Kaminsky, P. (2013). A linear programming-based method for job shop scheduling. Journal of Scheduling, 16(2), 161–183.
go back to reference Çaliş, B., & Bulkan, S. (2015). A research survey: Review of ai solution strategies of job shop scheduling problem. Journal of Intelligent Manufacturing, 26(5), 961–973. Çaliş, B., & Bulkan, S. (2015). A research survey: Review of ai solution strategies of job shop scheduling problem. Journal of Intelligent Manufacturing, 26(5), 961–973.
go back to reference Cao, Y., & Shi, H. (2015). A hybrid ant colony optimisation algorithm for job shop problems and its convergence analysis. International Journal of Modelling, Identification and Control, 23(3), 230–237. Cao, Y., & Shi, H. (2015). A hybrid ant colony optimisation algorithm for job shop problems and its convergence analysis. International Journal of Modelling, Identification and Control, 23(3), 230–237.
go back to reference Chaudhry, I. A., & Khan, A. A. (2016). A research survey: Review of flexible job shop scheduling techniques. International Transactions in Operational Research, 23(3), 551–591. Chaudhry, I. A., & Khan, A. A. (2016). A research survey: Review of flexible job shop scheduling techniques. International Transactions in Operational Research, 23(3), 551–591.
go back to reference Chen, B., & Matis, T. I. (2013). A flexible dispatching rule for minimizing tardiness in job shop scheduling. International Journal of Production Economics, 141(1), 360–365. Chen, B., & Matis, T. I. (2013). A flexible dispatching rule for minimizing tardiness in job shop scheduling. International Journal of Production Economics, 141(1), 360–365.
go back to reference Cheng, T., Peng, B., & Lü, Z. (2016). A hybrid evolutionary algorithm to solve the job shop scheduling problem. Annals of Operations Research, 242(2), 223–237. Cheng, T., Peng, B., & Lü, Z. (2016). A hybrid evolutionary algorithm to solve the job shop scheduling problem. Annals of Operations Research, 242(2), 223–237.
go back to reference Chiang, P. H., & Torng, C. C. (2016). A production planning and optimisation of multi-mode job shop scheduling problem for an avionics manufacturing plant. International Journal of Manufacturing Technology and Management, 30(3–4), 179–195. Chiang, P. H., & Torng, C. C. (2016). A production planning and optimisation of multi-mode job shop scheduling problem for an avionics manufacturing plant. International Journal of Manufacturing Technology and Management, 30(3–4), 179–195.
go back to reference da Silva, E. B., Costa, M. G., da Silva, M Fd S, & Pereira, F. H. (2014). Simulation study of dispatching rules in stochastic job shop dynamic scheduling. World Journal of Modelling and Simulation, 10(3), 231–240. da Silva, E. B., Costa, M. G., da Silva, M Fd S, & Pereira, F. H. (2014). Simulation study of dispatching rules in stochastic job shop dynamic scheduling. World Journal of Modelling and Simulation, 10(3), 231–240.
go back to reference Demirkol, E., Sanjay, M., & Reha, U. (1998). Benchmarks for shop scheduling problems. European Journal of Operational Research, 109(1), 137–141. Demirkol, E., Sanjay, M., & Reha, U. (1998). Benchmarks for shop scheduling problems. European Journal of Operational Research, 109(1), 137–141.
go back to reference Geiger, C. D., Uzsoy, R., & Aytuğ, H. (2006). Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. Journal of Scheduling, 9(1), 7–34. Geiger, C. D., Uzsoy, R., & Aytuğ, H. (2006). Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. Journal of Scheduling, 9(1), 7–34.
go back to reference Habib Zahmani, M., & Atmani, B. (2018). Extraction of dispatching rules for single machine total weighted tardiness using a modified genetic algorithm and data mining. International Journal of Manufacturing Research, 13(1), 1–25. Habib Zahmani, M., & Atmani, B. (2018). Extraction of dispatching rules for single machine total weighted tardiness using a modified genetic algorithm and data mining. International Journal of Manufacturing Research, 13(1), 1–25.
go back to reference Habib Zahmani, M., Atmani, B., Bekrar, A., & Aissani, N. (2015a). Multiple priority dispatching rules for the job shop scheduling problem. In: 2015 3rd International Conference on Control, Engineering and Information Technology (CEIT), IEEE, (pp. 1–6) Habib Zahmani, M., Atmani, B., Bekrar, A., & Aissani, N. (2015a). Multiple priority dispatching rules for the job shop scheduling problem. In: 2015 3rd International Conference on Control, Engineering and Information Technology (CEIT), IEEE, (pp. 1–6)
go back to reference Habib Zahmani, M., Atmani, B., Bekrar, A., & Aissani, N. (2015b). A real time data mining rules selection model for the job shop scheduling problem. In 45th international conference on computers and industrial engineering 2015 (CIE45) (pp. 465–472) Habib Zahmani, M., Atmani, B., Bekrar, A., & Aissani, N. (2015b). A real time data mining rules selection model for the job shop scheduling problem. In 45th international conference on computers and industrial engineering 2015 (CIE45) (pp. 465–472)
go back to reference Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., & Witten, I. H. (2009). The weka data mining software: An update. ACM SIGKDD Explorations Newsletter, 11(1), 10–18. Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., & Witten, I. H. (2009). The weka data mining software: An update. ACM SIGKDD Explorations Newsletter, 11(1), 10–18.
go back to reference Hasan, S. K., Sarker, R., & Essam, D. (2010). Evolutionary scheduling with rescheduling option for sudden machine breakdowns. In: IEEE congress on evolutionary computation (CEC) IEEE (pp. 1–8). Hasan, S. K., Sarker, R., & Essam, D. (2010). Evolutionary scheduling with rescheduling option for sudden machine breakdowns. In: IEEE congress on evolutionary computation (CEC) IEEE (pp. 1–8).
go back to reference Hasan, S. K., Sarker, R., & Essam, D. (2011). Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns. International Journal of Production Research, 49(16), 4999–5015. Hasan, S. K., Sarker, R., & Essam, D. (2011). Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns. International Journal of Production Research, 49(16), 4999–5015.
go back to reference Holland, J. (1975). Adaption in natural and artificial systems. Ann Arbor, MI: The University of Michigan Press. Holland, J. (1975). Adaption in natural and artificial systems. Ann Arbor, MI: The University of Michigan Press.
go back to reference Kaban, A., Othman, Z., & Rohmah, D. (2012). Comparison of dispatching rules in job-shop scheduling problem using simulation: A case study. International Journal of Simulation Modelling, 11(3), 129–140. Kaban, A., Othman, Z., & Rohmah, D. (2012). Comparison of dispatching rules in job-shop scheduling problem using simulation: A case study. International Journal of Simulation Modelling, 11(3), 129–140.
go back to reference Kacem, I. (2003). Genetic algorithm for the flexible job-shop scheduling problem. In IEEE international conference on systems, man and cybernetics, 2003, IEEE, vol 4, pp. 3464–3469 Kacem, I. (2003). Genetic algorithm for the flexible job-shop scheduling problem. In IEEE international conference on systems, man and cybernetics, 2003, IEEE, vol 4, pp. 3464–3469
go back to reference Kaplanoğlu, V. (2016). An object-oriented approach for multi-objective flexible job-shop scheduling problem. Expert Systems with Applications, 45, 71–84. Kaplanoğlu, V. (2016). An object-oriented approach for multi-objective flexible job-shop scheduling problem. Expert Systems with Applications, 45, 71–84.
go back to reference Karthikeyan, S., Asokan, P., Nickolas, S., & Page, T. (2012). Solving flexible job-shop scheduling problem using hybrid particle swarm optimisation algorithm and data mining. International Journal of Manufacturing Technology and Management, 26(1–4), 81–103. Karthikeyan, S., Asokan, P., Nickolas, S., & Page, T. (2012). Solving flexible job-shop scheduling problem using hybrid particle swarm optimisation algorithm and data mining. International Journal of Manufacturing Technology and Management, 26(1–4), 81–103.
go back to reference Koonce, D., & Tsai, S. C. (2000). Using data mining to find patterns in genetic algorithm solutions to a job shop schedule. Computers & Industrial Engineering, 38(3), 361–374. Koonce, D., & Tsai, S. C. (2000). Using data mining to find patterns in genetic algorithm solutions to a job shop schedule. Computers & Industrial Engineering, 38(3), 361–374.
go back to reference Korytkowski, P., Wiśniewski, T., & Rymaszewski, S. (2013). An evolutionary simulation-based optimization approach for dispatching scheduling. Simulation Modelling Practice and Theory, 35, 69–85. Korytkowski, P., Wiśniewski, T., & Rymaszewski, S. (2013). An evolutionary simulation-based optimization approach for dispatching scheduling. Simulation Modelling Practice and Theory, 35, 69–85.
go back to reference Kuczapski, A. M., Micea, M. V., Maniu, L. A., & Cretu, V. I. (2010). Efficient generation of near optimal initial populations to enhance genetic algorithms for job-shop scheduling. Information Technology and Control, 39(1), 32–37. Kuczapski, A. M., Micea, M. V., Maniu, L. A., & Cretu, V. I. (2010). Efficient generation of near optimal initial populations to enhance genetic algorithms for job-shop scheduling. Information Technology and Control, 39(1), 32–37.
go back to reference Kundakcı, N., & Kulak, O. (2016). Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem. Computers & Industrial Engineering, 96, 31–51. Kundakcı, N., & Kulak, O. (2016). Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem. Computers & Industrial Engineering, 96, 31–51.
go back to reference Kurdi, M. (2015). A new hybrid island model genetic algorithm for job shop scheduling problem. Computers & Industrial Engineering, 88, 273–283. Kurdi, M. (2015). A new hybrid island model genetic algorithm for job shop scheduling problem. Computers & Industrial Engineering, 88, 273–283.
go back to reference Li, X., & Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 174, 93–110. Li, X., & Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 174, 93–110.
go back to reference Li, X., & Olafsson, S. (2005). Discovering dispatching rules using data mining. Journal of Scheduling, 8(6), 515–527. Li, X., & Olafsson, S. (2005). Discovering dispatching rules using data mining. Journal of Scheduling, 8(6), 515–527.
go back to reference Lu, H., Huang, G. Q., & Yang, H. (2011). Integrating order review/release and dispatching rules for assembly job shop scheduling using a simulation approach. International Journal of Production Research, 49(3), 647–669. Lu, H., Huang, G. Q., & Yang, H. (2011). Integrating order review/release and dispatching rules for assembly job shop scheduling using a simulation approach. International Journal of Production Research, 49(3), 647–669.
go back to reference Metan, G., Sabuncuoglu, I., & Pierreval, H. (2010). Real time selection of scheduling rules and knowledge extraction via dynamically controlled data mining. International Journal of Production Research, 48(23), 6909–6938. Metan, G., Sabuncuoglu, I., & Pierreval, H. (2010). Real time selection of scheduling rules and knowledge extraction via dynamically controlled data mining. International Journal of Production Research, 48(23), 6909–6938.
go back to reference Natarajan, K., Mohanasundaram, K., Babu, B. S., Suresh, S., Raj, K. A. A. D., & Rajendran, C. (2007). Performance evaluation of priority dispatching rules in multi-level assembly job shops with jobs having weights for flowtime and tardiness. The International Journal of Advanced Manufacturing Technology, 31(7–8), 751–761. Natarajan, K., Mohanasundaram, K., Babu, B. S., Suresh, S., Raj, K. A. A. D., & Rajendran, C. (2007). Performance evaluation of priority dispatching rules in multi-level assembly job shops with jobs having weights for flowtime and tardiness. The International Journal of Advanced Manufacturing Technology, 31(7–8), 751–761.
go back to reference Nguyen, S., Zhang, M., Johnston, M., & Tan, K. C. (2013a). A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem. IEEE Transactions on Evolutionary Computation, 17(5), 621–639. Nguyen, S., Zhang, M., Johnston, M., & Tan, K. C. (2013a). A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem. IEEE Transactions on Evolutionary Computation, 17(5), 621–639.
go back to reference Nguyen, S., Zhang, M., Johnston, M., & Tan, K. C. (2013b). Learning iterative dispatching rules for job shop scheduling with genetic programming. The International Journal of Advanced Manufacturing Technology, 67(1–4), 85–100. Nguyen, S., Zhang, M., Johnston, M., & Tan, K. C. (2013b). Learning iterative dispatching rules for job shop scheduling with genetic programming. The International Journal of Advanced Manufacturing Technology, 67(1–4), 85–100.
go back to reference Ning, L., Abdelrahman, M., & Ramaswamy, S. (2005). A genetic algorithm for single machine total weighted tardiness scheduling problem. International Journal of Intelligent Control and Systems, 10(3), 218–225. Ning, L., Abdelrahman, M., & Ramaswamy, S. (2005). A genetic algorithm for single machine total weighted tardiness scheduling problem. International Journal of Intelligent Control and Systems, 10(3), 218–225.
go back to reference Olafsson, S., & Li, X. (2010). Learning effective new single machine dispatching rules from optimal scheduling data. International Journal of Production Economics, 128(1), 118–126. Olafsson, S., & Li, X. (2010). Learning effective new single machine dispatching rules from optimal scheduling data. International Journal of Production Economics, 128(1), 118–126.
go back to reference Pierreval, H., & Mebarki, N. (1997). Dynamic scheduling selection of dispatching rules for manufacturing system. International Journal of Production Research, 35(6), 1575–1591. Pierreval, H., & Mebarki, N. (1997). Dynamic scheduling selection of dispatching rules for manufacturing system. International Journal of Production Research, 35(6), 1575–1591.
go back to reference Potts, C. N., & Van Wassenhove, L. N. (1985). A branch and bound algorithm for the total weighted tardiness problem. Operations Research, 33(2), 363–377. Potts, C. N., & Van Wassenhove, L. N. (1985). A branch and bound algorithm for the total weighted tardiness problem. Operations Research, 33(2), 363–377.
go back to reference Qiao, F., Li, L., Ma, Y., & Shi, B. (2012). Single machine oriented match-up rescheduling method for semiconductor manufacturing system. In International Conference on Intelligent Robotics and Applications (pp. 217–226). Berlin: Springer Qiao, F., Li, L., Ma, Y., & Shi, B. (2012). Single machine oriented match-up rescheduling method for semiconductor manufacturing system. In International Conference on Intelligent Robotics and Applications (pp. 217–226). Berlin: Springer
go back to reference Raghu, T., & Rajendran, C. (1993). An efficient dynamic dispatching rule for scheduling in a job shop. International Journal of Production Economics, 32(3), 301–313. Raghu, T., & Rajendran, C. (1993). An efficient dynamic dispatching rule for scheduling in a job shop. International Journal of Production Economics, 32(3), 301–313.
go back to reference Ritwik, K., & Deb, S. (2011). A genetic algorithm-based approach for optimization of scheduling in job shop environment. Journal of Advanced Manufacturing Systems, 10(02), 223–240. Ritwik, K., & Deb, S. (2011). A genetic algorithm-based approach for optimization of scheduling in job shop environment. Journal of Advanced Manufacturing Systems, 10(02), 223–240.
go back to reference Said, N., Mouelhi, W., & Ghedira, K. (2015). Classification rules for the job shop scheduling problem with machine breakdowns. International Journal of Information and Electronics Engineering, 5(4), 300. Said, N., Mouelhi, W., & Ghedira, K. (2015). Classification rules for the job shop scheduling problem with machine breakdowns. International Journal of Information and Electronics Engineering, 5(4), 300.
go back to reference Shahzad, A., & Mebarki, N. (2012). Data mining based job dispatching using hybrid simulation-optimization approach for shop scheduling problem. Engineering Applications of Artificial Intelligence, 25(6), 1173–1181. Shahzad, A., & Mebarki, N. (2012). Data mining based job dispatching using hybrid simulation-optimization approach for shop scheduling problem. Engineering Applications of Artificial Intelligence, 25(6), 1173–1181.
go back to reference Shahzad, A., & Mebarki, N. (2016). Learning dispatching rules for scheduling: A synergistic view comprising decision trees, tabu search and simulation. Computers, 5(1), 3. Shahzad, A., & Mebarki, N. (2016). Learning dispatching rules for scheduling: A synergistic view comprising decision trees, tabu search and simulation. Computers, 5(1), 3.
go back to reference Sharma, P., & Jain, A. (2015). Performance analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times: Simulation approach. CIRP Journal of Manufacturing Science and Technology, 10, 110–119. Sharma, P., & Jain, A. (2015). Performance analysis of dispatching rules in a stochastic dynamic job shop manufacturing system with sequence-dependent setup times: Simulation approach. CIRP Journal of Manufacturing Science and Technology, 10, 110–119.
go back to reference Trentesaux, D., Pach, C., Bekrar, A., Sallez, Y., Berger, T., Bonte, T., et al. (2013). Benchmarking flexible job-shop scheduling and control systems. Control Engineering Practice, 21(9), 1204–1225. Trentesaux, D., Pach, C., Bekrar, A., Sallez, Y., Berger, T., Bonte, T., et al. (2013). Benchmarking flexible job-shop scheduling and control systems. Control Engineering Practice, 21(9), 1204–1225.
go back to reference Wang, J. F., Du, B. Q., Ding, H. M. (2011). A genetic algorithm for the flexible job-shop scheduling problem. In Advanced Research on Computer Science and Information Engineering, Berlin: Springer (pp. 332–339). Wang, J. F., Du, B. Q., Ding, H. M. (2011). A genetic algorithm for the flexible job-shop scheduling problem. In Advanced Research on Computer Science and Information Engineering, Berlin: Springer (pp. 332–339).
go back to reference Wang, L., & Zheng, D. Z. (2001). An effective hybrid optimization strategy for job-shop scheduling problems. Computers & Operations Research, 28(6), 585–596. Wang, L., & Zheng, D. Z. (2001). An effective hybrid optimization strategy for job-shop scheduling problems. Computers & Operations Research, 28(6), 585–596.
go back to reference Wilensky, U. (1999). Center for connected learning and computer-based modeling. Evanston, IL: NetLogo. Wilensky, U. (1999). Center for connected learning and computer-based modeling. Evanston, IL: NetLogo.
go back to reference Yazdani, M., Aleti, A., Khalili, S. M., & Jolai, F. (2017). Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem. Computers & Industrial Engineering, 107, 12–24. Yazdani, M., Aleti, A., Khalili, S. M., & Jolai, F. (2017). Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem. Computers & Industrial Engineering, 107, 12–24.
Metadata
Title
Multiple dispatching rules allocation in real time using data mining, genetic algorithms, and simulation
Authors
Mohamed Habib Zahmani
Baghdad Atmani
Publication date
19-08-2020
Publisher
Springer US
Published in
Journal of Scheduling / Issue 2/2021
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI
https://doi.org/10.1007/s10951-020-00664-5

Other articles of this Issue 2/2021

Journal of Scheduling 2/2021 Go to the issue