Abstract
The rapid growth of electricity demand has led governments around the world to implement energy-conscious policies, such as time-of-use tariffs. The manufacturing sector can embrace these policies by implementing an innovative scheduling system to reduce its energy consumption. Therefore, this study addresses bi-objective job-shop scheduling with total weighted tardiness and electricity cost minimization under time-of-use tariffs. The problem can be decomposed into two sub-problems, operation sequencing and start time determination. To solve this problem, we propose a distributed-elite local search based on a genetic algorithm that uses local improvement strategies based on the distribution of elites. Specifically, chromosome encoding uses two lines of gene representation corresponding to the operation sequence and start time. We propose a decoding method to obtain a schedule that incorporates operation sequencing and start time. A perturbation scheme to reduce electricity costs was developed. Finally, a local search framework based on the distribution of elites is used to guide the selection of individuals and the determination of perturbation. Comprehensive numerical experiments using benchmark data from the literature demonstrate that the proposed method is more effective than NSGA-II, MOEA/D, and SPEA2. The results presented in this work may be useful for the manufacturing sector to adopt the time-of-use tariffs policy.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Kucukvar M, Cansev B, Egilmez G, Onat NC, Samadi H (2016) Energy-climate-manufacturing nexus: new insights from the regional and global supply chains of manufacturing industries. Appl Energy 184:889–904. https://doi.org/10.1016/j.apenergy.2016.03.068
Okajima S, Okajima H (2013) Analysis of energy intensity in Japan. Energy Policy 61:574–586. https://doi.org/10.1016/j.enpol.2013.05.117
Cappers P, Goldman C, Kathan D (2010) Demand response in U.S. electricity markets: empirical evidence. Energy 35:1526–1535. https://doi.org/10.1016/j.energy.2009.06.029
Mouzon G, Yildirim MB, Twomey J (2007) Operational methods for minimization of energy consumption of manufacturing equipment. Int J Prod Res 45:4247–4271. https://doi.org/10.1080/00207540701450013
Che A, Wu X, Peng J, Yan P (2017) Energy-efficient bi-objective single-machine scheduling with power-down mechanism. Comput Oper Res 85:172–183. https://doi.org/10.1016/j.cor.2017.04.004
Tang D, Min D (2015) Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem. Chin J Mech Eng 28(5):1048–1055. https://doi.org/10.3901/cjme.2015.0617.082
Zhang R, Chiong R (2016) Solving the energy-efficient job shop scheduling problem: a multiobjective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption. J Clean Prod 112:3361–3375. https://doi.org/10.1016/j.jclepro.2015.09.097
Gahm C, Denz F, Dirr M, Tuma A (2016) Energy-efficient scheduling in manufacturing companies: a review and research framework. Eur J Oper Res 248:744–757. https://doi.org/10.1016/j.ejor.2015.07.017
Kurniawan B, Gozali AA, Weng W, Fujimura S (2019) A mix integer programming model for bi-objective single machine with total weighted tardiness and electricity cost under time-of-use tariffs. In: Proceedings of 2018 IEEE international conference on industrial engineering & engineering management, pp 137–141. https://doi.org/10.1109/IEEM.2018.8607420
Moon JY, Shin K, Park J (2013) Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency. Int J Adv Manuf Technol 68:523–535. https://doi.org/10.1007/s00170-013-4749-8
Shrouf F, Ordieres-Meré J, García-Sánchez A, Ortega-Mier M (2014) Optimizing the production scheduling of a single machine to minimize total energy consumption costs. J Clean Prod 67:197–207. https://doi.org/10.1016/j.jclepro.2013.12.024
Zhang H, Zhao F, Fang K, Sutherland JW (2014) Energy-conscious flow shop scheduling under time-of-use electricity tariffs. CIRP Ann Manuf Technol 63:37–40. https://doi.org/10.1016/j.cirp.2014.03.011
Wang S, Zhu Z, Kan Fang, Chu F, Chu C (2018) Scheduling on a two-machine permutation flow shop under time-of-use electricity tariffs. Int J Prod Res 56:3173–3187. https://doi.org/10.1080/00207543.2017.1401236
Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117–129
Shena L, Dauzère-Pérès S, Neufeldd JS (2018) Solving the flexible job shop scheduling problem with sequence-dependent setup times. Eur J Oper Res 265:503–516. https://doi.org/10.1016/j.ejor.2017.08.021
Balas E, Vazacopoulos A (1998) Guided local search with shifting bottleneck for job shop scheduling. Manag Sci 44(2):262–275
Brucker P, Jurisch B, Sievers B (1994) A branch and bound algorithm for the job-shop scheduling problem. Discrete Appl Math 49:107–127. https://doi.org/10.1016/0166-218X(94)90204-6
Artigues C, Feillet D (2008) A branch and bound method for the job-shop problem with sequence-dependent setup times. Ann Oper Res 159:135–159. https://doi.org/10.1007/s10479-007-0283-0
Mahnam M, Moslehi G (2009) A branch-and-bound algorithm for minimizing the sum of maximum earliness and tardiness with unequal release times. Eng Optim 41(6):521–536
Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manag Sci 34(3):391–401
Giffler B, Thompson GL (1960) Algorithms for solving production-scheduling problems. Oper Res 8(4):487–503
Amirghasemi M, Zamani R (2015) An effective asexual genetic algorithm for solving the job shop scheduling problem. Comput Ind Eng 83:123–138. https://doi.org/10.1016/j.cie.2015.02.011
Zhang CY, Li P, Rao Y, Guan Z (2008) A very fast TS/SA algorithm for the job shop scheduling problem. Comput Oper Res 35(1):282–294
Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manag Sci 42:797–813
Zhang CY, Li PG, Guan Z, Rao YQ (2007) A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Comput Oper Res 34(11):3229–3242
Kundakci N, Kulak O (2016) Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem. Comput Ind Eng 96:31–51. https://doi.org/10.1016/j.cie.2016.03.011
Lin TL, Horng SJ, Kao TW, Chen YH, Run RS, Chen RJ, Lai JL, Kuo IH (2010) An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Syst Appl 37(3):2629–2636. https://doi.org/10.1016/j.eswa.2009.08.015
Huang RH, Yu TH (2017) An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting. Appl Soft Comput 57:642–656. https://doi.org/10.1016/j.asoc.2017.04.062
Sharma N, Sharma H, Sharma A (2018) Beer froth artificial bee colony algorithm for job-shop scheduling problem. Appl Soft Comput 68:507–524. https://doi.org/10.1016/j.asoc.2018.04.001
Pinedo M, Singer M (1999) A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Nav Res Logist 46:1–17
Asano M, Ohta H (2002) A heuristic for job shop scheduling to minimize total weighted tardiness. Comput Ind Eng 42:137–147
Essafi I, Mati Y, Dauzère-Pérès S (2008) A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Comput Oper Res 35:2599–2616
Kuhpfal J, Bierwirth C (2016) A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective. Comput Oper Res 66:44–57. https://doi.org/10.1016/j.cor.2015.07.011
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6:182–197. https://doi.org/10.1109/4235.996017
Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11:712–731. https://doi.org/10.1109/TEVC.2007.892759
Dell’Amico M, Trubian M (1993) Applying tabu search to the job-shop scheduling problem. Ann Oper Res 41:231–252
Monyei CG, Adewumi AO (2018) Integration of demand side and supply side energy management resources for optimal scheduling of demand response loads—South Africa in focus. Electr Power Syst Res 158:92–104. https://doi.org/10.1016/j.epsr.2017.12.033
Craparo EM, Sprague JG (2019) Integrated supply- and demand-side energy management for expeditionary environmental control. Appl Energy 233–234:352–366. https://doi.org/10.1016/j.apenergy.2018.09.220
Bagal HA, Soltanabad YN, Dadjuo M, Wakil K, Ghadimi N (2018) Risk-assessment of photovoltaic-wind-battery-grid based large industrial consumer using information gap decision theory. Sol Energy 169:343–352. https://doi.org/10.1016/j.solener.2018.05.003
Abedinia O, Zareinejad M, Doranehgard MH, Fathi G, Noradin G (2019) Optimal offering and bidding strategies of renewable energy based large consumer using a novel hybrid robust-stochastic approach. J Clean Prod 215:878–889. https://doi.org/10.1016/j.jclepro.2019.01.085
Sadovskaia K, Bogdanov D, Honkapuro S, Breyer C (2019) Power transmission and distribution losses—a model based on available empirical data and future trends for all countries globally. Int J Electr Power Energy Syst 107:98–109. https://doi.org/10.1016/j.ijepes.2018.11.012
Khodaei H, Hajiali M, Darvishan A, Sepehr M, Ghadimi N (2018) Fuzzy-based heat and power hub models for cost-emission operation of an industrial consumer using compromise programming. Appl Therm Eng 137:395–405. https://doi.org/10.1016/j.applthermaleng.2018.04.008
Gao W, Darvishan A, Toghani M, Mohammadi M, Abedinia O, Ghadimi N (2019) Different states of multi-block based forecast engine for price and load prediction. Int J Electr Power Energy Syst 104:423–435. https://doi.org/10.1016/j.ijepes.2018.07.014
Ghadimi N, Akbarimajd A, Shayeghi H, Abedinia O (2019) Two stage forecast engine with feature selection technique and improved meta-heuristic algorithm for electricity load forecasting. Energy 161:130–142. https://doi.org/10.1016/j.energy.2018.07.088
Saeedi M, Moradi M, Hosseini M, Emamifar A, Ghadimi N (2019) Robust optimization based optimal chiller loading under cooling demand uncertainty. Appl Therm Eng 148:1081–1091. https://doi.org/10.1016/j.applthermaleng.2018.11.122
Chandramitasari W, Kurniawan B, Fujimura S (2018) Building deep neural network model for short term electricity consumption forecasting. In: Proceedings 2018 international symposium on advanced intelligent informatics (SAIN), pp 43–48. https://doi.org/10.1109/SAIN.2018.8673340
Kurniawan B, Gozali AA, Weng W, Fujimura S (2018) A genetic algorithm for unrelated parallel machine scheduling minimizing makespan cost and electricity cost under time-of-use (TOU) tariffs with job delay mechanism. In: Proceedings of 2017 IEEE international conference on industrial engineering and engineering management, pp 583–587. https://doi.org/10.1109/IEEM.2017.8289958
Mouzon G, Yildirim MB (2008) A framework to minimise total energy consumption and total tardiness on a single machine. Int J Sustain Eng 1(2):105–116. https://doi.org/10.1080/19397030802257236
Aghelinejad MM, Ouazene Y, Yalaoui A (2019) Complexity analysis of energy-efficient single machine scheduling problems. Oper Res Perspect 6:100–105. https://doi.org/10.1016/j.orp.2019.100105
Li K, Zhang X, Leung JYT, Yang SL (2016) Parallel machine scheduling problems in green manufacturing industry. J Manuf Syst 38:98–106. https://doi.org/10.1016/j.ejor.2015.08.064
Abikarram JB, McConky K, Proano R (2019) Energy cost minimization for unrelated parallel machine scheduling under real time and demand charge pricing. J Clean Prod 208:232–242. https://doi.org/10.1016/j.epsr.2017.12.033
Yan J, Li L, Zhao F, Zhang F, Zhao Q (2016) A multi-level optimization approach for energy-efficient flexible flow shop scheduling. J Clean Prod 137:1543–1552. https://doi.org/10.1016/j.jclepro.2016.06.161
Mansouri SA, Aktas E, Besikci U (2016) Green scheduling of a two-machine flowshop: trade-off between makespan and energy consumption. Eur J Oper Res 248:772–788. https://doi.org/10.1016/j.ejor.2015.08.064
Jiang T, Zhang C, Zhu H, Den G (2018) Energy-efficient scheduling for a job shop using Grey Wolf optimization algorithm with double-searching mode. Math Problems Eng. https://doi.org/10.1155/2018/8574892
Corominas A, García-Villoria A, González NA, Pastor R (2019) A multistage graph-based procedure for solving a just-in-time flexible job-shop scheduling problem with machine and time-dependent processing costs. J Oper Res Soc 70(4):620–633. https://doi.org/10.1080/01605682.2018.1452537
Bülbül K (2011) A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem. Comput Oper Res 38(6):967–983. https://doi.org/10.1016/j.cor.2010.09.015
Mati Y, Dauzère-Pérès S, Lahlou C (2011) A general approach for optimizing regular criteria in the job-shop scheduling problem. Eur J Oper Res 212:33–42. https://doi.org/10.1016/j.ejor.2011.01.046
Bierwirth C, Kuhpfal J (2017) Extended GRASP for the job shop scheduling problem with total weighted tardiness objective. Eur J Oper Res 261:835–848. https://doi.org/10.1016/j.ejor.2017.03.030
González MA, González-Rodríguez I, Vela CR, Varela R (2012) An efficient hybrid evolutionary algorithm for scheduling with setup times and weighted tardiness minimization. Soft Comput 16:2097–2113. https://doi.org/10.1007/s00500-012-0880-y
Masmoudi O, Delorme X, Gianessi P (2019) Job-shop scheduling problem with energy consideration. Int J Prod Econ 216:12–22. https://doi.org/10.1016/j.ijpe.2019.03.021
May G, Stahl B, Taisch M, Prabhu V Vittal (2015) Multi-objective genetic algorithm for energy-efficient job shop scheduling. Int J Prod Res 5:7071–7089. https://doi.org/10.1080/00207543.2015.1005248
Liu Y, Dong H, Lohse N, Petrovic S, Gindy N (2014) An investigation into minimising total energy consumption and total weighted tardiness in job shops. J Clean Prod 65:87–96. https://doi.org/10.1155/2018/8574892
Salido MA, Escamilla J, Giret A, Barber F (2016) A genetic algorithm for energy-efficiency in job-shop scheduling. Int J Adv Manuf Technol 85:1303–1314. https://doi.org/10.1007/s00170-015-7987-0
Fang K, Uhan NA, Zhao F, Sutherland JW (2016) Scheduling on a single machine under time-of-use electricity tariffs. Ann Oper Res 238:199–227. https://doi.org/10.1007/s10479-015-2003-5
Che A, Zeng Y, Lyu K (2016) An efficient greedy insertion heuristic for energy-conscious single machine scheduling problem under time-of-use electricity tariffs. J Clean Prod 129:565–577. https://doi.org/10.1016/j.jclepro.2016.03.150
Aghelinejad MM, Ouazene Y, Yalaoui A (2018) Production scheduling optimisation with machine state and time-dependent energy costs. Int J Prod Res 56:5558–5575. https://doi.org/10.1080/00207543.2017.1414969
Cheng J, Chu F, Liu M, Wue P, Xia W (2017) Bi-criteria single-machine batch scheduling with machine on/off witching under time-of-use tariffs. Comput Ind Eng 112:721–734. https://doi.org/10.1016/j.cie.2017.04.026
Sharma A, Zhao F, Sutherland JW (2015) Econological scheduling of manufacturing enterprise operating under a time-of-use electricity tariff. J Clean Prod 108:256–270. https://doi.org/10.1016/j.jclepro.2015.06.002
Koo J, Kim BI (2016) Some comments on “Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency”. Int J Adv Manuf Technol 86:2803–2806. https://doi.org/10.1007/s00170-016-8375-0
Kurniawan B, Chandramitasari W, Gozali AA, Weng W, Fujimura S (2020) Triple-chromosome genetic algorithm for unrelated parallel machine scheduling under time-of-use tariffs. IEEJ Trans Electr Electron Eng 15:208–217. https://doi.org/10.1002/tee.23047
Ding JY, Song S, Zhang R, Chiong R (2016) Parallel machine scheduling under time-of-use electricity prices: new models and optimization approaches. IEEE Trans Autom Sci Eng 13:1138–1154. https://doi.org/10.1109/TASE.2015.2495328
Che A, Zhang S, Wu X (2017) Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. J Clean Prod 156:688–697. https://doi.org/10.1016/j.jclepro.2017.04.018
Cheng J, Chu F, Zhou MC (2018) An improved model for parallel machine scheduling under time-of-use electricity price. IEEE Trans Autom Sci Eng 15:896–899. https://doi.org/10.1109/TASE.2016.2631491
Zeng YZ, Che A, Wu X (2018) Bi-objective scheduling on uniform parallel machines considering electricity cost. Eng Optim 50:19–36. https://doi.org/10.1080/0305215X.2017.1296437
Manne AS (1960) On the job-shop scheduling. Oper Res 8:219–223
Liu M, Yang X, Chu F, Zhang J, Chu C (2019) Energy-oriented bi-objective optimization for the tempered glass scheduling. Omega 90:101995. https://doi.org/10.1016/j.omega.2018.11.004
Cheng R, Gen M, Tsujimura Y (1996) A tutorial survey of job shop scheduling problem using genetic algorithm—I. Representation. Comput Ind Eng 30:983–997
Veldhuizen DAV (1999) Multiobjective evolutionary algorithms: classifications, analyses, and new innovations. Dissertation, Department of Electrical and Computer Engineering, Graduate School of Engineering, Air Force Institute of Technology, Wright-Patterson AFB
Beasley JE (2018) OR-Library. http://people.brunel.ac.uk/mastjib/jeb/info.html. 25 Nov 2018
Taillard E (2019) Scheduling instances. http://mistic.heig-vd.ch/taillard. 25 June 2019
Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength pareto evolutionary algorithm. Technical report, Swiss Federal Institute of Technology (ETH), Zurich
Montgomery DC (2013) Design and analysis of experiments, 8th edn. Wiley, Hoboken
JASP Team (2020). JASP (Version 0.12.2)[Computer software]
Acknowledgements
The authors wish to thank the anonymous referees for their constructive feedback. The authors also thank all who provided support to this research. This research is supported by the Indonesia Endowment Fund for Education (Lembaga Pengelola Dana Pendidikan LPDP Indonesia).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Kurniawan, B., Song, W., Weng, W. et al. Distributed-elite local search based on a genetic algorithm for bi-objective job-shop scheduling under time-of-use tariffs. Evol. Intel. 14, 1581–1595 (2021). https://doi.org/10.1007/s12065-020-00426-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12065-020-00426-4