Advances in Industrial Engineering

Advances in Industrial Engineering

Unrelated Parallel Machines Scheduling with Sequence-Dependent Setup Times to Minimize Makespan and Tariff Charged Energy Consumption

Document Type : Research Paper

Authors
Taha Keshavarz 1
Erfaneh Karimi 2
Majid Shakhsi-Niaei 2
1 Department of Industrial Engineering, Semnan University, Semnan, Iran
2 Department of Industrial Engineering, Yazd University, Yazd, Iran
10.22059/jieng.2021.326682.1788
Abstract
An appropriate trade-off between total electricity costs and makespan can lead to good production planning and reduce unnecessary energy consumption. Time-of-use (TOU) electricity pricing policy has been executed in many countries which enabled industrial consumers with high energy consumption to reduce their energy costs. In this study, an unrelated parallel machines scheduling problem is considered for minimizing makespan and also energy consumption costs. Due to the importance of sequence-dependent setup times in production environments, they are considered according to the restricted duration of time periods under TOU policy. These considerations are added to the current literature. A mixed-integer bi-objective mathematical model is presented and the ε-constraint method is applied to solve small and also medium-sized instances. Because the problem is shown to be NP-hard, several large-sized instances are approximately solved using Multiple Objective Particle Swarm Optimization algorithm, and Multiple Objective Simulated Annealing algorithm. Computational experiments are conducted on randomly generated data. The results show the efficiency and appropriate performance of the proposed methods.
Keywords
Unrelated parallel machines scheduling
Makespan
Energy consumption
Time-of-use electricity price
Sequence-dependent setup times
  • [1] EI Energy use in industry, https://www.eia.gov/energyexplained/use-of-energy/industry.php ; 2020 [Accessed 28 July 2020].
  • [2] Li, L., Li, C., Tang, Y., & Li, L. An integrated approach of process planning and cutting parameter optimization for energy-aware CNC machining. Journal of Cleaner Production. 2017;162: 458-73.
  • [3] Zeng, Y., Che, A., & Wu, X. Bi-objective scheduling on uniform parallel machines considering electricity cost. Engineering Optimization. 2018;50(1): 19-36.
  • [4] Wu, X., & Che, A. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega. 2019; 82: 155-65.
  • [5] Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., & Sassani, F. Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research. 2009; 36(12): 3224-30.
  • [6] Angel, E., Bampis, E., & Kacem, F. Energy aware scheduling for unrelated parallel machines. IEEE International Conference on Green Computing and Communications: IEEE;2012 .p. 533-40.
  • [7] Liang, P., Yang, H. D., Liu, G. S., & Guo, J. H. An ant optimization model for unrelated parallel machine scheduling with energy consumption and total tardiness. Mathematical Problems in Engineering. 2015. doi: 1155/2015/907034
  • [8] 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(1-4): 213-26.
  • [9] Cota, L. , Coelho, V. N., Guimarães, F. G., & Souza, M. J. Bi‐criteria formulation for green scheduling with unrelated parallel machines with sequence‐dependent setup times. International Transactions in Operational Research. 2018 doi: 10.1111/itor.12566
  • [10] Soleimani, H., Ghaderi, H., Tsai, P. W., Zarbakhshnia, N., & Maleki, M. Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependent learning and power consumption minimization. Journal of Cleaner Production. 2020; 249: 119428.
  • [11] Zhu, W., & Tianyu, L. A Novel Multi-Objective Scheduling Method for Energy Based Unrelated Parallel Machines With Auxiliary Resource Constraints. IEEE Access.2019; 7: 168688-168699.
  • [12] Moon, J. Y., Shin, K., & Park, J. Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency. The International Journal of Advanced Manufacturing Technology. 2013; 68(1-4): 523-35.
  • [13] Ding, J. Y., Song, S., Zhang, R., Chiong, R., & Wu, C. Parallel machine scheduling under time-of-use electricity prices: New models and optimization approaches. IEEE Transactions on Automation Science and Engineering. 2015; 13(2): 1138-54.
  • [14] 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.
  • [15] Cheng, J., Chu, F., & Zhou, M. An improved model for parallel machine scheduling under time-of-use electricity price. IEEE Transactions on Automation Science and Engineering. 2017; 15(2): 896-9.
  • [16] Abikarram, J. B., McConky, K., & Proano, R. Energy cost minimization for unrelated parallel machine scheduling under real time and demand charge pricing. Journal of Cleaner Production. 2019; 208: 232-42.
  • [17] Saberi-Aliabad, H., Reisi-Nafchi, M., & Moslehi, G. Energy-efficient scheduling in an unrelated parallel-machine environment under time-of-use electricity tariffs. Journal of Cleaner Production.2020;249: 119393.
  • [18] Kurniawan, B. Mathematical Models of Energy-Conscious Bi-Objective Unrelated Parallel Machine Scheduling. Jurnal Teknik Industri.2020; 21(2): 115-125.
  • [19] 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.
  • [20] Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics: Elsevier; 1979. p. 287-326.
  • [21] Ehrgott, M., & Gandibleux, X. Multiobjective combinatorial optimization—theory, methodology, and applications. Multiple criteria optimization: State of the art annotated bibliographic surveys: Springer; 2003. p. 369-444.
  • [22] Coello, C. A. C., Pulido, G. T., & Lechuga, M. S. Handling multiple objectives with particle swarm optimization. IEEE Transactions on evolutionary computation. 2004; 8(3): 256-79.
  • [23] Wang, W., Chen, L., Jie, J., Zhao, Y., & Zhang, J. A novel multi-objective particle swarm optimization algorithm for flow shop scheduling problems. International Conference on Intelligent Computing: Springer; 2011 .p. 24-31.
  • [24] Torabi, S. A., Sahebjamnia, N., Mansouri, S. A., & Bajestani, M. A. A particle swarm optimization for a fuzzy multi-objective unrelated parallel machines scheduling problem. Applied Soft Computing. 2013; 13(12): 4750-62.
  • [25] Liao, X., Zhang, R., & Chiong, R. Multi-objective optimization of single machine scheduling with energy consumption constraints. IEEE Symposium Series on Computational Intelligence (SSCI): IEEE; 2017. p. 1-8.
  • [26] Manupati, V. K., Rajyalakshmi, G., Chan, F. T., & Thakkar, J. J. A hybrid multi-objective evolutionary algorithm approach for handling sequence-and machine-dependent set-up times in unrelated parallel machine scheduling problem. Sādhanā. 2017; 42(3): 391-403.
  • [27] Liu, Y., Liao, X., & Zhang, R. An Enhanced MOPSO Algorithm for Energy-Efficient Single-Machine Production Scheduling. Sustainability,. 2019; 11(19): 5381.
  • [28] Ulungu, E. L., Teghem, J. F. P. H., Fortemps, P. H., & Tuyttens, D. MOSA method: a tool for solving multiobjective combinatorial optimization problems. Journal of multicriteria decision analysis. 1999; 8(4): 221.
  • [29] Mansouri, S. A., Hendizadeh, S. H., & Salmasi, N. Bicriteria scheduling of a two-machine flowshop with sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology. 2009; 40(11-12): 1216-26.
  • [30] Chyu, C. C., & Chang, W. S. Optimizing fuzzy makespan and tardiness for unrelated parallel machine scheduling with archived metaheuristics. The International Journal of Advanced Manufacturing Technology. 2011; 57(5-8): 763.
  • [31] Mohammadi, H., & Sahraeian, R. Bi-objective simulated annealing and adaptive memory procedure approaches to solve a hybrid flow shop scheduling problem with unrelated parallel machines. IEEE International Conference on Industrial Engineering and Engineering Management: IEEE; 2012. p. 528-32.
  • [32] Shoaardebili, N., & Fattahi, P. Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints. International Journal of Production Research. 2015; 53(3): 944-68.
  • [33] Tirkolaee, E. B., Goli, A., Hematian, M., Sangaiah, A. K., & Han, T. Multi-objective multi-mode resource constrained project scheduling problem using Pareto-based algorithms. Computing. 2019; 101(6): 547-70.
  • [34] Shannon, C. E. A mathematical theory of communication. The Bell system technical journal. 1948; 27(3): 379-423.
  • [35] Zhang, H., Wu, Y., Pan, R., & Xu, G. Two-stage parallel speed-scaling machine scheduling under time-of-use tariffs. Journal of Intelligent Manufacturing. 2020:1-22.
Advances in Industrial Engineering
Volume 55, Issue 1
Winter 2021
Pages 91-113