# Dynamic Job and Conveyor-Based Transport Joint Scheduling in Flexible Manufacturing Systems
## 3 Problem Description
### Problem Formulation  
We consider a dynamic environment in which jobs continuously arrive. We adopt a total rescheduling strategy, i.e., we recompute the schedule at every job arrival; we discuss such a choice in detail in Section 4.4. The aim of the scheduling is to minimize the _makespan_, i.e., the total execution time required to process all the tasks of the current set of jobs \(J(t)\). Formally, we have  
\[\underset{i\in[1,n(t)]}{\text{minimize}} \max\ C_{ij}\] (2) s.t. \[s_{ijk}+p_{ijk}=C_{ij} \tag{3}\] \[s_{ijk}+p_{ijk}+t_{kl}\leq s_{ij\gamma l} \forall\tau_{ij},\tau_{ij^{\prime}}|U_{ij\gamma^{\prime}}=1\] (4) \[\sum_{k}E_{ijk}=1 \forall\tau_{ij}\] (5) \[s_{ijk}+p_{ijk}<s_{i^{\prime}\gamma k} \forall\tau_{ij},\tau_{i^{\prime}\gamma^{\prime}},k\in[1,m]\] (6) \[\left[s_{ijk},\,s_{ijk}+p_{ijk}\right]\in A_{k}(t) \forall\tau_{ij},\ \forall k \tag{7}\]  
Equation (3) specifies that the end time of each task must be equal to its start time plus its processing time. Here, we omit the necessary time to store the material produced by the last task of each job. Equation (4) models the dependencies between tasks within the same job. If a task (\(j\)) is assigned to a machine (\(k\)), it has precedence over another task (\(j^{\prime}\)) assigned to the machine (\(l\)); the starting time of the task (\(j^{\prime}\)) must be greater or equal to the end time of the task (\(j\)) plus the transport time between the two machines. Equation (5) imposes the maximum number of machines to which a task can be assigned, i.e., one. Equation (6) limits the number of tasks a machine can process in parallel. Finally, Equation (7) indicates that tasks can be executed on the machines only during their availability intervals.  
The provided equations can be utilized to formulate and solve the constraints of a mixed linear integer programming (MILP) model. However, conventional MILP solvers, such as IBM CPLEX, face challenges in finding a solution within a reasonable time frame; more specifically, even with a modest number of jobs, they are unable to converge within a 12 h timeframe on standard hardware. This computational inefficiency arises due to the incorporation of transport time in Equation (4), where \(t_{kl}\) is contingent on the values derived from Equation (1), significantly escalating the computational complexity of the model. Consequently, we must turn to alternative methodologies that involve exploring the solution space.  
\begin{table}
\begin{tabular}{l l} \hline \hline \multicolumn{2}{c}{**Inputs**} \\ \hline \(M\) & Set of machines, \(\{1,2,\ldots,m\}\) \\ \(J(t)\) & Set of jobs \(\{1,2,\ldots,n(t)\}\) \\ \(h_{i}\) & Number of tasks of job \(i\) \\ \(\tau_{ij}\) & \(j\)th task of job \(i,j\in[1,h_{i}]\) \\ \(p_{ijk}\) & Processing time for \(\tau_{ij}\) on machine \(k\) \\ \(U_{i}\) & Precedence matrix for job \(i\): 1 if \(\tau_{ij}\) precedes \(\tau_{ij^{\prime}}\); otherwise, it is 0 \\ \(A_{k}(t)\) & Availability intervals for machine \(k\) \\ \(t_{kl}\) & Transfer time between machines \(k\) and \(l\) \\ \hline \multicolumn{2}{c}{**Auxiliary Variables**} \\ \hline \(E_{ijk}\) & 1 if \(\tau_{ij}\) is executed on machine \(k\); otherwise, it is 0 \\ \(s_{ijk}\) & Execution start time of \(\tau_{ij}\) on machine \(k\) \\ \(C_{ij}\) & Completion time of \(\tau_{ij}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Notation summary.