# Beyond Kanban: POLCA-Constrained Scheduling for Job Shops
## 3 POLCA and the Enhanced Contraint Programming: A Basic Case
### The Proposed Methodology
#### 3.3.1 Constraint Programming Model  
The constraint programming model is formulated to schedule jobs on workcenters while minimizing the total tardiness across all orders. Prior to presenting the model, Table 1 summarizes the notation employed in the formulation. The CP model is constructed with the following objective and constraints:  
\[\text{Min}\quad\text{StaticLex}\left(\underbrace{\max_{i}\text{ LengthOf}(\text{ordItv}_{i})}_{\text{(i) Max Lead Time}},\underbrace{\sum_{i}\tau_{i}}_{\text{(ii) Sum of Tardiness}},\underbrace{\sum_{i}\text{LengthOf}(\text{ordItv}_{i})}_{\text{(iii) Sum of Lead Times}}\right) \tag{1}\] \begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Description** \\ \hline \(M\) & Number of workcenters \\ \(N\) & Number of orders \\ \(\mathcal{I}_{i}\) & Number of jobs of order \(i\) \\ \(\mathcal{M}=\{1,\ldots,M\}\) & Set of all workcenters \\ \(\mathcal{N}=\{1,\ldots,N\}\) & Set of all orders \\ \(\mathcal{J}_{i}=\{1,\ldots,j_{i}\}\) & Sorted set of all jobs of order \(i\) \\ \(p_{i,j}\) & Processing time of job \(j\) in order \(i\) \\ \(\mu_{i,j}\) & Workcenter of job \(j\) in order \(i\) \\ \(\mathcal{O}_{m}=\{(i,j):\forall i\in\mathcal{N},j\in\mathcal{J}_{i}|\mu_{i,j}=m\}\) & Set of jobs assigned to workcenter \(m\) \\ \(\mathcal{L}_{m_{1},m_{2}}=\{(i,j):\forall i\in\mathcal{N},j\in\mathcal{J}_{i}|( \mu_{i,j-1},\mu_{i,j})=(m_{1},m_{2})\}\) & Set of jobs representing transitions between workcenters \(m_{1}\) and \(m_{2}\) \\ \(a_{i}\) & Arrival time of order \(i\) \\ \(d_{i}\) & Due time of order \(i\) \\ \(C\) & Maximum number of active POLCA cards \\ \(\text{ordItv}_{i}\) & Interval variable for order \(i\) \\ \(\text{jobItv}_{i,j}\) & Interval variable for job \(j\) in order \(i\) \\ \(\text{loopItv}_{i,j}\) & Interval variable for POLCA card \(\mu_{i,j-1}|\mu_{i,j}\) utilization \\ \(\tau_{i}\) & Integer variable corresponding to tardiness of order \(i\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notation used in the constraint programming model. Subject to:  
\[\text{SizeOf(jobItv}_{i,j})=p_{i,j},\forall i\in\mathcal{N},j\in \mathcal{J}_{i} \tag{2}\] \[\text{Span}\Big{(}\text{ordItv}_{i},\,\{\text{jobItv}_{i,j}:\forall j \in\mathcal{J}_{i}\}\Big{)},\forall i\in\mathcal{N}\] (3) \[\text{EndBeforeStart}\Big{(}\text{jobItv}_{i,j},\text{jobItv}_{i,j +1}\Big{)},\forall i\in\mathcal{N},j\in\{1,\dots,J_{i}-1\}\] (4) \[\text{StartOf(ordItv}_{i})\geq a_{i},\forall i\in\mathcal{N}\] (5) \[\text{EndOf(ordItv}_{i})\leq d_{i}+\tau_{i},\forall i\in\mathcal{N}\] (6) \[\text{NoOverlap}\Big{(}\{\text{jobItv}_{i,j}:\forall(i,j)\in \mathcal{O}_{m}\}\Big{)},\forall m\in\mathcal{M}\] (7) \[\text{StartAtStart(loopItv}_{i,j},\,\text{jobItv}_{i,j-1}),\forall i \in\mathcal{N},j\in 2,\dots,J_{i}\] (8) \[\text{EndAtEnd(loopItv}_{i,j},\,\text{jobItv}_{i,j}),\forall i \in\mathcal{N},j\in 2,\dots,J_{i}\] (9) \[\text{AlwaysIn}\left(\sum_{(i,j)\in\mathcal{L}_{m_{1},m_{2}}} \text{Pulse(loopItv}_{i,j},1),\,[0,T],\,[0,C]\right),\forall(m_{1},m_{2})\in \mathcal{M}\times\mathcal{M}:m_{1}\
eq m_{2} \tag{10}\]  
Equation (1) defines the lexicographic multi-objective function, which minimizes sequentially (i) the maximum lead time across orders, (ii) the sum of tardiness, and (iii) the sum of lead times. Equation (4) ensures that, within each order, the start time of job \(j+1\) cannot precede the completion of job \(j\). Equation (5) enforces that each order interval cannot start before its arrival time \(a_{i}\). Equation (3) ensures that the interval variable for each order \(i\) begins with the first scheduled job and ends with the last one. Equation (6) defines the tardiness \(\tau_{i}\) of each order as the non-negative difference between the completion time of the last job and the order's due time \(d_{i}\). Equation (7) enforces that no two tasks assigned to the same workcenter \(m\) overlap in time, thereby guaranteeing the exclusive use of each workcenter.