[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

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

  • Research Paper
  • Published:
Evolutionary Intelligence Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. 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

    Article  Google Scholar 

  2. 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

    Article  MATH  Google Scholar 

  3. 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

    Article  Google Scholar 

  4. 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

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. 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-8

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  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–17

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  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

    Google Scholar 

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

Download references

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

Authors

Corresponding author

Correspondence to Bobby Kurniawan.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12065-020-00426-4

Keywords

Navigation