# Minimum-Energy Scheduling of Flexible Job-Shop Through Optimization and Comprehensive Heuristic
## 5 Evaluation of the Proposed Scheduling Heuristic
### Priority Rules for Flexible Job Shop Scheduling  
Simple priority rules were developed first for jobs processed by a single machine and then for jobs composed of a string of operations to be processed on given machines in a job shop; a survey classifying tens of them is given in [43]. When the objective is to minimize the make-span of a production plan, one of the more intuitive priority rules is the Shortest Processing Time (SPT) algorithm, which prioritizes operations based on their processing times, with the shortest operations being handled first. Since the focus in this study is on minimizing total energy, a new basic rule, a counterpart of SPT, can be introduced: the Smaller Processing Energy (SPE), whose algorithm prioritizes tasks based on their processing energy, with the more energy-efficient tasks being selected first. However, when considering flexible job shop scheduling, this is not sufficient, since some operations can be processed concurrently on different machines. Then, in this case, a priority rule must address two sub problems [44]: machine assignment and job sequencing. In the schedule of a flexible job shop, when an operation of a job is planned to finish to be processed on a machine at some scheduled time, the schedule must provide two pieces of information:  
* Which machine will process the next operation of that job? * What will be the next operation of a job processed by that machine? The successive answers to the first question can describe the processing of the jobs according to the schedule. In contrast, the successive answers to the second question can describe the load plan of each machine according to this same schedule. The answer to the second question results from the choice of an operation among the ones waiting at that machine. If the queue of operations at that time is empty, the machine becomes idle until new operations are assigned to it. Simple priority rules will tackle these two decision problems in sequence and not simultaneously, contrarily with what is achieved in the heuristic proposed in this study with relation to (24). Then, in the case of a flexible job shop, a priority rule will have first to assign, for each operation, a machine, and then schedule each operation on its assigned machine. It is important to observe that assigning each operation a priori to a machine according to its processing time or processing energy for this operation would result in priority rules that are much simpler to implement, but this could generate additional delays since it would be necessary to wait for the machine previously assigned to an operation to become free, while other machines may be available earlier. Then, two on-line priority rules, which can be seen as extensions of SPT and SPE to the flexible case of job shop scheduling, are considered for comparison with the proposed heuristic:One focusing on processing time, named TTE (indicating Time-Time-Energy according to the nature of the criterion considered at each stage of the priority rule), where the machine is able to process earlier that operation is assigned to it and where the operation to be next processed among the waiting operations of a machine is chosen according to SPT. When different machines have the same fastest processing time for an operation, the one with the smallest processing energy will be assigned to it, and in case of equal energy performance, a random choice will be made among them. If different queuing operations at the same machine have the same processing time, the FIFO rule is applied. One focusing on processing energy, named ETT (for Energy-Time-Time), where a machine is able to process with the minimum energy that operation is assigned to it, while the operation to be next processed among the waiting operations of a machine is also chosen according to SPT. In the case of machines with equal processing energy performance, the one with the shortest processing time will be assigned to it, and in the case of an equal processing time, a random choice will be made among these waiting operations.