## 3 Problem Description and Methodology
### Mixed Integer Programming (MIP) Model  
Based on the above description, we formulate a MIP model for the \(1\big{|}r_{j},nr,fpm\big{|}\sum w_{j}T_{j}\) problem. The parameters and variables used in the model are as follows:  
* Parameters \(n\): number of jobs \(J_{j}\): job j \(L\): maximum working time limit \(MT\): maintenance time, which is a constant \(M\): a very large positive integer constant \(r_{j}\): release time of job \(j\) \(p_{j}\): processing time of job \(j\) \(w_{j}\): weight of job \(j\) \(d_{j}\): due date of job \(j\)
* Decision variables \(C_{j}\): completion time of job \(j\) \(T_{j}\): tardiness of job j, where \(T_{j}=max\big{(}0,C_{j}-d_{j}\big{)}\) \(X_{jk}\): 1 if job \(j\) is assigned at position \(k\) in the sequence, 0 otherwise \(Y_{k}\): 1 if maintenance activity is assigned after position \(k\) in the sequence, 0 otherwise \(Q_{k}\): continuous working time of machine after position \(k\) in the sequence \(ST_{k}\): start time at position \(k\) for processing in the sequence \(PT_{k}\): processing time for the job assigned at position \(k\) in the sequence \(CT_{k}\): completion time at position \(k\) in the sequence To obtain a feasible schedule, variables \(X_{jk}\) and \(Y_{k}\) are binary and decide which job is assigned at position \(k\) and whether a maintenance activity is assigned after position \(k\), as shown in Figure 1. This is based on the following constraints. Each job must be arranged into exactly one position  
\[\sum_{k=1}^{n}X_{jk}=1\quad\quad\forall\quad j=1,2,3,\ldots,n \tag{1}\]  
Each position must be occupied by exactly one job  
\[\sum_{j=1}^{n}X_{jk}=1\quad\quad\forall\quad k=1,2,3,\ldots,n \tag{2}\]  
For each position \(k\), the start time for the processing job can be given by  
\[ST_{k}\geq\sum_{j=1}^{n}(r_{j}\cdot X_{jk})\quad\quad\forall\quad k=1,2,3, \ldots,n \tag{3}\]  
\[ST_{k}\geq CT_{k-1}+(MT\cdot Y_{k-1})\quad\forall\quad k=2,3,4,\ldots,n \tag{4}\]  
For each position \(k\), the processing time for the assigned job can be given by  
\[PT_{k}=\sum_{j=1}^{n}(p_{j}\cdot X_{jk})\quad\quad\forall\quad k=1,2,3,\ldots,n \tag{5}\]  
For each position \(k\), the completion time of position \(k\) should be satisfied by  
\[CT_{k}\geq ST_{k}+PT_{k}\quad\quad\forall\quad k=1,2,3,\ldots,n \tag{6}\]  
For the first position, the continuous working time can be given by  
\[Q_{1}=\sum\
olimits_{j=1}^{n}\bigl{(}p_{j}\cdot X_{j1}\bigr{)} \tag{7}\]  
For each position \(k\), excluding the first position, the continuous working time can be given by  
\[Q_{k-1}+\sum\
olimits_{j=1}^{n}(p_{j}\cdot X_{jk})\leq Q_{k}+(M\cdot Y_{k-1}) \quad\forall\quad k=2,3,4,\ldots,n \tag{8}\]  
\[\sum\
olimits_{j=1}^{n}(p_{j}\cdot X_{jk})\leq Q_{k}+M\cdot(1-Y_{k-1})\quad \forall\quad k=2,3,4,\ldots,n \tag{9}\]  
In the above two equations, we apply the \(M\) value, a very large positive constant, to obtain the continuous working time for each position. If \(Y_{k-1}=0\), then the continuous working time at position \(k\) (\(Q_{k}\)) will be forced to be \(Q_{k-1}+\sum\
olimits_{j=1}^{n}(p_{j}\cdot X_{jk})\); on the other hand, if \(Y_{k-1}=1\), then the continuous working time at position \(k\) (\(Q_{k}\)) will be \(\sum\
olimits_{j=1}^{n}(p_{j}\cdot X_{jk})\). \[\sum_{k=1}^{n}X_{jk}=1\quad\quad\forall\quad j=1,2,3,\ldots,n \tag{1}\]0 Feasible schedule. For each position, the continuous working time should satisfy  
\[\sum_{k=1}^{n}X_{jk}=1\quad\quad\forall\quad j=1,2,3,\ldots,n \tag{1}\]1  
At the end of the sequence, there is no need to maintain the machine:  
\[\sum_{k=1}^{n}X_{jk}=1\quad\quad\forall\quad j=1,2,3,\ldots,n \tag{1}\]2  
For each job, the completion time can be given by  
\[C_{j}+M\cdot(1-X_{jk})\geq CT_{k}\quad\forall\quad \begin{cases}j=1,2,3,\ldots, n\\ k=1,2,3,\ldots,n\end{cases}