Energy-Conscious Common Operation Scheduling in an Identical Parallel Machine Environment

Document Type : Original Article

Authors

Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran

Abstract

The relentless growth of global energy consumption poses a multitude of complex challenges, including the depletion of finite energy resources and the exacerbation of greenhouse gas emissions, which contribute to climate change. In the face of these pressing environmental concerns, the manufacturing sector, a significant energy consumer, is under immense pressure to adopt sustainable practices. The critical intersection of energy consumption management and production operation scheduling emerges as a pivotal domain for addressing these challenges. The scheduling of common operations, exemplified by the cutting stock problem in industries like furniture and apparel, represents a prevalent challenge in production environments. For the first time, this paper pioneers an investigation into an identical parallel machine scheduling problem, taking into account common operations to minimize total energy consumption and total completion time concurrently. For this purpose, two bi-objective mixed integer linear programming models are presented, and an augmented ε – constraint method is used to obtain the Pareto optimal front for small-scale instances. Considering the NP-hardness of this problem, a non-dominated sorting genetic algorithm (NSGA-II) and a hybrid non-dominated sorting genetic algorithm with particle swarm optimization (HNSGAII-PSO) are developed to solve medium- and large-scale instances to achieve good approximate Pareto fronts. The performance of the proposed algorithms is assessed by conducting computational experiments on test problems. The results demonstrate that the proposed HNSGAII-PSO performs better than the suggested NSGA-II in solving the test problems.

Graphical Abstract

Energy-Conscious Common Operation Scheduling in an Identical Parallel Machine Environment

Keywords

Main Subjects

References

  1. Babaee Tirkolaee E, Goli A, Mardani A. A novel two-echelon hierarchical location-allocation-routing optimization for green energy-efficient logistics systems. Annals of Operations Research. 2021. 10.1007/s10479-021-04363-y
  2. Zhang X, Zhou H, Fu C, Mi M, Zhan C, Pham DT, et al. Application and planning of an energy-oriented stochastic disassembly line balancing problem. Environmental Science and Pollution Research. 2023:1-15. 10.1007/s11356-023-27288-4
  3. Zandvakili A, Mansouri N, Javidi M. Energy-aware task scheduling in cloud compting based on discrete pathfinder algorithm. International Journal of Engineering, Transactions C: Aspects. 2021;34(9):2124-36. 10.5829/IJE.2021.34.09C.10
  4. Tian G, Zhang C, Fathollahi-Fard AM, Li Z, Zhang C, Jiang Z. An enhanced social engineering optimizer for solving an energy-efficient disassembly line balancing problem based on bucket brigades and cloud theory. IEEE Transactions on Industrial Informatics. 2022. 10.1109/TII.2022.3193866
  5. Fang K, Uhan N, Zhao F, Sutherland JW. A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. Journal of Manufacturing Systems. 2011;30(4):234-40. 10.1016/j.jmsy.2011.08.004
  6. Lu C, Gao L, Li X, Pan Q, Wang Q. Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm. Journal of cleaner production. 2017;144:228-38. 10.1016/j.jclepro.2017.01.011
  7. Jovane F, Yoshikawa H, Alting L, Boer CR, Westkamper E, Williams D, et al. The incoming global technological and industrial revolution towards competitive sustainable manufacturing. CIRP annals. 2008;57(2):641-59. 10.1016/j.cirp.2008.09.010
  8. Mori M, Fujishima M, Inamasu Y, Oda Y. A study on energy efficiency improvement for machine tools. CIRP annals. 2011;60(1):145-8. 10.1016/j.cirp.2011.03.099
  9. Pinedo ML. Scheduling: Springer; 2012.
  10. Ding J, Schulz S, Shen L, Buscher U, Lü Z. Energy aware scheduling in flexible flow shops with hybrid particle swarm optimization. Computers & Operations Research. 2021;125:105088. 10.1016/j.cor.2020.105088
  11. Zhang M, Yan J, Zhang Y, Yan S. Optimization for energy-efficient flexible flow shop scheduling under time of use electricity tariffs. Procedia CIRP. 2019;80:251-6. 10.1016/j.procir.2019.01.062
  12. Guo J, Lei D, Li M. Two-phase imperialist competitive algorithm for energy-efficient flexible job shop scheduling. Journal of Intelligent & Fuzzy Systems. 2021;40(6):12125-37. 10.3233/JIFS-210198
  13. Fathollahi-Fard AM, Woodward L, Akhrif O. Sustainable distributed permutation flow-shop scheduling model based on a triple bottom line concept. Journal of Industrial Information Integration. 2021;24:100233. 10.1016/j.jii.2021.100233
  14. Li Z, Yang H, Zhang S, Liu G. Unrelated parallel machine scheduling problem with energy and tardiness cost. The International Journal of Advanced Manufacturing Technology. 2016;84:213-26. 10.1007/s00170-015-7657-2
  15. Che A, Zhang S, Wu X. Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. Journal of cleaner production. 2017;156:688-97. 10.1016/j.jclepro.2017.04.018
  16. Wang Y-C, Wang M-J, Lin S-C. Selection of cutting conditions for power constrained parallel machine scheduling. Robotics and Computer-Integrated Manufacturing. 2017;43:105-10. 10.1016/j.rcim.2015.10.010
  17. Zeng Y, Che A, Wu X. Bi-objective scheduling on uniform parallel machines considering electricity cost. Engineering Optimization. 2018;50(1):19-36. 10.1080/0305215X.2017.1296437
  18. Wu X, Che A. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega. 2019;82:155-65. 10.1016/j.omega.2018.01.001
  19. Cota LP, Coelho VN, Guimarães FG, Souza MJ. Bi‐criteria formulation for green scheduling with unrelated parallel machines with sequence‐dependent setup times. International Transactions in Operational Research. 2021;28(2):996-1017. 10.1111/itor.12566
  20. Safarzadeh H, Niaki STA. Bi-objective green scheduling in uniform parallel machine environments. Journal of cleaner production. 2019;217:559-72. 10.1016/j.jclepro.2019.01.166
  21. Wang S, Wang X, Yu J, Ma S, Liu M. Bi-objective identical parallel machine scheduling to minimize total energy consumption and makespan. Journal of cleaner production. 2018;193:424-40. 10.1016/j.jclepro.2018.05.056
  22. Anghinolfi D, Paolucci M, Ronco R. A bi-objective heuristic approach for green identical parallel machine scheduling. European Journal of Operational Research. 2021;289(2):416-34. 10.1016/j.ejor.2020.07.020
  23. Zhang H, Wu Y, Pan R, Xu G. Two-stage parallel speed-scaling machine scheduling under time-of-use tariffs. Journal of Intelligent Manufacturing. 2021;32:91-112. 10.1007/s10845-020-01561-6
  24. Keshavarz T, Karimi E, Shakhsi-Niaei M. Unrelated parallel machines scheduling with sequence-dependent setup times to minimize makespan and tariff charged energy consumption. Advances in Industrial Engineering. 2021;55(1):91-113. 10.22059/jieng.2021.326682.1788
  25. Zhou B-H, Gu J. Energy-awareness scheduling of unrelated parallel machine scheduling problems with multiple resource constraints. International Journal of Operational Research. 2021;41(2):196-217. 10.1504/IJOR.2021.115623
  26. Módos I, Šucha P, Hanzálek Z. On parallel dedicated machines scheduling under energy consumption limit. Computers & Industrial Engineering. 2021;159:107209. 10.1016/j.cie.2021.107209
  27. Rego MF, Pinto JCE, Cota LP, Souza MJ. A mathematical formulation and an NSGA-II algorithm for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling. PeerJ Computer Science. 2022;8:e844. 10.7717/peerj-cs.844
  28. Asadpour M, Hodaei Z, Azami M, Kehtari E, Vesal N. A green model for identical parallel machines scheduling problem considering tardy jobs and job splitting property. Sustainable Operations and Computers. 2022;3:149-55.
  29. Gaggero M, Paolucci M, Ronco R. Exact and Heuristic Solution Approaches for Energy-Efficient Identical Parallel Machine Scheduling with Time-of-Use Costs. European Journal of Operational Research. 2023.
  30. Arbib C, Servilio M, Felici G, Servilio M. Sorting common operations to minimize the number of tardy jobs. Networks. 2014;64(4):306-20. 10.1002/net.21576
  31. Cheng T, Diamond J, Lin BM. Optimal scheduling in film production to minimize talent hold cost. Journal of Optimization Theory and Applications. 1993;79(3):479-92. 10.1007/BF00940554
  32. Wang J, Qiao C, Yu H, editors. On progressive network recovery after a major disruption. 2011 Proceedings IEEE INFOCOM; 2011: IEEE. 10.1109/INFCOM.2011.5934996
  33. Arbib C, Felici G, Servilio M. Common operation scheduling with general processing times: A branch-and-cut algorithm to minimize the weighted number of tardy jobs. Omega. 2019;84:18-30. 10.1016/j.omega.2018.04.002
  34. Cherri AC, Arenales MN, Yanasse HH, Poldi KC, Vianna ACG. The one-dimensional cutting stock problem with usable leftovers–A survey. European Journal of Operational Research. 2014;236(2):395-402. 10.1016/j.ejor.2013.11.026
  35. Hinxman A. The trim-loss and assortment problems: A survey. European Journal of Operational Research. 1980;5(1):8-18. 10.1016/0377-2217(80)90068-5
  36. Dyckhoff H. A typology of cutting and packing problems. European journal of operational research. 1990;44(2):145-59. 10.1016/0377-2217(90)90350-K
  37. Wäscher G, Haußner H, Schumann H. An improved typology of cutting and packing problems. European journal of operational research. 2007;183(3):1109-30. 10.1016/j.ejor.2005.12.047
  38. Arbib C, Marinelli F. On cutting stock with due dates. Omega. 2014;46:11-20. 10.1016/j.omega.2014.01.004
  39. Cui Y, Zhong C, Yao Y. Pattern-set generation algorithm for the one-dimensional cutting stock problem with setup cost. European Journal of Operational Research. 2015;243(2):540-6. 10.1016/j.ejor.2014.12.015
  40. Wuttke DA, Heese HS. Two-dimensional cutting stock problem with sequence dependent setup times. European Journal of Operational Research. 2018;265(1):303-15. 10.1016/j.ejor.2017.07.036
  41. Graham RL, Lawler EL, Lenstra JK, Kan AR. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics. 5: Elsevier; 1979. p. 287-326.
  42. Garey MR, Johnson DS. ``strong''np-completeness results: Motivation, examples, and implications. Journal of the ACM (JACM). 1978;25(3):499-508.
  43. Deb K, Agrawal S, Pratap A, Meyarivan T, editors. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. International conference on parallel problem solving from nature; 2000: Springer.
  44. Duan J, Wang J. Energy-efficient scheduling for a flexible job shop with machine breakdowns considering machine idle time arrangement and machine speed level selection. Computers & Industrial Engineering. 2021;161:107677.
  45. Xue L, Wang X. A multi-objective discrete differential evolution algorithm for energy-efficient two-stage flow shop scheduling under time-of-use electricity tariffs. Applied Soft Computing. 2023;133:109946.
  46. Eberhart R, Kennedy J, editors. Particle swarm optimization. Proceedings of the IEEE international conference on neural networks; 1995: Citeseer.
  47. Hulett M, Damodaran P, Amouie M. Scheduling non-identical parallel batch processing machines to minimize total weighted tardiness using particle swarm optimization. Computers & Industrial Engineering. 2017;113:425-36.
  48. Marichelvam M, Geetha M, Tosun Ö. An improved particle swarm optimization algorithm to solve hybrid flowshop scheduling problems with the effect of human factors–A case study. Computers & Operations Research. 2020;114:104812. 10.1016/j.cor.2019.104812
  49. Damodaran P, Diyadawagamage DA, Ghrayeb O, Vélez-Gallego MC. A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines. The International Journal of Advanced Manufacturing Technology. 2012;58(9):1131-40.
  50. Lian Z. A united search particle swarm optimization algorithm for multiobjective scheduling problem. Applied Mathematical Modelling. 2010;34(11):3518-26. 10.1016/j.apm.2010.03.001
  51. Afzalirad M, Rezaeian J. A realistic variant of bi-objective unrelated parallel machine scheduling problem: NSGA-II and MOACO approaches. Applied Soft Computing. 2017;50:109-23. 10.1016/j.asoc.2016.10.039
  52. Zandi A, Ramezanian R, Monplaisir L. Green parallel machines scheduling problem: A bi-objective model and a heuristic algorithm to obtain Pareto frontier. Journal of the Operational Research Society. 2020;71(6):967-78. 10.1080/01605682.2019.1595190
  53. Taguchi G. Introduction to quality engineering, Asian productivity organization. Dearborn, Michigan: American Supplier Institute Inc. 1986.
International Journal of Engineering
Volume 37, Issue 7
TRANSACTIONS A: Basics
July 2024
Pages 1443-1465

Files

Share

How to cite

Statistics