Skip to main content
Erschienen in: Memetic Computing 4/2019

24.10.2019 | Regular Research Paper

Genetic algorithms with greedy strategy for green batch scheduling on non-identical parallel machines

verfasst von: Mao Tan, Hua-Li Yang, Yong-Xin Su

Erschienen in: Memetic Computing | Ausgabe 4/2019

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Large scale batch scheduling problems with complex constraints are difficult and time-consuming to solve. Therefore, this paper addresses the green batch scheduling problem on non-identical parallel machines with time-of-use electricity prices. The objective of the problem is to minimise total electricity costs (TEC) in production. Two kinds of algorithms—single-population genetic algorithms (SPGA) and multi-population genetic algorithm (MPGA)—are proposed to solve the problem. In the algorithms, the products are allocated into batches and are then allocated to machines randomly. A greedy strategy is designed to arrange the production sequence and the starting time of the batches. Furthermore, a self-adaptive parameter adjustment strategy is proposed to enhance the adaptability of the algorithm. Computational experiments with CPLEX solver have been conducted to evaluate the performance of the algorithms. On small instances, both SPGA and MPGA can achieve approximate results compared with those obtained by CPLEX, and can also achieve smaller TEC on large instances with less computing time. In addition, the proposed MPGA implemented by parallel computing outperforms SPGA in getting better results with nearly the same computing time.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat Nghiem T, Behl M, Pappas GJ, Mangharam R (2011) Green scheduling: scheduling of control systems for peak power reduction. In: 2011 international green computing conference and workshops (IGCC), pp 1–8 Nghiem T, Behl M, Pappas GJ, Mangharam R (2011) Green scheduling: scheduling of control systems for peak power reduction. In: 2011 international green computing conference and workshops (IGCC), pp 1–8
2.
Zurück zum Zitat 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(3):772–788MathSciNetCrossRef 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(3):772–788MathSciNetCrossRef
3.
Zurück zum Zitat Li Y, Wang Y, Zhao X, Ren M (2013) Multi-objective optimization of rolling schedules for tandem hot rolling based on opposition learning multi-objective genetic algorithm. In: The 25th Chinese control and decision conference. IEEE, pp 846–849 Li Y, Wang Y, Zhao X, Ren M (2013) Multi-objective optimization of rolling schedules for tandem hot rolling based on opposition learning multi-objective genetic algorithm. In: The 25th Chinese control and decision conference. IEEE, pp 846–849
4.
Zurück zum Zitat Lu C, Gao L, Li X, Chen P (2016) Energy-efficient multi-pass turning operation using multi-objective backtracking search algorithm. J Clean Prod 137:1516–1531CrossRef Lu C, Gao L, Li X, Chen P (2016) Energy-efficient multi-pass turning operation using multi-objective backtracking search algorithm. J Clean Prod 137:1516–1531CrossRef
5.
Zurück zum Zitat Aghelinejad M, Ouazene Y, Yalaoui A (2018) Energy optimization of a speed-scalable and multi-states single machine scheduling problem. In: Daniele P, Scrimali L (eds) New trends in emerging complex real life problems. Springer, Cham, pp 23–31CrossRef Aghelinejad M, Ouazene Y, Yalaoui A (2018) Energy optimization of a speed-scalable and multi-states single machine scheduling problem. In: Daniele P, Scrimali L (eds) New trends in emerging complex real life problems. Springer, Cham, pp 23–31CrossRef
6.
Zurück zum Zitat 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–242CrossRef 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–242CrossRef
7.
Zurück zum Zitat Desta AA, Badis H, George L (2018) Demand response scheduling in industrial asynchronous production lines constrained by available power and production rate. Appl Energy 230:1414–1424CrossRef Desta AA, Badis H, George L (2018) Demand response scheduling in industrial asynchronous production lines constrained by available power and production rate. Appl Energy 230:1414–1424CrossRef
8.
Zurück zum Zitat Wang Y, Li L (2015) Time-of-use electricity pricing for industrial customers: a survey of US utilities. Appl Energy 149:89–103CrossRef Wang Y, Li L (2015) Time-of-use electricity pricing for industrial customers: a survey of US utilities. Appl Energy 149:89–103CrossRef
9.
Zurück zum Zitat Mitra S, Pinto JM, Grossmann IE (2014) Optimal multi-scale capacity planning for power-intensive continuous processes under time-sensitive electricity prices and demand uncertainty. Part I: modeling. Comput Chem Eng 65:89–101CrossRef Mitra S, Pinto JM, Grossmann IE (2014) Optimal multi-scale capacity planning for power-intensive continuous processes under time-sensitive electricity prices and demand uncertainty. Part I: modeling. Comput Chem Eng 65:89–101CrossRef
10.
Zurück zum Zitat Fang K, Uhan UA, Zhao F, Sutherland JW (2015) Scheduling on a single machine under time-of-use electricity tariffs. Ann Oper Res 238(1):199–227MathSciNetMATH Fang K, Uhan UA, Zhao F, Sutherland JW (2015) Scheduling on a single machine under time-of-use electricity tariffs. Ann Oper Res 238(1):199–227MathSciNetMATH
11.
Zurück zum Zitat 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–577CrossRef 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–577CrossRef
12.
Zurück zum Zitat Kurniawan B, Gozali AA, Weng W, Fujimura S (2018) A mix integer programming model for bi-objective single machine with total weighted tardiness and electricity cost under time-of-use tariffs. In: 2018 IEEE international conference on industrial engineering and engineering management. IEEE, pp 137–141 Kurniawan B, Gozali AA, Weng W, Fujimura S (2018) A mix integer programming model for bi-objective single machine with total weighted tardiness and electricity cost under time-of-use tariffs. In: 2018 IEEE international conference on industrial engineering and engineering management. IEEE, pp 137–141
13.
Zurück zum Zitat Wang S, Zhu Z, Fang K, Chu F, Chu C (2018) Scheduling on a two-machine permutation flow shop under time-of-use electricity tariffs. Int J Prod Res 56(9):3173–3187CrossRef Wang S, Zhu Z, Fang K, Chu F, Chu C (2018) Scheduling on a two-machine permutation flow shop under time-of-use electricity tariffs. Int J Prod Res 56(9):3173–3187CrossRef
14.
Zurück zum Zitat Ding JY, Song S, Zhang R, Chiong R, Wu (2016) Parallel machine scheduling under time-of-use electricity prices: new models and optimization approaches. IEEE Trans Autom Sci Eng 13(2):1138–1154CrossRef Ding JY, Song S, Zhang R, Chiong R, Wu (2016) Parallel machine scheduling under time-of-use electricity prices: new models and optimization approaches. IEEE Trans Autom Sci Eng 13(2):1138–1154CrossRef
15.
Zurück zum Zitat Cheng J, Chu F, Zhou M (2018) An improved model for parallel machine scheduling under time-of-use electricity price. IEEE Trans Autom Sci Eng 15(2):896–899CrossRef Cheng J, Chu F, Zhou M (2018) An improved model for parallel machine scheduling under time-of-use electricity price. IEEE Trans Autom Sci Eng 15(2):896–899CrossRef
16.
Zurück zum Zitat Che A, Zhang S, Wu X (2017) Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. J Clean Prod 156:688–697CrossRef Che A, Zhang S, Wu X (2017) Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. J Clean Prod 156:688–697CrossRef
17.
Zurück zum Zitat Zarandi MHF, Kayvanfar V (2015) A bi-objective identical parallel machine scheduling problem with controllable processing times: a just-in-time approach. Int J Adv Manuf Technol 77(1–4):545–563CrossRef Zarandi MHF, Kayvanfar V (2015) A bi-objective identical parallel machine scheduling problem with controllable processing times: a just-in-time approach. Int J Adv Manuf Technol 77(1–4):545–563CrossRef
18.
Zurück zum Zitat Zhou S, Li X, Du N, Pang Y, Pang Y, Chen H (2018) A multi-objective differential evolution algorithm for parallel batch processing machine scheduling considering electricity consumption cost. Comput Oper Res 96:55–68MathSciNetCrossRef Zhou S, Li X, Du N, Pang Y, Pang Y, Chen H (2018) A multi-objective differential evolution algorithm for parallel batch processing machine scheduling considering electricity consumption cost. Comput Oper Res 96:55–68MathSciNetCrossRef
20.
Zurück zum Zitat Zhang W, Wen JB, Zhu YC, Hu Y (2017) Multi-objective scheduling simulation of flexible job-shop based on multi-population genetic algorithm. Int J Simul Model 16(2):313–321CrossRef Zhang W, Wen JB, Zhu YC, Hu Y (2017) Multi-objective scheduling simulation of flexible job-shop based on multi-population genetic algorithm. Int J Simul Model 16(2):313–321CrossRef
21.
Zurück zum Zitat Hadera H, Harjunkoski I, Sand G, Grossmann IE, Engell S (2015) Optimization of steel production scheduling with complex time-sensitive electricity cost. Comput Chem Eng 76:117–136CrossRef Hadera H, Harjunkoski I, Sand G, Grossmann IE, Engell S (2015) Optimization of steel production scheduling with complex time-sensitive electricity cost. Comput Chem Eng 76:117–136CrossRef
22.
Zurück zum Zitat Schwindt C, Trautmann N (2000) Batch scheduling in process industries: an application of resource constrained project scheduling. OR-Spektrum 22(4):501–524MathSciNetCrossRef Schwindt C, Trautmann N (2000) Batch scheduling in process industries: an application of resource constrained project scheduling. OR-Spektrum 22(4):501–524MathSciNetCrossRef
23.
Zurück zum Zitat 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–207CrossRef 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–207CrossRef
24.
Zurück zum Zitat Wang J, Qiao F, Zhao F, Sutherland JW (2016) Batch scheduling for minimal energy consumption and tardiness under uncertainties: a heat treatment application. CIRP Ann 65(1):17–20CrossRef Wang J, Qiao F, Zhao F, Sutherland JW (2016) Batch scheduling for minimal energy consumption and tardiness under uncertainties: a heat treatment application. CIRP Ann 65(1):17–20CrossRef
25.
Zurück zum Zitat Wang S, Liu M, Chu F, Chu C (2016) Bi-objective optimization of a single machine batch scheduling problem with energy cost consideration. J Clean Prod 137:1205–1215CrossRef Wang S, Liu M, Chu F, Chu C (2016) Bi-objective optimization of a single machine batch scheduling problem with energy cost consideration. J Clean Prod 137:1205–1215CrossRef
26.
Zurück zum Zitat Cheng J, Chu F, Liu M, Wu P, Xia W (2017) Bi-criteria single-machine batch scheduling with machine on/off switching under time-of-use tariffs. Comput Ind Eng 112:721–734CrossRef Cheng J, Chu F, Liu M, Wu P, Xia W (2017) Bi-criteria single-machine batch scheduling with machine on/off switching under time-of-use tariffs. Comput Ind Eng 112:721–734CrossRef
27.
Zurück zum Zitat Sharma A, Zhao F, Sutherland JW (2015) Econological scheduling of a manufacturing enterprise operating under a time-of-use electricity tariff. J Clean Prod 108:256–270CrossRef Sharma A, Zhao F, Sutherland JW (2015) Econological scheduling of a manufacturing enterprise operating under a time-of-use electricity tariff. J Clean Prod 108:256–270CrossRef
28.
Zurück zum Zitat Tan M, Chen Y, Su YX, Li S, Li H (2019) Integrated optimization model for industrial self-generation and load scheduling with tradable carbon emission permits. J Clean Prod 210:1289–1300CrossRef Tan M, Chen Y, Su YX, Li S, Li H (2019) Integrated optimization model for industrial self-generation and load scheduling with tradable carbon emission permits. J Clean Prod 210:1289–1300CrossRef
29.
Zurück zum Zitat Tan M, Duan B, Su Y (2018) Economic batch sizing and scheduling on parallel machines under time-of-use electricity pricing. Oper Res Int J 18(1):105–122CrossRef Tan M, Duan B, Su Y (2018) Economic batch sizing and scheduling on parallel machines under time-of-use electricity pricing. Oper Res Int J 18(1):105–122CrossRef
30.
Zurück zum Zitat Yin Y, Wang Y, Cheng TCE, Wang DJ, Wu CC (2016) Two-agent single-machine scheduling to minimize the batch delivery cost. Comput Ind Eng 92:16–30CrossRef Yin Y, Wang Y, Cheng TCE, Wang DJ, Wu CC (2016) Two-agent single-machine scheduling to minimize the batch delivery cost. Comput Ind Eng 92:16–30CrossRef
31.
Zurück zum Zitat Lipowski A, Lipowska D (2012) Roulette-wheel selection via stochastic acceptance. Physica A 391(6):2193–2196CrossRef Lipowski A, Lipowska D (2012) Roulette-wheel selection via stochastic acceptance. Physica A 391(6):2193–2196CrossRef
Metadaten
Titel
Genetic algorithms with greedy strategy for green batch scheduling on non-identical parallel machines
verfasst von
Mao Tan
Hua-Li Yang
Yong-Xin Su
Publikationsdatum
24.10.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
Memetic Computing / Ausgabe 4/2019
Print ISSN: 1865-9284
Elektronische ISSN: 1865-9292
DOI
https://doi.org/10.1007/s12293-019-00296-z

Weitere Artikel der Ausgabe 4/2019

Memetic Computing 4/2019 Zur Ausgabe