## 4 The Parametric PERT/CPM Method for Finding the Optimum Schedule
### Description of the PERT/CPM Algorithm A  
This algorithm considers the case where the processing times of operations are flexible and bounded by their low bounds. In addition, the time required to complete the sequence of operations in the HTS system is limited by the specified screening time constraints, which will be presented below. We show that for any given robot route, this problem reduces to the parametric critical path problem, which is a well-solvable special case of a general linear programming problem. Unlike linear programming, the parametric critical path algorithm is executed in a time that is strongly polynomial in the number of operations. Consider a 1-cyclic robot route, and let \(T\) be its (unknown) cycle length. The completion time of operation \(O_{k}\) performed in interval \([0\), \(T)\), \(k=0\), \(1\), \(\ldots\), \(5\) is denoted by \(t_{k}\). Let us take \(t_{0}=0\), i.e., assume that the cycle \([0\), \(T)\) starts when the robot takes a microplate from workstation \(M_{0}\) (Cytomat2C). The time in the cycle \([0\), \(T)\) when the (next instance of) operation \(O_{0}\) starts is denoted using \(t_{6}\). Note that the microplate, having completed its operation \(O_{0}\) at time \(t_{0}=0\) starts this instance of this operation at time \(t_{6}-T\). The cyclic robot route is denoted using \(R=(O_{0}\), \(O_{[1]}\), \(O_{[2]}\), \(O_{[3]}\), \(O_{[4]})\). This means that at time \(t_{0}=0\), the robot picks up the microplate from workstation \(M_{0}\) and moves it to workstation \(M_{1}\). If operation \(O_{[1]}\) is performed on workstation \(M_{1}\), i.e., \([1]=1\), then the robot waits for operation \(O_{1}\) to complete at time \(t_{1}\). If \([1]\
eq 1\), then the unloaded robot moves to the workstation performing operation \(O_{[1]}\) and waits there for operation \(O_{[1]}\) to complete at time \(t_{[1]}\). At time \(t_{[1]}\), the robot picks up the microplate and moves it to the next workstation in the screening process sequence \(S\), as defined in Section 2. If this workstation does not perform operation \(O_{[2]}\), then the unloaded robot moves to another workstation that performs operation \(O_{[2]}\). Similar robot actions are associated with operations \(O_{[2]}\), \(O_{[3]}\), and \(O_{[4]}\). At time \(T\), the robot takes the next microplate from workstation \(M_{0}\) and repeats the same steps as in the previous cycle. We can now reformulate our cyclic scheduling problem as the following special-type parametric linear programming problem \(\mathbf{P}\) with \(t_{0}=0\) and variables \(T\), \(t_{1}\), \(\ldots\), \(t_{6}\) defined for any specific robot route and introduced below:  
Problem \(\mathbf{P}\): Minimize \(T\)  
subject to  
The robot move constraints:  
\[t_{[k]}\geq t_{[k-1]}+d_{[k-1]}\text{, }k=1,2\ldots\text{, }5\text{; }t_{[5]}=T. \tag{1}\]The processing time constraints:  
\[p_{k}=t_{k}-t_{k-1}-d_{k-1}\geq l_{k}\text{, if }t_{k}>t_{k-1},k=1,2,4; \tag{2a}\] \[p_{k}=t_{k}+T-t_{k-1}-d_{k-1}\geq l_{k}\text{, if }t_{k}<t_{k-1},k=1,2,4;\] (2b) \[p_{3}=t_{3}-t_{2}+(\beta-1)T-d_{2}\geq l_{3}\text{, if }t_{2}<t_{3}\text{ and }t_{3}\
eq t_{2}+d_{2};\] (2c) \[p_{3}=t_{3}+\beta\ T-t_{2}-d_{2}\geq l_{3}\text{, if }t_{3}<t_{2}\text{ or }t_{3}=t_{2}+d_{2};\] (2d) \[p_{0}=t_{0}+T-t_{6}\geq l_{0};\] (2e) \[p_{5}=t_{5}-t_{4}-d_{4}\geq l_{3}. \tag{2f}\]  
Screening time constraints:  
\[t_{1}+d_{1}+T-t_{6}\leq 152; \tag{3a}\] \[t_{1}+d_{1}-t_{0}-d_{0}\leq 44;\] (3b) \[t_{3}+d_{3}+(\beta-1)T-t_{0}-d_{0}\leq 369\text{, if }t_{2}<t_{3};\] (3c) \[p_{k}=t_{k}-t_{k-1}-d_{k-1}\geq l_{k}\text{, if }t_{k}>t_{k-1},k=1,2,4; \tag{2a}\]0  
Overlapping constraints:  
\[p_{k}=t_{k}-t_{k-1}-d_{k-1}\geq l_{k}\text{, if }t_{k}>t_{k-1},k=1,2,4; \tag{2a}\]1 \[p_{k}=t_{k}-t_{k-1}-d_{k-1}\geq l_{k}\text{, if }t_{k}>t_{k-1},k=1,2,4; \tag{2a}\]2 (4b) \[p_{k}=t_{k}-t_{k-1}-d_{k-1}\geq l_{k}\text{, if }t_{k}>t_{k-1},k=1,2,4; \tag{2a}\]3  
The robot-move constraints (1) ensure that the robot has enough time to complete all its movements without delay.