Search
2016 Volume 31
Article Contents
RESEARCH ARTICLE   Open Access    

A metaheuristic technique for energy-efficiency in job-shop scheduling

More Information
  • Abstract: Many real life problems can be modeled as a scheduling problem. The main objective of these problems is to obtain optimal solutions in terms of processing time, cost and quality. Nowadays, energy-efficiency is also taken into consideration. However, these problems are 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 classical job-shop scheduling problem. In the extended version, each operation has to be executed by one machine and this machine can work at different speed rates. The machines consume different amounts of energy to process tasks at different rates. The evaluation section shows that a powerful commercial tools 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.
  • 加载中
  • Agnetis A., Flamini M., Nicosia G. & Pacifici A. (2011). A job-shop problem with one additional resource type. Journal of Scheduling 14(3), 225–237.

    Google Scholar

    Allahverdi A., Ng C.T., Cheng T.C.E. & Kovalyov M. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research 187(3), 985–1032.

    Google Scholar

    Bartak R., Salido M. & Rossi F. (2010). New trends in constraint satisfaction, planning, and scheduling: a survey. The Knowledge Engineering Review 25(3), 249–279.

    Google Scholar

    Beasley D., Martin R. & Bull D. (1993). An overview of genetic algorithms: part 1. Fundamentals. University Computing 15, 58–58.

    Google Scholar

    Billaut J., Moukrim A. & Sanlaville E. (2008). Flexibility and Robustness in Scheduling. Wiley.

    Google Scholar

    Blazewicz J., Cellary W., Slowinski R. & Weglarz J. (1986). Scheduling under resource constraints-deterministic models. Annals of Operations Research 7, 1–356.

    Google Scholar

    Bruzzone A., Anghinolfi D., Paolucci M. & Tonelli F. (2012). Energy-aware scheduling for improving manufacturing process sustainability: a mathematical model for flexible flow shops. CIRP Annals-Manufacturing Technology 61(1), 459–462.

    Google Scholar

    Dahmus J. & Gutowski T. 2004. An environmental analysis of machining. In ASME International Mechanical Engineering Congress and RD&D Exposition.

    Google Scholar

    Dai M., Tang D., Giret A., Salido M.A. & Li W. (2013). Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing 29(5), 418–429.

    Google Scholar

    Duflou J., Sutherland J., Dornfeld D., Herrmann C., Jeswiet J., Kara S., Hauschild M. & Kellens K. (2012). Towards energy and resource efficient manufacturing: a processes and systems approach. CIRP Annals-Manufacturing Technology 61(2), 587–609.

    Google Scholar

    Escamilla J., Salido M. A., Giret A. & Barber F. (2014). A metaheuristic technique for energy-efficiency in job-shop scheduling. In COPLAS’ 2014: ICAPS Workshop on Constraint Satisfaction Techniques for Planning and Scheduling, 42–50.

    Google Scholar

    Fang K., Uhan N., Zhao F. & Sutherland J. (2011). A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. Journal of Manufacturing Systems 30(4), 234–240.

    Google Scholar

    Garrido A., Salido M. A., Barber F. & Lopez M. (2000). Heuristic methods for solving job-shop scheduling problems. In ECAI-2000 Workshop on New Results in Planning, Scheduling and Design, 36–43.

    Google Scholar

    Huang K. & Liao C. 2008. Ant colony optimization combined with taboo search for the job shop scheduling problem. Computers & Operations Research 35(4), 1030–1046.

    Google Scholar

    IBM 2007. Modeling with IBM ILOG CP optimizer – practical scheduling examples. IBM.

    Google Scholar

    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), 148–162.

    Google Scholar

    Li W., Zein A., Kara S. & Herrmann C. (2011). An investigation into fixed energy consumption of machine tools. In Glocalized Solutions for Sustainability in Manufacturing, Hesselbach, J. & Herrmann, C. (eds), 268–273. Springer.

    Google Scholar

    Malakooti B., Sheikh S., Al-Najjar C. & Kim H. (2013). Multi-objective energy aware multiprocessor scheduling using bat intelligence. Journal of Intelligent Manufacturing 24(4), 805–819.

    Google Scholar

    Mestl H. E., Aunan K., Fang J., Seip H. M., Skjelvik J. M. & Vennemo H. (2005). Cleaner production as climate investment integrated assessment in Taiyuan City, China. Journal of Cleaner Production 13(1), 57–70.

    Google Scholar

    Mouzon G. & Yildirim M. 2008. A framework to minimise total energy consumption and total tardiness on a single machine. International Journal of Sustainable Engineering 1(2), 105–116.

    Google Scholar

    Mouzon G., Yildirim M. & Twomey J. (2007). Operational methods for minimization of energy consumption of manufacturing equipment. International Journal of Production Research 45(18–19), 4247–4271.

    Google Scholar

    Neugebauer R., Wabner M., Rentzsch H. & Ihlenfeldt S. (2011). Structure principles of energy efficient machine tools. CIRP Journal of Manufacturing Science and Technology 4(2), 136–147.

    Google Scholar

    Salido M. A., 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, 44–53.

    Google Scholar

    Seow Y. & Rahimifard S. 2011. A framework for modelling energy consumption within manufacturing systems. CIRP Journal of Manufacturing Science and Technology 4(3), 258–264.

    Google Scholar

    Varela R., Serrano D. & Sierra M. (2005). New codification schemas for scheduling with genetic algorithms. In Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach, 11–20. Springer.

    Google Scholar

    Watson J.-P., Barbulescu L., Howe A. E. & Whitley L. D. (1999). Algorithm performance and problem structure for flow-shop scheduling. In AAAI/IAAI, 688–695.

    Google Scholar

    Weinert N., Chiotellis S. & Seliger G. (2011). Methodology for planning and operating energy-efficient production systems. CIRP Annals-Manufacturing Technology 60(1), 41–44.

    Google Scholar

    Yan J. & Li L. 2013. Multi-objective optimization of milling parameters the trade-offs between energy, production rate and cutting quality. Journal of Cleaner Production 52, 462–471.

    Google Scholar

    Yusoff S. 2006. Renewable energy from palm oil—innovation on effective utilization of waste. Journal of Cleaner Production 14(1), 87–93.

    Google Scholar

  • Cite this article

    Joan Escamilla, Miguel A. Salido, Adriana Giret, Federico Barber. 2016. A metaheuristic technique for energy-efficiency in job-shop scheduling. The Knowledge Engineering Review 31(5)475−485, doi: 10.1017/S026988891600031X
    Joan Escamilla, Miguel A. Salido, Adriana Giret, Federico Barber. 2016. A metaheuristic technique for energy-efficiency in job-shop scheduling. The Knowledge Engineering Review 31(5)475−485, doi: 10.1017/S026988891600031X

Article Metrics

Article views(30) PDF downloads(41)

RESEARCH ARTICLE   Open Access    

A metaheuristic technique for energy-efficiency in job-shop scheduling

The Knowledge Engineering Review  31 2016, 31(5): 475−485  |  Cite this article

Abstract: Abstract: Many real life problems can be modeled as a scheduling problem. The main objective of these problems is to obtain optimal solutions in terms of processing time, cost and quality. Nowadays, energy-efficiency is also taken into consideration. However, these problems are 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 classical job-shop scheduling problem. In the extended version, each operation has to be executed by one machine and this machine can work at different speed rates. The machines consume different amounts of energy to process tasks at different rates. The evaluation section shows that a powerful commercial tools 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.

    • This research has been supported by the Spanish Government under research project MINECO TIN2013-46511-C2-1.

    • http://gps.webs.upv.es/jobshop/

    • http://gps.webs.upv.es/jobshop/

    • © Cambridge University Press, 2017 2017Cambridge University Press
References (29)
  • About this article
    Cite this article
    Joan Escamilla, Miguel A. Salido, Adriana Giret, Federico Barber. 2016. A metaheuristic technique for energy-efficiency in job-shop scheduling. The Knowledge Engineering Review 31(5)475−485, doi: 10.1017/S026988891600031X
    Joan Escamilla, Miguel A. Salido, Adriana Giret, Federico Barber. 2016. A metaheuristic technique for energy-efficiency in job-shop scheduling. The Knowledge Engineering Review 31(5)475−485, doi: 10.1017/S026988891600031X
  • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return