A Memetic Algorithm for an Energy-Costs-Aware Flexible Job-Shop Scheduling Problem

Authors: Christian Böning, Henrik Prinzhorn, Eric C. Hund, Malte Stonis

Abstract:

In this article, the flexible job-shop scheduling problem is extended by consideration of energy costs which arise owing to the power peak, and further decision variables such as work in process and throughput time are incorporated into the objective function. This enables a production plan to be simultaneously optimized in respect of the real arising energy and logistics costs. The energy-costs-aware flexible job-shop scheduling problem (EFJSP) which arises is described mathematically, and a memetic algorithm (MA) is presented as a solution. In the MA, the evolutionary process is supplemented with a local search. Furthermore, repair procedures are used in order to rectify any infeasible solutions that have arisen in the evolutionary process. The potential for lowering the real arising costs of a production plan through consideration of energy consumption levels is highlighted.

Keywords: Energy costs, flexible job-shop scheduling, memetic algorithm, power peak.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1131387

References:

[1] Pinedo M (2012) Scheduling: Theory, Algorithms and Systems. 4th edn. Springer, New York, Heidelberg, London.
[2] Yazdani M, Amiri M, Zandieh M (2010) Flexible Job-shop Scheduling with Parallel Variable Neighborhood Search Algorithm. Expert Syst Appl 37:678–687.
[3] Garey M R, Johnson D S, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117–129.
[4] BMWI - German Federal Ministry for Economic Affairs and Energy (2014) Entwicklung von Energiepreisen und Preisindizes zu nominalen Preisen Deutschland. http://www.bmwi.de/BMWi/Redaktion/Binaer/Energiedaten/energiepreise-und-energiekosten1-entwicklung-energiepreise-preisindizes,property=blob,bereich=bmwi2012,sprache=de,rwb=true.xls 12.01.2015http://www.bmwi.de/BMWi/Redaktion/Binaer/Energiedaten/energiepreise-und-energiekosten1-entwicklung-energiepreise preisindizes,property=blob,bereich=bmwi2012,sprache=de,rwb=true.xls. Accessed 07 April 2016.
[5] 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. Robot Cim-Int Manuf 29:418-429.
[6] Luo H, Du B, Huang G Q, Chen H, Li X (2013) Hybrid flow shop scheduling considering machine electricity consumption cost. Int J Prod Econ 146: 423-439.
[7] Moon J-Y, Park J (2014) Smart production scheduling with time-dependent and machine-dependent electricity cost by considering distributed energy resources and energy storage. Int J Prod Res 52:3922-3939.
[8] Fink R (2013) A priority rule based multi criteria scheduling framework for energy efficiency aware detailed production planning. 39th Annual Conference of the IEEE Industrial-Electronics-Society, Vienna, 39:7508-7512.
[9] Wiendahl H-P (1995) Load-Oriented Manufacturing Control. Springer, Berlin, Heidelberg, New York.
[10] Nyhuis P, Wiendahl H-P (2009) Fundamentals of Production Logistics. Springer, Berlin, Heidelberg.
[11] Gutenberg E (1951) Grundlagen der Betriebswirtschaftslehre. Volume 1: Die Produktion. 1st edn. Berlin.
[12] Brucker P, Schlie R (1990) Job-shop scheduling with multi-purpose machines. Computing 45:369–375.
[13] Pezzella F, Morganti G, Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 35:3202–3212.
[14] Wang L, Zhou G, Xu Y, Wang S, Liu M (2012) An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Technol 60:303–315.
[15] Xia W, Wu Z (2005) An effective hybrid optimization approach for multiobjective flexible job-shop scheduling problem. Comput Ind Eng 48:409–425.
[16] Yuan Y, Xu H, Yang J (2013) A hybrid harmony search algorithm for the flexible job shop scheduling problem. Appl Soft Comput 13:3259–3272.
[17] Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 41:157–183.
[18] Paulli J (1995) A hierarchical approach for the FMS scheduling problem. Eur J Oper Res 86:32–42.
[19] Dauzére-Pérés S, Paulli J (1997) An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Ann Oper Res 70:281–306.
[20] Mastrolilli M, Gambardella L M (2000) Effective neighborhood functions for the flexible job shop problem. J Sched 3:3–20.
[21] Chen H, Ihlow J, Lehmann C (1999) Agenetic algorithm for flexible Job-shop scheduling. IEEE Int conf robot, Detroit, 1120–1125.
[22] Kacem I, Hammadi S, Borne P (2002) Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE T Syst Man Cyb 32:1–13.
[23] Zhang H P, Gen M (2005) Multistage-based genetic algorithm for flexible jobshop scheduling problem. Journal of Complexity International 11:223–232.
[24] Gao J, Sun L, Gen M (2008) A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Comput Oper Res 35:2892–2907.
[25] Al-Hinai N, ElMekkawy T Y (2011) An Efficient Hybridized Genetic Algorithm Architecture for the Flexible Job Shop Scheduling Problem. Flexible Services and Manufacturing Journal 23:64–85.
[26] Raeesi M N, Kobti Z (2012) A memetic algorithm for job shop scheduling using a critical-path-based local search heuristic. Memetic Computing 4:231–245.
[27] Gutiérrez C, García-Magariño I (2011) Modular design of a hybrid genetic algorithm for a flexible job-shop scheduling problem. Knowl-Based Syst 24:102–112.
[28] Jiang J, Wen M, Ma K, Long X, Li J (2011) Hybrid Genetic Algorithm for Flexible Job-Shop Scheduling with Multi-objective. Journal of Information & Computational Science 8:2197-2205.
[29] Rager M (2008) Energieorientierte Produktionsplanung. GWV Fachverlage, Wiesbaden.
[30] Rager M, Gahm C, Denz F (2015) Energy-oriented scheduling based on Evolutionary Algorithms. Comput Oper Res 54:218-231.
[31] Fang K, Uhan N, Zhao F, Sutherland J W (2011) A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. J Manuf Syst 30:234-240.
[32] Bruzzone A A G, Anghinolfi D, Paolucci M, Tonellia F (2012) Energy-aware scheduling for improving manufacturing process sustainability: a mathematical model for flexible flow shops. CIRP Ann-Manuf Techn 61:459-462.
[33] Wiehndahl H-P (2014) Betriebsorganisation für Ingenieure. 8th edn. Hanser, München, Wien.
[34] Weinert N, Chiotellis S, Seliger G (2011) Methodology for planning and operating energy-efficient production systems. CIRP Ann-Manuf Techn 60:41-44.
[35] Bierwirth C (1995) A generalized permutation approach to job shop scheduling with genetic algorithms. OR Spektrum 17:87-92.
[36] Eiben A E, Smith J E (2003) Introduction to Evolutionary Computing. Springer, Berlin, Heidelberg.
[37] Zäpfel G, Braune R, Bögl M (2010) Metaheuristic Search Concepts. Springer, Berlin, Heidelberg.
[38] Tawarmalani M, Sahinidis N V (2005) A polyhedral branch-and-cut approach to global optimization. Math Program 103:225-249.