- -

A Genetic Algorithm for Energy-Efficiency in Job-Shop Scheduling

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A Genetic Algorithm for Energy-Efficiency in Job-Shop Scheduling

Show simple item record

Files in this item

dc.contributor.author Salido, Miguel A. es_ES
dc.contributor.author Escamilla Fuster, Joan es_ES
dc.contributor.author Giret Boggino, Adriana Susana es_ES
dc.contributor.author Barber, Federico es_ES
dc.date.accessioned 2016-09-08T07:46:42Z
dc.date.available 2016-09-08T07:46:42Z
dc.date.issued 2016-07
dc.identifier.issn 0268-3768
dc.identifier.uri http://hdl.handle.net/10251/69061
dc.description.abstract Many real-world scheduling problems are solved to obtain optimal solutions in term of processing time, cost, and quality as optimization objectives. Currently, energyefficiency is also taken into consideration in these problems. However, this problem is NP-hard, so many search techniques are not able to obtain a solution in a reasonable time. In this paper, a genetic algorithm is developed to solve an extended version of the Job-shop Scheduling Problem in which machines can consume different amounts of energy to process tasks at different rates (speed scaling). This problem represents an extension of the classical jobshop scheduling problem, where each operation has to be executed by one machine and this machine can work at different speeds. The evaluation section shows that a powerful commercial tool for solving scheduling problems was not able to solve large instances in a reasonable time, meanwhile our genetic algorithm was able to solve all instances with a good solution quality. es_ES
dc.description.sponsorship This research has been supported by the Spanish Government under research project MINECO TIN2013-46511-C2-1 and the CASES project supported by a Marie Curie International Research Staff Exchange Scheme Fellowship within the 7th European Community Framework Programme under the grant agreement No 294931. We would like to thanks Philippe Laborie (IBM ILOG CPLEX) for validating the CP Optimizer model for this problem. We also appreciate the significant efforts made by all the reviewers to improve this paper. en_EN
dc.language Inglés es_ES
dc.publisher Springer Verlag (Germany) es_ES
dc.relation Spanish Government under research project MINECO TIN2013-46511-C2-1 es_ES
dc.relation CASES project by a Marie Curie International Research Staff Exchange Scheme Fellowship within the 7th European Community 294931 es_ES
dc.relation.ispartof International Journal of Advanced Manufacturing Technology es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Job-shop scheduling problems es_ES
dc.subject Metaheuristic es_ES
dc.subject Energy-efficiency es_ES
dc.subject Robustness es_ES
dc.subject Makespan es_ES
dc.subject Artificial intelligence es_ES
dc.subject.classification LENGUAJES Y SISTEMAS INFORMATICOS es_ES
dc.title A Genetic Algorithm for Energy-Efficiency in Job-Shop Scheduling es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s00170-015-7987-0
dc.rights.accessRights Cerrado es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Salido, MA.; Escamilla Fuster, J.; Giret Boggino, AS.; Barber, F. (2016). A Genetic Algorithm for Energy-Efficiency in Job-Shop Scheduling. International Journal of Advanced Manufacturing Technology. 85(5-8):1303-1314. doi:10.1007/s00170-015-7987-0 es_ES
dc.description.accrualMethod Senia es_ES
dc.relation.publisherversion http://dx.doi.org/10.1007/s00170-015-7987-0 es_ES
dc.description.upvformatpinicio 1303 es_ES
dc.description.upvformatpfin 1314 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 85 es_ES
dc.description.issue 5-8 es_ES
dc.relation.senia 294862 es_ES
dc.identifier.eissn 1433-3015
dc.relation.references Adams J, Balas E, Zawack D (1988) Shifting bottleneck procedure for job shop scheduling. Manag Sci 34(3):391–401 es_ES
dc.relation.references Agnetis A, Flamini M, Nicosia G, Pacifici A (2011) A job-shop problem with one additional resource type. J Sched 14(3):225–237 es_ES
dc.relation.references Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985–1032 es_ES
dc.relation.references Barba I, Del Valle C, Borrego D (2009) A constraint-based job-shop scheduling model for software development planning. Actas de los Talleres de las Jornadas de Ingeniería del Software y Bases de Datos, vol 3 es_ES
dc.relation.references Beasley D, Martin RR, Bull DR (1993) An overview of genetic algorithms: Part 1. fundamentals, vol 15. University computing, pp 58–58 es_ES
dc.relation.references Bierwirth C (1995) A generalized permutation approach to job shop scheduling with genetic algorithms. Operations-Research-Spektrum 17(2-3):87–92 es_ES
dc.relation.references Blazewicz J, Cellary W, Slowinski R, Weglarz J (1986) Scheduling under resource constraints-deterministic models. Ann Oper Res 7:1–356 es_ES
dc.relation.references Brown APG, Lomnicki ZA (1966) Some applications of the branch-and-bound algorithm to the machine scheduling problem. Oper Res:173–186 es_ES
dc.relation.references Bruzzone AAG, Anghinolfi D, Paolucci M, Tonelli F (2012) Energy-aware scheduling for improving manufacturing process sustainability: a mathematical model for flexible flow shops es_ES
dc.relation.references Bunde DP (2006) Power-aware scheduling for makespan and flow. In: Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. ACM, New York, pp 190–196 es_ES
dc.relation.references Dai M, Tang D, Giret A, Salido MA, Li WD (2013) Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robot Comput Integr Manuf 29(5):418–429 es_ES
dc.relation.references Fang K, Uhan N, Zhao F, Sutherland JW (2011) A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. J Manuf Syst 30(4):234–240 es_ES
dc.relation.references Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1(2):117–129 es_ES
dc.relation.references Gonċalves JF, de Magalhães Mendes JJ, Resende MGC (2005) A hybrid genetic algorithm for the job shop scheduling problem. Eur J Oper Res 167(1):77–95 es_ES
dc.relation.references Guo ZX, Wong WK, Leung SYS, Fan JT, Chan SF (2006) Mathematical model and genetic optimization for the job shop scheduling problem in a mixed-and multi-product assembly environment: a case study based on the apparel industry. Comput Ind Eng 50(3):202–219 es_ES
dc.relation.references IBM (2007) Modeling with IBM ILOG CP Optimizer—practical scheduling examples. IBM es_ES
dc.relation.references IBM ILOG CPLEX Optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/. es_ES
dc.relation.references Jain AS, Meeran S (1998) Job-shop scheduling using neural networks. Int J Prod Res 36(5):1249–1272 es_ES
dc.relation.references Kapamara T, Sheibani K, Haas OCL, Reeves CR, Petrovic D (2006) A review of scheduling problems in radiotherapy. In: Proceedings of the Eighteenth International Conference on Systems Engineering (ICSE2006), Coventry University, UK , pp 201–207 es_ES
dc.relation.references Khormali A, Mirzazadeh A, Faez F (2012) The openshop batch processing problem with non-identical processing times, using simulated annealing and genetic algorithms approaches. Int J Adv Manuf Technol 59(9-12):1157–1165 es_ES
dc.relation.references Laborie P (2009) IBM ILOG CP Optimizer for detailed scheduling illustrated on three problems. In: Proceedings of the 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR09), pp 148–162 es_ES
dc.relation.references Li L, Yan J, Xing Z (2013) Energy requirements evaluation of milling machines based on thermal equilibrium and empirical modelling es_ES
dc.relation.references Li W, Zein A, Kara S, Herrmann C (2011) An investigation into fixed energy consumption of machine tools. Glocalized Solutions for Sustainability in Manufacturing es_ES
dc.relation.references Ching-Fang L (2000) A hybrid genetic algorithm for the open shop scheduling problem. Eur J Oper Res 124(1):28–42 es_ES
dc.relation.references Malakooti B, Sheikh S, Al-Najjar C, Kim H (2013) Multi-objective energy aware multiprocessor scheduling using bat intelligence. J Int Manag 24(4):805–819 es_ES
dc.relation.references May G, Stahl B, Taisch M, Prabhu V (2015) Multi-objective genetic algorithm for energy-efficient job shop scheduling. Int J Prod Res:1–19 es_ES
dc.relation.references Mestl HE, Aunan K, Fang J, Seip HM, Skjelvik JM, Vennemo H (2005) Cleaner production as climate investmentin-tegrated assessment in Taiyuan city, China. J Clean Prod 13(1):57–70 es_ES
dc.relation.references Mouzon G, Yildirim MB, Twomey J (2007) Operational methods for minimization of energy consumption of manufacturing equipment. Int J Prod Res 45(18-19):4247–4271 es_ES
dc.relation.references Neugebauer R, Wabner M, Rentzsch H, Ihlenfeldt S (2011) Structure principles of energy efficient machine tools. CIRP J Manuf Sci Technol 4(2):136–147 es_ES
dc.relation.references Ono I, Yamamura M, Kobayashi S (1996) A genetic algorithm for job-shop scheduling problems using job-based order crossover. In: Evolutionary Computation, 1996., Proceedings of IEEE International Conference on, pages 547–552. IEEE es_ES
dc.relation.references Perez-Rodriguez R, Jons S, Hernandez-Aguirre A, Alberto-Ochoa C (2014) Simulation optimization for a flexible jobshop scheduling problem using an estimation of distribution algorithm. Int J Adv Manuf Technol 73(1-4):3–21 es_ES
dc.relation.references Resende MGC (1997) A grasp for job shop scheduling. In: INFORMS Spring Meeting es_ES
dc.relation.references Salido MA, Escamilla J, Barber F, Giret A, Tang D, Dai M (2013) Energy-aware parameters in job-shop scheduling problems. In: GREEN-COPLAS 2013: IJCAI 2013 Workshop on Constraint Reasoning, Planning and Scheduling Problems for a Sustainable Future, pp 44–53 es_ES
dc.relation.references Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278–285 es_ES
dc.relation.references Vahedi-Nouri B, Fattahi P, Tavakkoli-Moghaddam R, Ramezanian R (2014) A general flow shop scheduling problem with consideration of position-based learning effect and multiple availability constraints. Int J Adv Manuf Technol 73(5-8):601–611 es_ES
dc.relation.references Watson J-P, Barbulescu L, Howe AE, Whitley DL (1999) Algorithm performance and problem structure for flow-shop scheduling. In: AAAI/IAAI, pp 688–695 es_ES
dc.relation.references Yan J, Li L (2013) Multi-objective optimization of milling parametersthe trade-offs between energy, production rate and cutting quality. J Clean Prod es_ES
dc.relation.references Yusoff S (2006) Renewable energy from palm oil–innovation on effective utilization of waste. J Clean Prod 14(1):87–93 es_ES


This item appears in the following Collection(s)

Show simple item record