# Minimum-Energy Scheduling of Flexible Job-Shop Through Optimization and Comprehensive Heuristic
## 4 Minimum-Energy Scheduling Heuristic with Due Times
### Adopted Principles to Design the Heuristic  
Here, the main idea is to develop, on a moving time front line, the allocation of machines and time schedules at the earliest start time of operations in ascending rank in any of the active jobs. This greedy scheme will promptly produce a solution promoting energy savings that is feasible for the current situation of the job shop. This will allow a reactive approach to reschedule the current production plan as many times as necessary. The solution must face the dilemma of having to choose between short job processing times and minimizing the necessary energy. This is achieved as follows: on the one side, the earliest assignment of a machine to a new operation is performed, but on the other side, the choice between the available machines is limited to the more energy efficient ones. The decision to assign a machine and to schedule the starting time for an operation will be based, on one side, on the processing delays and transfer delays from its directly preceding operations and, on the other side, on the transfer energy from the preceding operations and on the processing energy of the candidate machine. The driving dimension in the heuristic is time, since this will yield feasible solutions constructed step by step in the timeline according to the earliest feasible starting time for the operations. To assess, according to energy, the transitions from one operation to a successor one, new parameters must be defined. For operations \(O_{ih}\) and \(O_{ik}\) such that \(O_{ik}\in T_{ih}\), the energy cost of deciding that \(O_{ik}\) will be processed by machine \(l^{\prime}\), while \(O_{ih}\) is performed by machine \(l_{h}\), is the sum of the transfer energy and of the process energy \(tpe_{iikll^{\prime}}\) given by \(tpe_{iikll^{\prime}}\)=\(\sum_{h\in T_{ik}^{-1}}te_{i_{ih}l^{\prime}}+pe_{iikl^{\prime}}\) (see Figure 3).  
Consider now the sets of machines \(MM_{ih}=M_{ih}\times\cup_{k\in T_{ih}^{-1}}M_{ik}\), \(h=1\) to \(S_{i}\) and their associated energy costs. In large job shops, several machines may be identical, with almost equal transport time and energy between some pairs of machines. Pairs (\(l\), \(l^{\prime}\)) with the same total transfer energy costs can be grouped into the same subset, and these subsets can be ranked by increasing energy costs. Let \(MM_{ih}^{u}\) be these sets, with \(w_{i}=1\) to \(W_{i}\), where \(MM_{ih}=\oplus_{w_{i}=1}^{w_{i}=W_{i}}MM_{ih}^{u}\). Here, \(MM_{ih}^{1}\) is the subset of pairs with the minimum total (transport and processing) energy costs, while \(MM_{ih}^{W_{i}}\) is the subset of pairs with the highest energy cost.  
It is important to note that the operations that can be candidates to be assigned a machine are those for which all their predecessor operations have already been assigned  
Figure 3: Delays and energy costs for machine assignment to \(O_{ik}\).  
and scheduled. Then, the operations of each job are addressed by increasing rank in the corresponding DAG. The scheduling approach is a greedy one, so idle periods of machines may happen, but on the other side, decisions about machines will only consider their next free time up to the end of the working period, which is much easier to treat. It is important to also observe that, contrary to the approach presented in the previous section, in this case, the machine assignment to operations is performed step by step in the timeline.