# Minimum-Energy Scheduling of Flexible Job-Shop Through Optimization and Comprehensive Heuristic
## 1 Introduction
### The Objective of the Study  
The objective of this study is to contribute to energy efficiency in the manufacturing industry, more particularly in high-energy-consuming integrated, flexible production plants, by developing a new approach to generate energy-efficient schedules with acceptable production delays for flexible job-shop scheduling problems. This study considers the main energy consumption sources in a flexible job shop, machine processing, and transfer of materials. Energy consumed by idle machines is not contemplated. Effectively, if idle times are small, the energy consumed by an idle machine may be negligible, while if idle times are large, the corresponding machines will certainly be shut off.  
In this study, jobs are composed of a finite set of operations linked together by precedence-succession constraints without cycling, and due times are assigned to them. Flexibility here refers to the ability to assign the processing of certain operations to different machines. One important element of the solution is the concurrent assignment of the machines to the operations of the different jobs. As early as 1993, [PERSON] [30] considered a two-level approach with the decomposition of the flexible job-shop scheduling problem into routing and job-shop sub-problems to minimize the make-span of a given production plan. His work has received over 400 citations, mainly for his flexible job shop scheduling benchmark and its early use of Taboo Search [31] to solve the two sub-problems than for the proposed decomposition.  
In this study, this dual view of the flexible job-shop problem is first adopted to achieve minimum energy schedules by considering the machine assignment of all the operations of a job as a decision variable. The non-consideration of the energy consumed by idle machines means that the energy consumption associated with a production program only depends on the allocation of the operations of each job to the different machines of the job shop and not the timing adopted for their execution. This leads to a formulation of a two-level optimization problem where energy costs and job shop dynamics are separated, opening the way to use exact or approximate solution approaches for this class of mathematical programming problem. This will provide nominal solutions to production plans over a finite period. However, the objectives of this study go well beyond this result. The goal is to propose a scheduling scheme that can adapt easily to cope efficiently with the following:  
* Planned (scheduled maintenance, for example) or unplanned disturbances (machine or conveyor breakdown between machines, for example);
* The fast generation of energy-efficient schedules to cope with the arrival of new jobs, allowing permanent operation with the efficient energy performance of the job shop.  
This goal has led to the development, in a second step of the study, an ad hoc heuristic able to produce promptly after any significant perturbation or event, an updated solution consistent with the current operational state of the job shop for this original scheduling problem.  
The rest of this paper is organized as follows: first, the characteristics of the considered job shop and the adopted notations are displayed in section two; section three presents a separable formulation of a nominal minimum-energy flexible job-shop problem is introduced to ease the search for its exact solution; a heuristic based on the earliest processing time with minimum energy is introduced to generate an open-loop solution to the scheduling problem in the fourth section. Then, the extensions of this heuristic to enable it to cope with disruptions and new jobs are discussed, and the application to a small illustrative case is displayed. Finally, in the Conclusion section, additional research directions are pointed out.