# Minimum-Energy Scheduling of Flexible Job-Shop Through Optimization and Comprehensive Heuristic
## 2 The Considered Class of Flexible Job Shops and Their Representation
### The Two-Level Minimum-Energy Scheduling Problem  
The minimum-energy flexible job-shop scheduling problem formulated as an optimization problem by using the machine assignment variables \(x_{ij}\), the precedence variables \(z_{iji^{\prime}}r_{ik^{\prime}}\) and the timing variables \(t_{ijk}\) is the following:  
\(x_{ij}=1\) if machine assignment \(j\) is chosen to perform job \(i\), and \(x_{ij}=0\) otherwise;  
\(t_{ikj}\): the starting time of operation \(O_{ik}\) at machine \(l_{ikj}\);\(z_{ijij^{\prime}jk^{\prime}}=1\) if operation \(O_{ik}\) with machine \(l_{ij}\) is decided to be realized before operation \(O_{i^{\prime}k^{\prime}}\) using the same machine (\(l_{ijij}=l_{i^{\prime}k^{\prime}j^{\prime}}\)), and \(z_{ijij^{\prime}jk^{\prime}}=0\) otherwise. The problem is formulated as a mono-criterion optimization problem, avoiding the introduction of relative weights between criteria or the exploration of a Pareto frontier involving energy and make-span. The global criterion to be minimized is expressed as  
\[\min_{x,j,z}E_{T}=\sum_{i=1}^{n}\sum_{j=1}^{|A_{i}|}x_{ij}\cdot E_{ij} \tag{9}\]  
The considered constraints are  
\[\sum_{j\in A_{i}}x_{ij}=1\qquad i=1\,\text{to}\,n \tag{10}\]  
and for \(ij\), such as \(x_{ij}=1\):  
\[est_{1 ij}\leq t_{1 ij}\;\;i=1\,\text{to}\,n \tag{11}\]  
\[\max_{h\in\Gamma_{ik}^{-1}}\Bigl{\{}t_{ihj}+d_{ihj}+T_{ihj}\Bigr{\}}\leq t_{ kj}\;i=1\,\text{to}\,n,k=2\,\text{to}\,S_{i} \tag{12}\]  
\[t_{iS,j}+d_{iS,j}\leq dt_{i}\;i=1\,\text{to}\,n \tag{13}\]  
For \(ij\) and \(i^{\prime}j^{\prime}\), such as \(x_{ij}=x_{i^{\prime}j^{\prime}}=1\):  
\[\forall i\
eq i^{\prime},\;\forall j,j^{\prime},\;\forall k,\;k^{\prime}\; \text{with}\;l_{ikj}=l_{i^{\prime}k^{\prime}j^{\prime}}\;:\;z_{iji^{\prime}j^{ \prime}kk^{\prime}}+z_{i^{\prime}j^{\prime}k^{\prime}}=1 \tag{14}\]  
\[\forall i\
eq i^{\prime},\;\forall j,j^{\prime},\;\forall k,\;k^{\prime}\; \text{with}\;l_{ikj}\
eq l_{i^{\prime}k^{\prime}j^{\prime}}\;:\;z_{iji^{\prime} j^{\prime}kk^{\prime}}=z_{i^{\prime}j^{\prime}k^{\prime}}=0 \tag{15}\]  
and \(\forall i\
eq i^{\prime},\;\forall j,j^{\prime},\;\forall k,\;k^{\prime}\; \text{with}\;l_{ikj}=l_{i^{\prime}k^{\prime}j^{\prime}}\):  
\[t_{ikj}+d_{ikj}\leq t_{i^{\prime}k^{\prime}j^{\prime}}+V\Bigl{(}1-z_{iji^{ \prime}j^{\prime}kk^{\prime}}\Bigr{)}\;\text{and}\;t_{ikj}+d_{ikj}+V\cdot z_{iji^ {\prime}j^{\prime}kk^{\prime}}\geq t_{i^{\prime}k^{\prime}j^{\prime}} \tag{16}\]  
The significance of the different constraints are as follows: constraint (10): the choice of a unique path for each job; constraint (11): feasibility bounds for the starting time of the first operation of job \(i\) with machine assignment \(j\); constraint (12): starting time succession constraints along a path; constraint (13): due time constraints for the different jobs, where \(t_{iS,j}+d_{iS,j}\;\) is the completion time of job \(i\) along path \(j\); constraints (14), (15), and (16): non-overlapping of operations of chosen paths on the same machine, where \(V\) is a very large number. However, in situations in which the feasible time intervals for processing on a same machine (\(l_{ikj}=l_{i^{\prime}k^{\prime}j^{\prime}}\)) do not intersect, the value of the \(z\) variable is already fixed:  
\[lst_{ikj}+d_{ikj}\leq est_{i^{\prime}k^{\prime}j^{\prime}}\;:\;z_{iji^{\prime} j^{\prime}kk^{\prime}}=1 \tag{17}\]  
\[est_{ikj}\geq lst_{i^{\prime}k^{\prime}j^{\prime}}+d_{i^{\prime}k^{\prime}j^{ \prime}}\;:\;\;z_{iji^{\prime}j^{\prime}kk^{\prime}}=0 \tag{18}\]  
Problem (9)-(16) is a two-level optimization problem, where the machine assignment problem, with the objective of minimizing total energy consumption, is considered at the upper level (relations (9) and (10), with only decision variable \(x_{ij}\)), while at the lower level, the satisfaction of dynamic constraints (11)-(16) lead to a feasible scheduling. Different approaches appear of interest to generate solutions for instances of this problem, which is expected to be of the NP-Complete complexity class [32].