Efficient Approaches for Solving a Multiobjective Energy-aware Job Shop Scheduling Problem

• Autorzy: González, Miguel A. , Oddi, Angelo , Rasconi, Riccardo
• Języki publikacji: EN

Abstrakty

EN

One of the most recent and interesting trends in intelligent scheduling is trying to reduce the energy consumption in order to obtain lower production costs and smaller carbon footprint. In this work we consider the energy-aware job shop scheduling problem, where we have to minimize at the same time an efficiency-based objective, as is the total weighted tardiness, and also the overall energy consumption. We experimentally show that we can reduce the energy consumption of a given schedule by delaying some operations, and to this end we design a heuristic procedure to improve a given schedule. As the problem is computationally complex, we design three approaches to solve it: a Pareto-based multiobjective evolutionary algorithm, which is hybridized with a multiobjective local search method and a linear programming step, a decomposition-based multiobjective evolutionary algorithm hybridized with a single-objective local search method, and finally a constraint programming approach. We perform an extensive experimental study to analyze our algorithms and to compare them with the state of the art.

Słowa kluczowe

EN

energy; job shop; metaheuristics; multiobjective optimization

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 167, nr 1-2
• Strony: 93--132
• Opis fizyczny: Bibliogr. 85 poz., rys., tab., wykr.

Twórcy

autor

González, Miguel A.

• Department of Computing, University of Oviedo, Campus de Gijón, 33203 Gijón, Spain,

autor

Oddi, Angelo

• ISTC-CNR, Via San Martino della Battaglia, 44, 00185 Rome, Italy,

autor

Rasconi, Riccardo

• ISTC-CNR, Via San Martino della Battaglia, 44, 00185 Rome, Italy,

Bibliografia

• [1] Pinedo M. Planning and Scheduling in Manufacturing and Services. Springer, 2005. doi:10.1007/b139030.
• [2] Garey M, Johnson D, Sethi R. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1976. 1 (2):117-129. URL https://www.jstor.org/stable/3689278.
• [3] Wisner J, Siferd S. A survey of US manufacturing practices in make-to-order machine shops. Production and Inventory Management Journal, 1995. 1:1-7.
• [4] Conner G. 10 questions. Manufacturing Engineering Magazine, 2009. pp. 93-99.
• [5] Dabia S, Talbi EG, van Woensel T, De Kok T. Approximating multi-objective scheduling problems. Computers & Operations Research, 2013. 40:1165-1175. URL https://doi.org/10.1016/j.cor.2012.12.001.
• [6] Deb K, Pratap A, Agarwal S, Meyarivan T. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002. 6 (2):182-197. doi:10.1109/4235.996017.
• [7] Zhang Q, Li H. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. Evolutionary Computation, IEEE Transactions on, 2007. 11 (6):712-731. doi:10.1109/TEVC.2007.892759.
• [8] Miettinen K. Nonlinear Multiobjective Optimization. International Series in Operations Research & Management Science. Springer US, 2012. ISBN 9781461555636. URL https://books.google.it/books?id=bnzjBwAAQBAJ.
• [9] González MA, Oddi A, Rasconi R. Multi-Objective Optimization in a Job Shop with Energy Costs through Hybrid Evolutionary Techniques. In: Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling (ICAPS-2017). AAAI Press, 2017 pp. 140-148.
• [10] Adams J, Balas E, Zawack D. The shifting bottleneck procedure for job shop scheduling. Managament Science, 1988. 34:391-401. URL https://doi.org/10.1287/mnsc.34.3.391.
• [11] Beck JC, Feng T, Watson JP. Combining Constraint Programming and Local Search for Job-Shop Scheduling. Informs Journal on Computing, 2011. 23:1-14. doi:10.1287/ijoc.1100.0388.
• [12] Nowicki E, Smutnicki C. An Advanced Tabu Search Algorithm For The Job Shop Problem. Journal of Scheduling, 2005. 8 (2):145-159. doi:10.1007/s10951-005-6364-5.
• [13] Singer M, Pinedo M. A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. IIE Transactions, 1998. 30:109-118. doi:10.1023/A:1007405915227.
• [14] Singer M, Pinedo M. A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Naval Research Logistics, 1999. 46 (1):1-17. URL https://doi.org/10.1002/(SICI)1520-6750(199902)46:1<1::AID-NAV1>3.0.CO;2-%23.
• [15] Kreipl S. A large step random walk for minimizing total weighted tardiness in a job shop. Journal of Scheduling, 2000. 3:125-138. doi:10.1002/(SICI)1099-1425(200005/06)3:3¡125::AID-JOS40¿3.0.CO;2-C.
• [16] Essafi I, Mati Y, Dauzère-Pérès S. A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Computers & Operations Research, 2008. 35:2599-2616. doi:10.1016/j.cor.2006.12.019.
• [17] Mati Y, Dauzere-Peres S, Lahlou C. A General Approach for Optimizing Regular Criteria in the Job-Shop Scheduling Problem. European Journal of Operational Research, 2011. 212:33-42. URL https://doi.org/10.1016/j.ejor.2011.01.046.
• [18] Bülbül K. A Hybrid shifting bottleneck-tabu serach heuristic for the job shop total weighted tardiness problem. Computers & Operations Research, 2011. 38:967-783. URL https://doi.org/10.1016/j.cor.2010.09.015.
• [19] González MA, González-Rodríguez I, Vela C, Varela R. An efficient hybrid evolutionary algorithm for scheduling with setup times and weighted tardiness minimization. Soft Computing, 2012. 16:2097-2113.doi:10.1007/s00500-012-0880-y.
• [20] Kuhpfahl J, Bierwirth C. A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective. Computers & Operations Research, 2016. 66:44-57. doi:10.1016/j.cor.2015.07.011.
• [21] Mouzon G, Yildirim MB, Twomey J. Operational methods for minimization of energy consumption of manufacturing equipment. International Journal of Production Research, 2007. 45 (18-19):4247-4271. URL https://doi.org/10.1080/00207540701450013.
• [22] Yildirim MB, Mouzon G. Single-Machine Sustainable Production Planning to Minimize Total Energy Consumption and Total Completion Time Using a Multiple Objective Genetic Algorithm. IEEE Transactions on Engineering Management, 2012. 59 (4):585-597. doi:10.1109/TEM.2011.2171055.
• [23] Shrouf F, Ordieres-Meré J, García-Sánchez A, Ortega-Mier M. Optimizing the production scheduling of a single machine to minimize total energy consumption costs. Journal of Cleaner Production, 2014. 67:197-207. doi:10.1016/j.jclepro.2013.12.024.
• [24] Liu Y, Tiwari A. An investigation into minimising total energy consumption and total completion time in a flexible job shop for recycling carbon fiber reinforced polymer. Procedia CIRP, 2015. 29:722-727. doi:10.1016/j.procir.2015.01.063.
• [25] Liu Q, Zhan M, Chekem FO, Shao X, Ying B, Sutherland JW. A hybrid fruit fly algorithm for solving flexible job-shop scheduling to reduce manufacturing carbon footprint. Journal of Cleaner Production, 2017. 168:668-678. doi:10.1016/j.jclepro.2017.09.037.
• [26] Yin L, Li X, Gao L, Lu C, Zhang Z. A novel mathematical model and multi-objective method for the low-carbon flexible job shop scheduling problem. Sustainable Computing: Informatics and Systems, 2017. 13:15-30. doi:10.1016/j.suscom.2016.11.002.
• [27] Wu X, Sun Y. A green scheduling algorithm for flexible job shop with energy-saving measures. Journal of Cleaner Production, 2018. 172:3249-3264. doi:10.1016/j.jclepro.2017.10.342.
• [28] Mokhtari H, Aliakbar H. An energy-efficient multi-objective optimization for flexible job shop scheduling problem. Computers & Chemical Engineering, 2017. 104:339-352. doi:10.1016/j.compchemeng.2017.05.004.
• [29] Piroozfard H, Wong KY, Wong WP. Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling using an improved multi-objective genetic algorithm. Resources, Conservation and Recycling, 2018. 128:267-283. doi:10.1016/j.resconrec.2016.12.001.
• [30] He Y, Li Y, Wu T, Sutherland JW. An energy-responsive optimization method for machine tool selection and operation sequence in flexible machining job shops. Journal of Cleaner Production, 2015. 87:245-254. doi:10.1016/j.jclepro.2014.10.006.
• [31] Zhang L, Tang Q, Wu Z, Wang F. Mathematical modeling and evolutionary generation of rule sets for energy-efficient flexible job shops. Energy, 2017. 138:210-227. doi:10.1016/j.energy.2017.07.005.
• [32] Zhang Y, Wang J, Liu Y. Game theory based real-time multi-objective flexible job shop scheduling considering environmental impact. Journal of Cleaner Production, 2017. 167:665-679. doi:10.1016/j.jclepro.2017.08.068.
• [33] Zhang H, Dai Z, Zhang W, Zhang S, Wang Y, Liu R. A new energy-aware flexible job shop scheduling method using modified biogeography-based optimization. Mathematical Problems in Engineering, 2017. Article ID 7249876:12 pages. doi:10.1155/2017/7249876.
• [34] 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-240. doi:10.1016/j.jmsy.2011.08.004.
• [35] Fang K, Uhan NA, Zhao F, Sutherland JW. Flow shop scheduling with peak power consumption constraints. Annals of Operations Research, 2013. 206 (1):115-145. doi:10.1007/s10479-012-1294-z.
• [36] Luo H, Du B, Huang GQ, Chen H, Li X. Hybrid flow shop scheduling considering machine electricity consumption cost. International Journal of Production Economics, 2013. 146 (2):423-439. doi:10.1016/j.ijpe.2013.01.028.
• [37] Dai M, Tang D, Giret A, Salido MA, Li W. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, 2013. 29:418-429.
• [38] Mansouri SA, Aktas E, Besikci U. Green scheduling of a two-machine flowshop: Trade-off between makespan and energy consumption. European Journal of Operational Research, 2016. 248 (3):772-788. doi:10.1016/j.ejor.2015.08.064.
• [39] Liu CH, Huang DH. Reduction of power consumption and carbon footprints by applying multi-objective optimisation via genetic algorithms. International Journal of Production Research, 2014. 52 (2):337-352. doi:10.1080/00207543.2013.825740.
• [40] Bruzzone A, Anghinolfi D, Paolucci M, Tonelli F. Energy-aware scheduling for improving manufacturing process sustainability: A mathematical model for flexible flow shops. CIRP Annals, 2012. 61 (1):459-462. doi:10.1016/j.cirp.2012.03.084.
• [41] Ji M, Wang JY, Lee WC. Minimizing resource consumption on uniform parallel machines with a bound on makespan. Computers & Operations Research, 2013. 40 (12):2970-2974. doi:10.1016/j.cor.2013.06.011.
• [42] Wu X, Che A. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega, 2019. 82:155-165. doi:10.1016/j.omega.2018.01.001.
• [43] Salido MA, Escamilla J, Barber F, Giret A. Rescheduling in job-shop problems for sustainable manufacturing systems. Journal of Cleaner Production, 2017. 162, Supplement:S121-S132. doi:10.1016/j.jclepro.2016.11.002.
• [44] Lei D, Guo X. An effective neighborhood search for scheduling in dual-resource constrained interval job shop with environmental objective. International Journal of Production Economics, 2015. 159:296-303. doi:10.1016/j.ijpe.2014.07.026.
• [45] Liu Y, Dong H, Lohse N, Petrovic S, Gindy N. An investigation into minimising total energy consumption and total weighted tardiness in job shops. Journal of Cleaner Production, 2014. 65:87-96.
• [46] May G, Stahl B, Taisch M, Prabhu V. Multi-objective genetic algorithm for energy-efficient job shop scheduling. International Journal of Production Research, 2015. 53(23):7071-7089.
• [47] Zhang R, Chiong R. Solving the energy-efficient job shop scheduling problem: a multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption. Journal of Cleaner Production, 2016. 112:3361-3375.
• [48] Liu Y, Dong H, Lohse N, Petrovic S. A multi-objective genetic algorithm for optimisation of energy consumption and shop floor production performance. International Journal of Production Economics, 2016. 179:259-272. doi:10.1016/j.ijpe.2016.06.019.
• [49] Salido MA, Escamilla J, Giret A, Barber F. A genetic algorithm for energy-efficiency in job shop scheduling. The International Journal of Advanced Manufacturing Technology, 2016. 85(5-8):1303-1314. doi:10.1007/s00170-015-7987-0.
• [50] González MA, Oddi A, Rasconi R. A multi-objective memetic algorithm for solving job shops with a non-regular energy cost. In: Proceedings of the 11th Workshop on Constraint Satisfaction Techniques for Planning and Scheduling (COPLAS-2016). 2016 pp. 15-24.
• [51] Oddi A, Rasconi R, González MA. A constraint programming approach for the energy-efficient job shop scheduling problem. In: Proceedings of the 8th Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA-2017). 2017 pp. 158-172.
• [52] Artigues C, Lopez P. Energetic reasoning for energy-constrained scheduling with a continuous resource. Journal of Scheduling, 2015. 18(3):225-241. doi:10.1007/s10951-014-0404-y.
• [53] Kim S, Meng C, Son YJ. Simulation-based machine shop operations scheduling system for energy cost reduction. Simulation Modelling Practice and Theory, 2017. 77:68-83. doi:10.1016/j.simpat.2017.05.007.
• [54] Grimes D, Ifrim G, O’Sullivan B, Simonis H. Analyzing the impact of electricity price forecasting on energy cost-aware scheduling. Sustainable Computing: Informatics and Systems, 2014. 4(4):276-291.
• [55] Paolucci M, Anghinolfi D, Tonelli F. Facing energy-aware scheduling: a multi-objective extension of a scheduling support system for improving energy efficiency in a moulding industry. Soft Computing, 2017. 21(13):3687-3698. doi:10.1007/s00500-015-1987-8.
• [56] Baker K. Introduction to Sequencing and Scheduling. Wiley, 1974.
• [57] Bürgy R, Bülbül K. The job shop scheduling problem with convex costs. European Journal of Operational Research, 2018. 268(1):82-100. doi:10.1016/j.ejor.2018.01.027.
• [58] Van Laarhoven P, Aarts E, Lenstra K. Job shop scheduling by simulated annealing. Operations Research, 1992. 40:113-125.
• [59] Brandimarte P, Maiocco M. Job shop scheduling with a non-regular objective: a comparison of neighbourhood structures based on a sequencing/timing decomposition. International Journal of Production Research, 1999. 37(8):1697-1715.
• [60] Bierwirth C. A Generalized Permutation Approach to Jobshop Scheduling with Genetic Algorithms. OR Spectrum, 1995. 17:87-92.
• [61] Liefooghe A, Humeau J, Mesmoudi S, Jourdan L, Talbi EG. On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems. Journal of Heuristics, 2012. 18(2):317-352. doi:10.1007/s10732-011-9181-3.
• [62] Knowles JD, Corne DW. Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy. Evolutionary Computation, 2000. 8(2):149-172. doi:10.1162/106365600568167.
• [63] Paquete L, Schiavinotto T, Stützle T. On local optima in multiobjective combinatorial optimization problems. Annals of Operations Research, 2007. 156:83-97. doi:10.1007/s10479-007-0230-0.
• [64] Lara A, Sánchez G, Coello Coello CA, Schütze O. HCS: A New Local Search Strategy for Memetic Multiobjective Evolutionary Algorithms. IEEE Transactions on Evolutionary Computation, 2010. 14(1):112-132. doi:10.1109/TEVC.2009.2024143.
• [65] Ishibuchi H, Hitotsuyanagi Y, Tsukamoto N, Nojima Y. Use of biased neighborhood structures in multiobjective memetic algorithms. Soft Computing, 2009. 13(8-9):795-810. doi:10.1007/s00500-008-0352-6.
• [66] Jaszkiewicz A. Do multiple-objective metaheuristics deliver on their promises? A computational experiment on the set-covering problem. IEEE Transactions on Evolutionary Computation, 2003. 7(2):133-143. doi:10.1109/TEVC.2003.810759.
• [67] Papadimitriou C, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. Dover Books on Computer Science. Dover Publications, 1982. ISBN 9780486402581. URL https://books.google.it/books?id=u1RmDoJqkF4C.
• [68] Sakkout H, Wallace M. Probe Backtrack Search for Minimal Perturbation in Dynamic Scheduling. Constraints, 2000. 5(4):359-388. doi:10.1023/A:1009856210543.
• [69] Giagkiozis I, Purshouse RC, Fleming PJ. Generalized Decomposition. In: Purshouse RC, Fleming PJ, Fonseca CM, Greco S, Shaw J (eds.), Evolutionary Multi-Criterion Optimization. Springer Berlin Heidelberg, Berlin, Heidelberg. ISBN 978-3-642-37140-0, 2013 pp. 428-442. doi:10.1007/978-3-642-37140-0.
• [70] Miettinen K. Nonlinear Multiobjective Optimization. International Series in Operations Research & Management Science. Springer US, 1998. ISBN 978-0-7923-8278-2.
• [71] Palacios JJ, Derbel B. On Maintaining Diversity in MOEA/D: Application to a Biobjective Combinatorial FJSP. In: GECCO’15 Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. ACM, 2015 pp. 719-726. doi:10.1145/2739480.2754774.
• [72] Li H, Zhang Q. Multiobjective Optimization Problems With Complicated Pareto Sets, MOEA/D and NSGA-II. Evolutionary Computation, IEEE Transactions on, 2009. 13 (2):284-302. doi:10.1109/TEVC.2008.925798.
• [73] Marquet G, Derbel B, Liefooghe A, Talbi EG. Shake Them All! Rethinking Selection and Replacement in MOEA/D. In: Bartz-Beielstein T, Branke J, Filipi B, Smith J (eds.), Parallel Problem Solving from Nature PPSN XIII, volume 8672 of Lecture Notes in Computer Science, pp. 641-651. Springer. ISBN 978-3-319-10761-5, 2014. doi:10.1007/978-3-319-10762-2\_63.
• [74] Apt K. Principles of Constraint Programming. Cambridge University Press, New York, NY, USA, 2003. ISBN 0521825830.
• [75] Vilím P, Barták R, Cepek O. Unary Resource Constraint with Optional Activities. In: Principles and Practice of Constraint Programming - CP 2004, 10th International Conference, CP 2004, Toronto, Canada, September 27 - October 1, 2004, Proceedings. 2004 pp. 62-76.
• [76] Le Pape C, Baptiste P, Nuijten W. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Springer Science+Business Media, New York, NY, USA, 2001. ISBN 978-1-4613-5574-8.
• [77] Laborie P. Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results. Artificial Intelligence, 2003. 143 (2):151-188.
• [78] IBM. IBM CPLEX Optimization Studio V12.7.1. URL https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.1/ilog.odms.studio.help/Optimization_Studio/topics/COS_home.html.
• [79] Fisher H, Thompson G. Probabilistic learning combinations of local job-shop scheduling rules. In: Muth J, Thompson G (eds.), Industrial Scheduling, pp. 225-251. Prentice Hall, 1963.
• [80] Lawrence S. Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement). Graduate School of Industrial Administration, Carnegie-Mellon University, 1984.
• [81] Applegate D, Cook W. A computational study of the job-shop scheduling problem. ORSA Journal of Computing, 1991. 3:149-156.
• [82] Baker KR. Sequencing rules and due-date assignments in a job shop. Management Science, 1984. 30 (9):1093-1104. doi:10.1287/mnsc.30.9.1093.
• [83] Sabuncuoglu I, Bayiz M. Job shop scheduling with beam search. European Journal of Operational Research, 1999. 118 (2):390-412.
• [84] Zitzler E, Thiele L. Multiobjective optimization using evolutionary algorithms — A comparative case study. In: Parallel Problem Solving from Nature — PPSN V Proceedings, pp. 292-301. Springer Berlin Heidelberg, 1998.
• [85] Parkinson S, Longstaff A, Fletcher S, Vallati M. On the Exploitation of Automated Planning for Reducing Machine Tools Energy Consumption Between Manufacturing Operations. In: Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling (ICAPS-2017). AAAI Press, 2017 pp. 400-408.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).

Identyfikatory

DOI

10.3233/FI-2019-1811