Top

Evolutionary Intelligence

Published in:

31-05-2020 | Research Paper

Distributed-elite local search based on a genetic algorithm for bi-objective job-shop scheduling under time-of-use tariffs

Authors: Bobby Kurniawan, Wen Song, Wei Weng, Shigeru Fujimura

Published in: Evolutionary Intelligence | Issue 4/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Self-adaptive learning for hybrid genetic algorithms

next article Chaotic multi verse optimizer based fuzzy logic controller for frequency control of microgrids

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

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.068CrossRef

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.117CrossRefMATH

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.029CrossRef

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/00207540701450013CrossRefMATH

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.004MathSciNetCrossRefMATH

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.082CrossRef

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.097CrossRef

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.017MathSciNetCrossRefMATH

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

10.

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-8CrossRef

11.

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.024CrossRef

12.

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.011CrossRef

13.

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.1401236CrossRef

14.

Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117–129MathSciNetCrossRef

15.

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.021MathSciNetCrossRef

16.

Balas E, Vazacopoulos A (1998) Guided local search with shifting bottleneck for job shop scheduling. Manag Sci 44(2):262–275CrossRef

17.

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-6MathSciNetCrossRefMATH

18.

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-0MathSciNetCrossRefMATH

19.

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–536MathSciNetCrossRef

20.

Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manag Sci 34(3):391–401MathSciNetCrossRef

21.

Giffler B, Thompson GL (1960) Algorithms for solving production-scheduling problems. Oper Res 8(4):487–503MathSciNetCrossRef

22.

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.011CrossRef

23.

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–294MathSciNetCrossRef

24.

Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manag Sci 42:797–813CrossRef

25.

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–3242MathSciNetCrossRef

26.

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.011CrossRef

27.

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.015CrossRef

28.

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.062CrossRef

29.

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.001CrossRef

30.

Pinedo M, Singer M (1999) A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Nav Res Logist 46:1–17MathSciNetCrossRef

31.

Asano M, Ohta H (2002) A heuristic for job shop scheduling to minimize total weighted tardiness. Comput Ind Eng 42:137–147CrossRef

32.

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–2616MathSciNetCrossRef

33.

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.011MathSciNetCrossRefMATH

34.

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.996017CrossRef

35.

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.892759CrossRef

36.

Dell’Amico M, Trubian M (1993) Applying tabu search to the job-shop scheduling problem. Ann Oper Res 41:231–252CrossRef

37.

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.033CrossRef

38.

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.220CrossRef

39.

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.003CrossRef

40.

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.085CrossRef

41.

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.012CrossRef

42.

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.008CrossRef

43.

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.014CrossRef

44.

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.088CrossRef

45.

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.122CrossRef

46.

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

47.

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

48.

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/19397030802257236CrossRef

49.

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.100105MathSciNetCrossRef

50.

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.064CrossRef

51.

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.033CrossRef

52.

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.161CrossRef

53.

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.064MathSciNetCrossRefMATH

54.

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/8574892CrossRef

55.

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.1452537CrossRef

56.

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.015MathSciNetCrossRefMATH

57.

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.046MathSciNetCrossRefMATH

58.

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.030MathSciNetCrossRefMATH

59.

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-yCrossRef

60.

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.021CrossRef

61.

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.1005248CrossRef

62.

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/8574892CrossRef

63.

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-0CrossRef

64.

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-5MathSciNetCrossRefMATH

65.

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.150CrossRef

66.

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.1414969CrossRef

67.

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.026CrossRef

68.

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.002CrossRef

69.

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-0CrossRef

70.

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.23047CrossRef

71.

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.2495328CrossRef

72.

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.018CrossRef

73.

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.2631491CrossRef

74.

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.1296437MathSciNetCrossRef

75.

Manne AS (1960) On the job-shop scheduling. Oper Res 8:219–223MathSciNetCrossRef

76.

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.004CrossRef

77.

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–997CrossRef

78.

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

79.

Beasley JE (2018) OR-Library. http://people.brunel.ac.uk/mastjib/jeb/info.html. 25 Nov 2018

80.

Taillard E (2019) Scheduling instances. http://mistic.heig-vd.ch/taillard. 25 June 2019

81.

Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength pareto evolutionary algorithm. Technical report, Swiss Federal Institute of Technology (ETH), Zurich

82.

Montgomery DC (2013) Design and analysis of experiments, 8th edn. Wiley, Hoboken

83.

JASP Team (2020). JASP (Version 0.12.2)[Computer software]

Title: Distributed-elite local search based on a genetic algorithm for bi-objective job-shop scheduling under time-of-use tariffs
Authors: Bobby Kurniawan
Wen Song
Wei Weng
Shigeru Fujimura
Publication date: 31-05-2020
Publisher: Springer Berlin Heidelberg
Published in: Evolutionary Intelligence / Issue 4/2021
Print ISSN: 1864-5909
Electronic ISSN: 1864-5917
DOI: https://doi.org/10.1007/s12065-020-00426-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2021

DNA motif discovery using chemical reaction optimization

Hybrid approach based on cuckoo optimization algorithm and genetic algorithm for task scheduling

A new Pareto multi-objective sine cosine algorithm for performance enhancement of radial distribution network by optimal allocation of distributed generators

An extensive experimental evaluation of automated machine learning methods for recommending classification algorithms

Numerical solution of Bagley–Torvik equations using Legendre artificial neural network method

RetrieveNet: a novel deep network for medical image retrieval

Premium Partner