## 3 Proposed Solution Approach for \(Qm,h_{in_{i}}|a|C_{max}\)
### Mathematical Model  
Let  
\[x_{ijk}=\left\{\begin{array}{ll}1&\text{if job $j$ is executed on machine $i$ during $k^{th}$ availability interval}\\ 0&\text{Otherwise.}\end{array}\right.\]  
\[y_{ik}=\left\{\begin{array}{ll}1&\text{if all jobs on machine $i$ are completed before the start of $k^{th}$ unavailability period}\\ 0&\text{Otherwise.}\end{array}\right.\]  
Using the above-listed decision variables, the problem can be modeled as a quadratic program as follows:  
\[\text{\emph{Minimize}}\ C_{max}=Max_{j}\ C_{j} \tag{1}\]  
Subject to  
\[\sum_{k=1}^{n_{i}+1}\sum_{j=1}^{n}p_{ij}x_{ijk}+\sum_{k=1}^{n_{i}-1}\Big{(} \sum_{l=1}^{k}(e_{il}-s_{il})\Big{)}y_{ik}\leq\sum_{k=1}^{n_{i}}s_{ik}y_{ik}+d (1-\sum_{k=1}^{n_{i}}y_{ik})\ \ i=1,\ldots,m, \tag{2}\]  
where \(d\) is a large positive number.  
\[\sum_{k=1}^{n_{i}+1}\sum_{j=1}^{n}p_{ij}x_{ijk}+\sum_{k=1}^{n_{i}}(e_{ik}-s_{ ik})(1-\sum_{l=1}^{k}y_{il})+\sum_{k=1}^{n_{i}}\Big{[}(s_{ik}-e_{ik-1})-\sum_{j=1 }^{n}p_{ij}x_{ijk}\Big{]}\Big{[}1-\sum_{l=1}^{k}y_{il}\Big{]}\leq C_{max} \tag{3}\]  
\[\sum_{k=1}^{n_{i}}y_{ik}\leq 1\ \ i=1,\ldots,m \tag{4}\]  
\[\sum_{j=1}^{n}p_{ij}x_{ijk}\leq s_{ik}-e_{ik-1}\ \ i=1,\ldots,m\ ;k=1,\ldots,n_{i} \tag{5}\]  
\[\sum_{i=1}^{m}\sum_{k=1}^{n_{i}+1}x_{ijk}=1\ \ j=1,\ldots,n \tag{6}\]  
\[x_{ijk}\in\{0,1\}\ \ i=1,\ldots,m;\ j=1,\ldots,n\ k=1,\ldots,n_{i}+1 \tag{7}\]  
\[y_{ik}\in\{0,1\}\ \ i=1,\ldots,m;\ k=1,\ldots,n_{i} \tag{8}\]  
Equation (1) minimizes the makespan. Equation (2) guarantees that, when all jobs are completed before the start of the 1 st unavailability period, the unavailability duration is not considered in the evaluation of the completion time of the last job assigned to machine \(i\). There are \(m\) of these constraints.  
Equation (3) states that the completion time of the last job assigned to machine \(i\) is at most equal to the makespan. There are \(m\) of these constraints. Equation (4) guarantees that no more than one \(y_{ik}\) is equal one for a given machine \(i\). There are \(m\) of these constraints. The total processing time of the jobs assigned to a given availability interval cannot exceed the length of that interval. This is shown by Equation (5). There are \(m\sum n_{i}\) of these constraints. Equation (6) assures that, if a job is assigned to a machine, it can be processed on only one availability interval of that machine. There are \(n\) constraints of this type. Equations (7) and (8) define the non-negativity constraints about the decision variables used to develop the mathematical model.  
The above quadratic model (\(QM\)) can be optimally solved by CPLEX for problem instances with up to 73 machines. Therefore, a good polynomial algorithm that can solve large and more complicated problems, and provide promising results is of great interest.  
The Largest Processing Time algorithm (\(LPT\)) is a famous rule used to build heuristics for scheduling problems with a makespan criterion. For example, in [15] the authors proposed \(LPT\)-based heuristics to solve \(Q2||Cmax\) and \(Qm,ai||Cmax\) problems, respectively. The \(LPT\) rule sorts jobs into a nonincreasing order of their processing times and then assigns a job to the machine on which it can finish as early as possible.