IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v13y2021i16p9277-d616793.html
   My bibliography  Save this article

Green Scheduling of Identical Parallel Machines with Release Date, Delivery Time and No-Idle Machine Constraints

Author

Listed:
  • Lotfi Hidri

    (Industrial Engineering Department, College of Engineering, King Saud University, P.O. Box 800, Riyadh 11421, Saudi Arabia)

  • Ali Alqahtani

    (Industrial Engineering Department, College of Engineering, King Saud University, P.O. Box 800, Riyadh 11421, Saudi Arabia)

  • Achraf Gazdar

    (Software Engineering Department, College of Computer and Information Sciences, King Saud University, P.O. Box 51178, Riyadh 11543, Saudi Arabia)

  • Belgacem Ben Youssef

    (Computer Engineering Department, College of Computer and Information Sciences, King Saud University, P.O. Box 51178, Riyadh 11543, Saudi Arabia)

Abstract

Global warming and climate change are threatening life on earth. These changes are due to human activities resulting in the emission of greenhouse gases. This is caused by intensive industrial activities and excessive fuel energy consumption. Recently, the scheduling of production systems has been judged to be an effective way to reduce energy consumption. This is the field of green scheduling, which aims to allocate jobs to machines in order to minimize total costs, with a focus on the sustainable use of energy. Several studies have investigated parallel-machine shops, with a special focus on reducing and minimizing the total consumed energy. Few studies explicitly include the idle energy of parallel machines, which is the energy consumed when the machines are idle. In addition, very few studies have considered the elimination of idle machine times as an efficient way to reduce the total consumed energy. This is the no-idle machine constraint, which is the green aspect of the research. In this context, this paper addresses the green parallel-machine scheduling problem, including release dates, delivery times, and no-idle machines, with the objective of minimizing the maximum completion time. This problem is of practical interest since it is encountered in several industry processes, such as the steel and automobile industries. A mixed-integer linear programming (MILP) model is proposed for use in obtaining exact solutions for small-sized instances. Due to the NP-hardness of the studied problem, and encouraged by the successful adaptation of metaheuristics for green scheduling problems, three genetic algorithms (GAs) using three different crossover operators and a simulated annealing algorithm (SA) were developed for large-sized problems. A new family of lower bounds is proposed. This was intended for the evaluation of the performance of the proposed algorithms over the average percent of relative deviation (ARPD). In addition, the green aspect was evaluated over the percentage of saved energy, while eliminating the idle-machine times. An extensive experimental study was carried out on a benchmark of test problems with up to 200 jobs and eight machines. This experimental study showed that one GA variant dominated the other proposed procedures. Furthermore, the obtained numerical results provide strong evidence that the proposed GA variant outperformed the existing procedures from the literature. The experimental study also showed that the adoption of the no-idle machine time constraints made it possible to reduce the total consumed energy by 29.57%, while the makespan (cost) increased by only 0.12%.

Suggested Citation

  • Lotfi Hidri & Ali Alqahtani & Achraf Gazdar & Belgacem Ben Youssef, 2021. "Green Scheduling of Identical Parallel Machines with Release Date, Delivery Time and No-Idle Machine Constraints," Sustainability, MDPI, vol. 13(16), pages 1-30, August.
    • Handle: RePEc:gam:jsusta:v:13:y:2021:i:16:p:9277-:d:616793
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/13/16/9277/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2071-1050/13/16/9277/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Federico Della Croce & Andrea Grosso & Fabio Salassa, 2021. "Minimizing total completion time in the two-machine no-idle no-wait flow shop problem," Journal of Heuristics, Springer, vol. 27(1), pages 159-173, April.
    2. Jeong, Yoonjea & Saha, Subrata & Chatterjee, Debajyoti & Moon, Ilkyeong, 2018. "Direct shipping service routes with an empty container management strategy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 123-142.
    3. Ilkyeong Moon & Yoon Jea Jeong & Subrata Saha, 2016. "Fuzzy Bi-Objective Production-Distribution Planning Problem under the Carbon Emission Constraint," Sustainability, MDPI, vol. 8(8), pages 1-17, August.
    4. Li, Lin & Sun, Zeyi & Yao, Xufeng & Wang, Donghai, 2016. "Optimal production scheduling for energy efficiency improvement in biofuel feedstock preprocessing considering work-in-process particle separation," Energy, Elsevier, vol. 96(C), pages 474-481.
    5. Zhi-Long Chen & Warren B. Powell, 1999. "Solving Parallel Machine Scheduling Problems by Column Generation," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 78-94, February.
    6. Peng Liang & Hai-dong Yang & Guo-sheng Liu & Jian-hua Guo, 2015. "An Ant Optimization Model for Unrelated Parallel Machine Scheduling with Energy Consumption and Total Tardiness," Mathematical Problems in Engineering, Hindawi, vol. 2015, pages 1-8, August.
    7. Anghinolfi, Davide & Paolucci, Massimo & Ronco, Roberto, 2021. "A bi-objective heuristic approach for green identical parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 289(2), pages 416-434.
    8. Zhou, Shengchao & Xie, Jianhui & Du, Ni & Pang, Yan, 2018. "A random-keys genetic algorithm for scheduling unrelated parallel batch processing machines with different capacities and arbitrary job sizes," Applied Mathematics and Computation, Elsevier, vol. 334(C), pages 254-268.
    9. Wu, Xueqi & Che, Ada, 2019. "A memetic differential evolution algorithm for energy-efficient parallel machine scheduling," Omega, Elsevier, vol. 82(C), pages 155-165.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tao Dai & Xiangqi Fan, 2021. "Multi-Stove Scheduling for Sustainable On-Demand Food Delivery," Sustainability, MDPI, vol. 13(23), pages 1-13, November.
    2. Qingfei Tong & Xinguo Ming & Xianyu Zhang, 2023. "Construction of Sustainable Digital Factory for Automated Warehouse Based on Integration of ERP and WMS," Sustainability, MDPI, vol. 15(2), pages 1-22, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yamashiro, Hirochika & Nonaka, Hirofumi, 2021. "Estimation of processing time using machine learning and real factory data for optimization of parallel machine scheduling problem," Operations Research Perspectives, Elsevier, vol. 8(C).
    2. Catanzaro, Daniele & Pesenti, Raffaele & Ronco, Roberto, 2023. "Job scheduling under Time-of-Use energy tariffs for sustainable manufacturing: a survey," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1091-1109.
    3. Lixin Tang & Gongshu Wang & Zhi-Long Chen, 2014. "Integrated Charge Batching and Casting Width Selection at Baosteel," Operations Research, INFORMS, vol. 62(4), pages 772-787, August.
    4. Sung, Inkyung & Lee, Taesik, 2016. "Optimal allocation of emergency medical resources in a mass casualty incident: Patient prioritization by column generation," European Journal of Operational Research, Elsevier, vol. 252(2), pages 623-634.
    5. H. Fei & C. Chu & N. Meskens, 2009. "Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria," Annals of Operations Research, Springer, vol. 166(1), pages 91-108, February.
    6. Timo Gschwind & Stefan Irnich & Christian Tilk & Simon Emde, 2020. "Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network," Journal of Scheduling, Springer, vol. 23(3), pages 363-377, June.
    7. Yunting Feng & Yong Geng & Ge Zhao & Mengya Li, 2022. "Carbon Emission Constraint Policy in an OEM and Outsourcing Remanufacturer Supply Chain with Consumer Preferences," IJERPH, MDPI, vol. 19(8), pages 1-16, April.
    8. Li, Yu & Kesharwani, Rajkamal & Sun, Zeyi & Qin, Ruwen & Dagli, Cihan & Zhang, Meng & Wang, Donghai, 2020. "Economic viability and environmental impact investigation for the biofuel supply chain using co-fermentation technology," Applied Energy, Elsevier, vol. 259(C).
    9. Hu, Yusha & Man, Yi, 2022. "Two-stage energy scheduling optimization model for complex industrial process and its industrial verification," Renewable Energy, Elsevier, vol. 193(C), pages 879-894.
    10. Chen, Haoxun & Luh, Peter B., 2003. "An alternative framework to Lagrangian relaxation approach for job shop scheduling," European Journal of Operational Research, Elsevier, vol. 149(3), pages 499-512, September.
    11. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    12. Zhen, Lu & Wu, Yiwei & Wang, Shuaian & Laporte, Gilbert, 2020. "Green technology adoption for fleet deployment in a shipping network," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 388-410.
    13. Liman Feng & Guo Chen & Shengchao Zhou & Xiaojun Zhou & Mingzhou Jin, 2024. "An Energy-Efficient Unrelated Parallel Machine Scheduling Problem with Batch Processing and Time-of-Use Electricity Prices," Mathematics, MDPI, vol. 12(3), pages 1-14, January.
    14. Pereira Lopes, Manuel J. & de Carvalho, J.M. Valerio, 2007. "A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1508-1527, February.
    15. Sun, Yanshuo & Chen, Zhi-Long & Zhang, Lei, 2020. "Nonprofit peer-to-peer ridesharing optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    16. Ge, Yuntian & Li, Lin, 2018. "System-level energy consumption modeling and optimization for cellulosic biofuel production," Applied Energy, Elsevier, vol. 226(C), pages 935-946.
    17. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    18. Fan, Tijun & Pan, Qianlan & Pan, Fei & Zhou, Wei & Chen, Jingyi, 2020. "Intelligent logistics integration of internal and external transportation with separation mode," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    19. Massimo Bertolini & Francesco Leali & Davide Mezzogori & Cristina Renzi, 2023. "A Keyword, Taxonomy and Cartographic Research Review of Sustainability Concepts for Production Scheduling in Manufacturing Systems," Sustainability, MDPI, vol. 15(8), pages 1-21, April.
    20. Ghoniem, Ahmed & Farhadi, Farbod & Reihaneh, Mohammad, 2015. "An accelerated branch-and-price algorithm for multiple-runway aircraft sequencing problems," European Journal of Operational Research, Elsevier, vol. 246(1), pages 34-43.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jsusta:v:13:y:2021:i:16:p:9277-:d:616793. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.