Job-shop like manufacturing system with variable power threshold and operations with power requirements

This article is an extended and improved version of two conference papers (Kemmoé, Lamy, and Tchernev 2015a, Kemmoé, Lamy, and Tchernev 2015b). The mathematical model is improved. The Local search procedure is improved and formalised. A construction heuristic is also introduced to generate good starting solutions. The data-set is extended with medium scale instances. Experiments are given.

Abstract

This paper addresses an important issue in manufacturing by considering the scheduling of a Job-shop like manufacturing system involving a power threshold that must not be exceeded over time. A power profile is attached to operations that must be scheduled. This power profile presents a consumption peak at the start of process in order to model most of real-world machining operations. These operations must be scheduled according to the instantly available power threshold. A mathematical formulation of the problem is proposed; its main goal is to minimise the total completion time of all operations. A set of instances is built based on classical format of instances for the Job-shop problem. As it is time-consuming to obtain exact solutions on these instances with the CPLEX solver, a Greedy Randomised Adaptive Search Procedure hybridised with an Evolutionary Local Search (GRASP × ELS) metaheuristic is designed. The GRASP × ELS is compared with two other metaheuristics: a Variable Neighbourhood Search and a Memetic Algorithm. The GRASP × ELS is also compared with several algorithms developed in the literature for the classical job-shop problem. Results show the relevancy of the metaheuristic approaches both in terms of computational time and quality of solutions.

Keywords:

• job-shop
• scheduling
• energy efficient manufacturing
• metaheuristics
• integer programming

Acknowledgements

This work was financially supported by the French Public Investment Bank (BPI) and granted under the ECOTHER project. The authors would like to thank the anonymous referees for their helpful suggestions, which greatly improved this paper.

Notes

This article is an extended and improved version of two conference papers (Kemmoé, Lamy, and Tchernev 2015a, Kemmoé, Lamy, and Tchernev 2015b). The mathematical model is improved. The Local search procedure is improved and formalised. A construction heuristic is also introduced to generate good starting solutions. The data-set is extended with medium scale instances. Experiments are given.

1. Available on damienlamy.com/Works/Energy/JSPPR/VariableThreshold/