Flexible Job Scheduling under Consideration of Time and Energy Consumption Using Enhanced Iterative Deferred Acceptance Algorithm

Document Type : Research Paper

Author

Assistant Professor, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran.

Abstract

This paper highlights the shift in the industrial sector towards a decentralized structure, focusing the importance of energy efficiency for manufacturers and the need for quick job completion to satisfy customers. The study proposes a matching game approach using the Job Scheduling Problem (JSP) to address both manufacturer and customer concerns. It introduces the Deferred Acceptance (DA) algorithm to create stable and optimal matches between machines and operations, incorporating the W-value concept to represent willingness values between partners. The Enhanced Iterative DA (EIDA) algorithm, enhanced with the W-value, shows improved job completion time, reduced energy consumption, and faster runtime compared to the Genetic Algorithm. Through experiments, our enhanced iterative DA (EIDA) algorithm results in an average 6.40% increase in job completion time and a 16.60% reduction in manufacturers' energy consumption compared to the Genetic Algorithm. Moreover, utilizing the W-value leads to a 19.03% average runtime improvement. 

Keywords

Main Subjects

References

Abdulkadiroğlu, A., Pathak, P. A., & Roth, A. E. (2009). Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match. American Economic Review, 99(5), 1954-1978. https://doi.org/https://www.doi.org/10.1257/aer.99.5.1954
Abdulkadiroğlu, A., & Sönmez, T. (2003). School Choice: A Mechanism Design Approach. American Economic Review, 93(3), 729-747. https://doi.org/http://doi.org/10.1257/000282803322157061
Ahmadian, M. M., Khatami, M., Salehipour, A., & Cheng, T. C. E. (2021). Four decades of research on the open-shop scheduling problem to minimize the makespan. European Journal of Operational Research. https://doi.org/https://doi.org/10.1016/j.ejor.2021.03.026
Armendariz-Lopez, J. F., Arena-Granados, A. P., Gonzalez-Trevizo, M. E., Luna-Leon, A., & Bojorquez-Morales, G. (2018). Energy payback time and Greenhouse Gas emissions: Studying the international energy agency guidelines architecture. Journal of Cleaner Production, 196, 1566-1575. https://doi.org/https://doi.org/10.1016/j.jclepro.2018.06.134
Bando, K. (2014a). A modified deferred acceptance algorithm for many-to-one matching markets with externalities among firms. Journal of Mathematical Economics, 52, 173-181. https://doi.org/https://doi.org/10.1016/j.jmateco.2014.01.001
Bando, K. (2014b). On the existence of a strictly strong Nash equilibrium under the student-optimal deferred acceptance algorithm. Games and Economic Behavior, 87, 269-287. https://doi.org/https://doi.org/10.1016/j.geb.2014.05.009
Baykasoğlu, A., Madenoğlu, F. S., & Hamzadayı, A. (2020). Greedy randomized adaptive search for dynamic flexible job-shop scheduling. Journal of Manufacturing Systems, 56, 425-451. https://doi.org/https://doi.org/10.1016/j.jmsy.2020.06.005
Berterottière, L., Dauzère-Pérès, S., & Yugma, C. (2024). Flexible job-shop scheduling with transportation resources. European Journal of Operational Research, 312(3), 890-909. https://doi.org/https://doi.org/10.1016/j.ejor.2023.07.036
Bie, Z., Xie, H., Hu, G., & Li, G. (2016). Optimal scheduling of power systems considering demand response. Journal of Modern Power Systems and Clean Energy, 4(2), 180-187. https://doi.org/https://doi.org/10.1007/s40565-015-0136-9
Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3), 157-183. https://doi.org/10.1007/BF02023073
Bruni, M. E., Khodaparasti, S., & Demeulemeester, E. (2020). The distributionally robust machine scheduling problem with job selection and sequence-dependent setup times. Computers & Operations Research, 123, 105017. https://doi.org/https://doi.org/10.1016/j.cor.2020.105017
Bürgy, R. (2017). A neighborhood for complex job shop scheduling problems with regular objectives. Journal of Scheduling, 20(4), 391-422. https://doi.org/https://doi.org/10.1007/s10951-017-0532-2
Cai, W., Liu, F., Zhou, X., & Xie, J. (2016). Fine energy consumption allowance of workpieces in the mechanical manufacturing industry. Energy, 114, 623-633. https://doi.org/https://doi.org/10.1016/j.energy.2016.08.028
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. https://doi.org/https://doi.org/10.1111/itor.12199
Chou, Y.-L., Yang, J.-M., & Wu, C.-H. (2020). An energy-aware scheduling algorithm under maximum power consumption constraints. Journal of Manufacturing Systems, 57, 182-197. https://doi.org/https://doi.org/10.1016/j.jmsy.2020.09.004
Dai, M., Tang, D., Giret, A., & Salido, M. A. (2019). Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints. Robotics and Computer-Integrated Manufacturing, 59, 143-157. https://doi.org/https://doi.org/10.1016/j.rcim.2019.04.006
Dai, M., Tang, D., Giret, A., Salido, M. A., & Li, W. D. (2013). Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, 29(5), 418-429. https://doi.org/https://doi.org/10.1016/j.rcim.2013.04.001
de Arruda, A. C., Weigang, L., & Milea, V. (2015). A new Airport Collaborative Decision Making algorithm based on Deferred Acceptance in a two-sided market. Expert Systems with Applications, 42(7), 3539-3550. https://doi.org/https://doi.org/10.1016/j.eswa.2014.11.060
Delaram, J., Fatahi Valilai, O., Houshamand, M., & Ashtiani, F. (2021). A matching mechanism for public cloud manufacturing platforms using intuitionistic Fuzzy VIKOR and deferred acceptance algorithm. International Journal of Management Science and Engineering Management, 1-16. https://doi.org/https://doi.org/10.1080/17509653.2021.1892549
Dworczak, P. (2021). Deferred Acceptance with Compensation Chains. Operations Research, 69(2), 456-468. https://doi.org/https://doi.org/10.1287/opre.2020.2042
Fan, J., Shen, W., Gao, L., Zhang, C., & Zhang, Z. (2021). A hybrid Jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths. Journal of Manufacturing Systems, 60, 298-311. https://doi.org/https://doi.org/10.1016/j.jmsy.2021.05.018
Gale, D., & Shapley, L. S. (1962). College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1), 9-15. https://doi.org/10.1080/00029890.1962.11989827
Gong, G., Deng, Q., Gong, X., Liu, W., & Ren, Q. (2018). A new double flexible job-shop scheduling problem integrating processing time, green production, and human factor indicators. Journal of Cleaner Production, 174, 560-576. https://doi.org/https://doi.org/10.1016/j.jclepro.2017.10.188
Gong, X., De Pessemier, T., Martens, L., & Joseph, W. (2019). Energy- and labor-aware flexible job shop scheduling under dynamic electricity pricing: A many-objective optimization investigation. Journal of Cleaner Production, 209, 1078-1094. https://doi.org/https://doi.org/10.1016/j.jclepro.2018.10.289
Guo, W., Lei, Q., Song, Y., & Lyu, X. (2021). A learning interactive genetic algorithm based on edge selection encoding for assembly job shop scheduling problem. Computers & Industrial Engineering, 159, 107455. https://doi.org/https://doi.org/10.1016/j.cie.2021.107455
Harjunkoski, I., Maravelias, C. T., Bongers, P., Castro, P. M., Engell, S., Grossmann, I. E., Hooker, J., Méndez, C., Sand, G., & Wassick, J. (2014). Scope for industrial applications of production scheduling models and solution methods. Computers & Chemical Engineering, 62, 161-193. https://doi.org/https://doi.org/10.1016/j.compchemeng.2013.12.001
Honda, E. (2020). A modified deferred acceptance algorithm for conditionally lexicographic-substitutable preferences. Journal of Mathematical Economics, 102458. https://doi.org/https://doi.org/10.1016/j.jmateco.2020.102458
Iqbal, M. W., Kang, Y., & Jeon, H. W. (2020). Zero waste strategy for green supply chain management with minimization of energy consumption. Journal of Cleaner Production, 245, 118827. https://doi.org/https://doi.org/10.1016/j.jclepro.2019.118827
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. https://doi.org/https://doi.org/10.1016/j.ijpe.2016.01.016
Li, Z., Tang, Q., & Zhang, L. (2016). Minimizing energy consumption and cycle time in two-sided robotic assembly line systems using restarted simulated annealing algorithm. Journal of Cleaner Production, 135, 508-522. https://doi.org/https://doi.org/10.1016/j.jclepro.2016.06.131
Liu, M., Lv, J., Du, S., Deng, Y., Shen, X., & Zhou, Y. (2024). Multi-resource constrained flexible job shop scheduling problem with fixture-pallet combinatorial optimisation. Computers & Industrial Engineering, 188, 109903. https://doi.org/https://doi.org/10.1016/j.cie.2024.109903
Liu, Y., Zhang, L., Tao, F., & Wang, L. (2017). Resource service sharing in cloud manufacturing based on the Gale–Shapley algorithm: advantages and challenge. International Journal of Computer Integrated Manufacturing, 30(4-5), 420-432. https://doi.org/10.1080/0951192X.2015.1067916
Liu, Z., Wang, J., Zhang, C., Chu, H., Ding, G., & Zhang, L. (2021). A hybrid genetic-particle swarm algorithm based on multilevel neighbourhood structure for flexible job shop scheduling problem. Computers & Operations Research, 105431. https://doi.org/https://doi.org/10.1016/j.cor.2021.105431
Lunardi, W. T., Birgin, E. G., Ronconi, D. P., & Voos, H. (2021). Metaheuristics for the online printing shop scheduling problem. European Journal of Operational Research, 293(2), 419-441. https://doi.org/https://doi.org/10.1016/j.ejor.2020.12.021
Mansouri, S. A., Aktas, E., & Besikci, U. (2016). Green scheduling of a two-machine flowshop: Trade-off between makespan and energy consumption. European Journal of Operational Research, 248(3), 772-788. https://doi.org/https://doi.org/10.1016/j.ejor.2015.08.064
Maschler, M., Solan, E., & Zamir, S. (2013). Game Theory. Cambridge University Press. https://doi.org/https://doi.org/10.1017/CBO9780511794216
Masmoudi, O., Delorme, X., & Gianessi, P. (2019). Job-shop scheduling problem with energy consideration. International Journal of Production Economics, 216, 12-22. https://doi.org/https://doi.org/10.1016/j.ijpe.2019.03.021
Meng, L., Zhang, C., Shao, X., & Ren, Y. (2019). MILP models for energy-aware flexible job shop scheduling problem. Journal of Cleaner Production, 210, 710-723. https://doi.org/https://doi.org/10.1016/j.jclepro.2018.11.021
Meng, L., Zhang, C., Zhang, B., Gao, K., Ren, Y., & Sang, H. (2023). MILP modeling and optimization of multi-objective flexible job shop scheduling problem with controllable processing times. Swarm and Evolutionary Computation, 82, 101374. https://doi.org/https://doi.org/10.1016/j.swevo.2023.101374
Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the Flexible Job-shop Scheduling Problem. Computers & Operations Research, 35(10), 3202-3212. https://doi.org/https://doi.org/10.1016/j.cor.2007.02.014
Pinedo, M. L. (2012). Scheduling (Vol. 29). Springer.
Raileanu, S., Anton, F., Iatan, A., Borangiu, T., Anton, S., & Morariu, O. (2017). Resource scheduling based on energy consumption for sustainable manufacturing. Journal of Intelligent Manufacturing, 28(7), 1519-1530. https://doi.org/10.1007/s10845-015-1142-5
Roth, A. E. (2003). The Origins, History, and Design of the Resident Match. JAMA, 289(7), 909-912. https://doi.org/https://www.doi.org/10.1001/jama.289.7.909
Roth, A. E. (2008). Deferred acceptance algorithms: history, theory, practice, and open questions. International Journal of Game Theory, 36(3), 537-569. https://doi.org/http://doi.org/10.1007/s00182-008-0117-6
Şahman, M. A. (2021). A discrete spotted hyena optimizer for solving distributed job shop scheduling problems. Applied Soft Computing, 106, 107349. https://doi.org/https://doi.org/10.1016/j.asoc.2021.107349
Sinha, R. K., & Chaturvedi, N. D. (2018). A graphical dual objective approach for minimizing energy consumption and carbon emission in production planning. Journal of Cleaner Production, 171, 312-321. https://doi.org/https://doi.org/10.1016/j.jclepro.2017.09.272
Sun, J., Zhang, G., Lu, J., & Zhang, W. (2021). A hybrid many-objective evolutionary algorithm for flexible job-shop scheduling problem with transportation and setup times. Computers & Operations Research, 105263. https://doi.org/https://doi.org/10.1016/j.cor.2021.105263
Tao, N., & Xu-ping, W. (2018). Study on disruption management strategy of job-shop scheduling problem based on prospect theory. Journal of Cleaner Production, 194, 174-178. https://doi.org/https://doi.org/10.1016/j.jclepro.2018.05.139
Türkyılmaz, A., Şenvar, Ö., Ünal, İ., & Bulkan, S. (2020). A research survey: heuristic approaches for solving multi objective flexible job shop problems. Journal of Intelligent Manufacturing, 31(8), 1949-1983. https://doi.org/https://doi.org/10.1007/s10845-020-01547-4
Vital-Soto, A., Azab, A., & Baki, M. F. (2020). Mathematical modeling and a hybridized bacterial foraging optimization algorithm for the flexible job-shop scheduling problem with sequencing flexibility. Journal of Manufacturing Systems, 54, 74-93. https://doi.org/https://doi.org/10.1016/j.jmsy.2019.11.010
Wang, J., Liu, Y., Ren, S., Wang, C., & Wang, W. (2021). Evolutionary game based real-time scheduling for energy-efficient distributed and flexible job shop. Journal of Cleaner Production, 293, 126093. https://doi.org/https://doi.org/10.1016/j.jclepro.2021.126093
Wang, L., Wang, S., Xu, Y., Zhou, G., & Liu, M. (2012). A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem. Computers & Industrial Engineering, 62(4), 917-926. https://doi.org/https://doi.org/10.1016/j.cie.2011.12.014
Wang, L., Zhou, G., Xu, Y., & Liu, M. (2013). A hybrid artificial bee colony algorithm for the fuzzy flexible job-shop scheduling problem. International Journal of Production Research, 51(12), 3593-3608. https://doi.org/https://doi.org/10.1080/00207543.2012.754549
Wang, S., Lu, X., Li, X. X., & Li, W. D. (2015). A systematic approach of process planning and scheduling optimization for sustainable machining. Journal of Cleaner Production, 87, 914-929. https://doi.org/https://doi.org/10.1016/j.jclepro.2014.10.008
Wu, X., Shen, X., & Li, C. (2019). The flexible job-shop scheduling problem considering deterioration effect and energy consumption simultaneously. Computers & Industrial Engineering, 135, 1004-1024. https://doi.org/https://doi.org/10.1016/j.cie.2019.06.048
Wu, X., & Sun, Y. (2018). A green scheduling algorithm for flexible job shop with energy-saving measures. Journal of Cleaner Production, 172, 3249-3264. https://doi.org/https://doi.org/10.1016/j.jclepro.2017.10.342
Wu, Z., Sun, S., & Yu, S. (2020). Optimizing makespan and stability risks in job shop scheduling. Computers & Operations Research, 122, 104963. https://doi.org/https://doi.org/10.1016/j.cor.2020.104963
Xie, J., Li, X., Gao, L., & Gui, L. (2023). A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems. Journal of Manufacturing Systems, 71, 82-94. https://doi.org/https://doi.org/10.1016/j.jmsy.2023.09.002
Xie, N., & Chen, N. (2018). Flexible job shop scheduling problem with interval grey processing time. Applied Soft Computing, 70, 513-524. https://doi.org/https://doi.org/10.1016/j.asoc.2018.06.004
Xin, X., Jiang, Q., Li, S., Gong, S., & Chen, K. (2021). Energy-efficient scheduling for a permutation flow shop with variable transportation time using an improved discrete whale swarm optimization. Journal of Cleaner Production, 293, 126121. https://doi.org/https://doi.org/10.1016/j.jclepro.2021.126121
Zhang, Y., Wang, J., Liu, S., & Qian, C. (2017). Game Theory Based Real-Time Shop Floor Scheduling Strategy and Method for Cloud Manufacturing. International Journal of Intelligent Systems, 32(4), 437-463. https://doi.org/https://doi.org/10.1002/int.21868
Zhou, G., Jiang, P., & Huang, G. Q. (2009). A game-theory approach for job scheduling in networked manufacturing. The International Journal of Advanced Manufacturing Technology, 41(9), 972-985. https://doi.org/https://doi.org/10.1007/s00170-008-1539-9
Advances in Industrial Engineering
Volume 58, Issue 2
December 2024
Pages 325-340

Files

Share

How to cite

Statistics