## 4 The Parametric PERT/CPM Method for Finding the Optimum Schedule
### The Prohibited Intervals Method B
In our numeric example in Figure 2\(T_{1}=T_{2}=200.5\), \(T=T_{1}+T_{2}=401\), which gives the sequence of operation completion times as follows:  
\[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]1 \[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]2  
Thus we obtained the following robot route:  
\[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]3  
This sequence of robot moves is the same for any of the two-cyclic schedules defined by time intervals \(T_{1}=191+x\) and \(T_{2}=210-x\), where \(0\leq x\leq 9.5\). Now consider the 2-cyclic schedules defined by the time intervals \((T_{1},T_{2})=(151,250)\) and \(T=T_{1}+T_{2}=401\). In this case, the sequence of operation completion times differs from the previous case:  
\[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]4 \[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]5  
The Gantt chart of this 2-cyclic schedule is presented in \[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]6  
The Gantt chart in Figure 5 has the same notations as \[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]7 The main difference between the two diagrams is that Figure 5 shows the optimal 2-cyclic schedule of the robot. In this notation, the corresponding periodic route of the loaded robot is as follows:  
\[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]8  
\[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]9 The Gantt chart for the optimal two-cyclic schedule \((T_{1},T_{2})=(151,250)\), \(T_{avr}=200.5\). As seen previously in Figure 2, the robot's movement is shown with a red dotted line. The numbers in the chart indicate the time the robot arrives at and leaves the corresponding workstations. The processing life of microplates is indicated by horizontal lines highlighted with small triangles, squares, and diamonds, respectively. The optimal two-cyclic schedule shown in Figure 5 is (\(T_{1}\), \(T_{2}\)) = (151, 250). _Complexity of the proposed PERT/CPM/PIM algorithm._ In concluding this section, we note that the worst-case complexity of the parametric PERT/CPM algorithm in Section 4 is the same as the complexity of the corresponding critical path-finding algorithm in [21], that is, O(\(m^{3}\)), while the complexity of the prohibited interval method is O(\(nr^{3}\)log \(m\)) [15]. Therefore, the complexity of the combined PERT/CPM/PIM algorithm, in the worst case, is O(\(m^{2}\)log \(m\)). _Discussion._ The main practical purpose of this work is twofold. First, we propose an algorithm that efficiently--in polynomial time--generates a set of optimal schedules with cycle times (\(T_{1}\), \(T_{2}\)) = (191 + \(x\), 210 - \(x\)), where \(x\in[0\), 9.5], which includes, as particular cases, the optimal solutions obtained by methods [11; 12; 13; 14]. Indeed, if \(x=9.5\), we obtain the one-cyclic schedule \(T=T_{1}=T_{2}=200.5\) found in [14]; if we set \(x=0\), then we obtain a 2-cyclic schedule with \(T_{1}=191\) and \(T_{2}=210\), the same as in [11]. Note that the 2-cyclic optimal schedule defined by times (\(T_{1}\), \(T_{2}\)) = (151, 250) and the corresponding robot route \(R\) presented above have not been discovered by the algorithms [11; 12; 13; 14]. Another important feature of the proposed method is that it significantly generalizes existing MIP and Petri net methods in the sense that it generates robust optimal two-cyclic schedules. Indeed, recall that a schedule is said to be robust if its cycle time \(T\) is insensitive to unexpected disturbances and/or can be easily corrected by a predetermined control policy. Let the resulting 2-cyclic schedule with times (\(T_{1}\), \(T_{2}\)) = (191 + \(x\), 210 - \(x\)) be fixed for some \(x\in(0\), 9.5). Assume that due to unforeseen variations in the processing times of operations, a certain microplate, instead of the planned cycle time \(T_{1}\), will be delayed by some fixed deviation \(\delta\), that is, it will have a cycle time \(T_{1}+\delta\). The controller will then select the next scheduled microplate to start \(\delta\) time units earlier, i.e., the next cycle time will be \(T_{2}-\delta\).