Skip to main content
No Access

A hybrid CP/MILP method for scheduling with energy costs

Published Online:pp 471-489https://doi.org/10.1504/EJIE.2011.042742

This paper deals with energy-related job scheduling for a foundry, in order to minimise the electricity bill. Accounting for energy and human resource constraints leads to better solutions in terms of cost and overall energy consumption. We propose a hybrid heuristic based on a two-step constraint/mathematical programming approach that improves significantly the computation time, compared to the full MILP model.

Keywords

scheduling, energy, human resources, parallel machines, hybrid approach

References

  • 1. Agha, M. , Thery, R. , Hetreux, G. , Le Lann, J-M. (2008). ‘Modèle intégré pour l’ordonnancement d’ateliers batch et la planification de centrales de cogénération’. Conférence Internationale de Modélisation et Simulation, MOSIM08, Paris, France Google Scholar
  • 2. Agha, M. , Thery, R. , Hetreux, G. , Haït, A. , Le Lann, J-M. (2010). ‘Integrated production and utility system approach for optimizing industrial unit operations’. Energy. 35, 2, 611-627 Google Scholar
  • 3. Artigues, C. , Lopez, P. , Haït, A. (2009). ‘Scheduling under energy constraints’. Proceedings of the International Conference on Industrial Engineering and Systems Management (IESM‘09). Google Scholar
  • 4. Baptiste, Ph. , Jouglet, A. , Le Pape, C. , Nuijten, W. (2000). ‘A constraint-based approach to minimize the weighted number of late jobs on parallel machines’. UTC Technical Report 2000/288 Google Scholar
  • 5. Boukas, E-K. , Haurie, A. , Soumis, F. (1990). ‘Hierarchical approach to steel production scheduling under a global energy constraint’. Annals of Operations Research. 26, 289-311 Google Scholar
  • 6. Chen, Z-L. , Powell, W.B. (1999). ‘Solving parallel machine scheduling problems by column generation’. INFORMS J. on Computing. 11, 1, 78-94 Google Scholar
  • 7. Cheng, T. , Sin, C. (1990). ‘A state-of-the-art review of parallel-machine scheduling research’. European Journal of Operational Research. 47, 271-292 Google Scholar
  • 8. Cheung, K-Y. , Hui, C-W. (2004). ‘Total-site scheduling for better energy utilization’. Journal of Cleaner Production. 12, 171-184 Google Scholar
  • 9. Drozdowski, M. (2004). ‘Scheduling multiprocessor tasks – an overview’. European Journal of Operational Research. 94, 215-230 Google Scholar
  • 10. Gacias, B. , Artigues, C. , Lopez, P. (2010). ‘Parallel machine scheduling with precedence constraints and setup times’. Computers and Operations Research. 10.1016/j.cor.2010.03.003 Google Scholar
  • 11. Gibbs, D. , Deutz, P. (2007). ‘Reflexion on implementing industrial ecology through ecoindustrial park development’. Journal of Cleaner Production. 15, 17, 1683-1695 Google Scholar
  • 12. Haït, A. , Artigues, C. , Trepanier, M. , Baptiste, P. (2007). ‘Ordonnancement sous contraintes dènergie et de ressources humaines’. 11e Congrés de la Société Française de Génie des Procédés, Saint-Etienne, France, Récents progrès en Génie des Procédés. 96, Google Scholar
  • 13. Harjunkoski, I. , Grossmann, I. (2001). ‘A decomopsition approach for the scheduling of a steel plant production’. Computers and Chemical Engineering. 25, 1647-1660 Google Scholar
  • 14. Irani, S. , Pruhs, K. (2005). ‘Algorithmic problems in power management’. SIGACT News. 36, 2, 63-76 Google Scholar
  • 15. Korhonen, J. (2002). ‘A material and energy flow for co-production of heat and power’. Journal of Cleaner Production. 10, 537-544 Google Scholar
  • 16. Laborie, P. (2009). ‘IBM ILOG CP optimizer for detailed scheduling illustrated on three problems’. Proceedings of the 6th International Conference, on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’09), LNCS. 5547, 148-162 Google Scholar
  • 17. Nèron, E. , Tercinet, F. , Sourd, F. (2008). ‘Search tree based approaches for parallel machine scheduling’. Computers and Operations Research. 35, 4, 1127-1137 Google Scholar
  • 18. Nolde, K. , Morari, M. (2010). ‘Electrical load tracking scheduling of a steel plant’. Computers and Operations Research. to appear Google Scholar
  • 19. Pearn, W.L. , Chung, S.H. , Lai, C.M. (2007). ‘Scheduling integrated circuit assembly operations on die bonder’. IEEE Transactions on Electronics Packaging Manufacturing. 30, 2, Google Scholar
  • 20. Sadykov, R. , Wolsey, L.A. (2006). ‘Integer programming and constraint programming in solving a multimachine assignment scheduling problem with deadlines and release dates’. INFORMS Journal on Computing. 18, 2, 209-217 Google Scholar
  • 21. Salem, A. , Anagnostopoulos, G.C. , Rabadi, G. (2000). ‘A branch-and-bound algorithm for parallel machine scheduling problems’. in Harbour, Maritime & Multimodal Logistics Modeling and Simulation Workshop, Portofino, Italy:Society for Computer Simulation International (SCS) Google Scholar