## 4 The Parametric PERT/CPM Method for Finding the Optimum Schedule
### Description of the PERT/CPM Algorithm A
Inequalities (2a) take into account the case when the operation \(O_{k}\) starts and ends within the cycle \([0,T)\). Inequalities (2b) consider the case where the operation \(O_{k}\) starts in the cycle \([0,T)\) and ends in the next cycle \([T,2T)\). Inequalities (2c,d) take into account the case where the processing time of microplates at workstation \(M_{3}\) exceeds the cycle time \(T\). The parameter \(\beta\) determines the number of simultaneously processed microplates at workstation \(M_{3}\). In the case where \(t_{3}=t_{2}+d_{2}\) in inequality (2d), the robot simultaneously unloads the microplate from workstation \(M_{3}\) and loads the next microplate onto it. Inequalities (2e,f) determine the processing time of operations \(O_{0}\) and \(O_{5}\), respectively. Inequality (3a) requires that the interval between the starts of operations \(O_{0}\) and \(O_{2}\) does not exceed the specified value of 152 s.  
Inequality (3b) requires that the interval between the starts of operations \(O_{1}\) and \(O_{2}\) should not exceed 44 s. Inequalities (3c,d) require that the interval between the starts of operations \(O_{1}\) and \(O_{4}\) of the same microplate should not exceed 369 s. Constraint (4a) ensures that operations \(O_{0}\) and \(O_{5}\) do not overlap in time on workstation \(M_{0}\). Constraints (4b,c) ensure that operations \(O_{2}\) and \(O_{4}\) do not overlap in time on workstation \(M_{2}\). At this stage we need to modify the parametric critical path approach originally proposed by the authors in [21]. We reformulate Problem P above as a parametric critical path model as follows. A graph, \(G_{P}\), is constructed, in which each \(t\)-variable in constraints (1)-(4c) corresponds to a node of the graph. Next, each constraint in problem P is presented in the form \(t_{j}\geq t_{i}+(a+bT)\), where \(i,j\in(1,2,\ldots,6)\), \(a\) is a real number, and \(b\) is an integer. To this constraint we associate a directed arc \(c_{ij}\) in the graph \(G_{P}\) leading from node \(i\) to node \(j\) and having length \(w_{ij}=a+bT\) (see Figure 4). Thus, problem P reduces to the following parametric critical path problem, denoted Problem Q:Problem **Q**. For any specific robot route, find the minimum value of parameter \(T\) in the constructed graph \(G_{P}\), such that the graph does not contain cycles of positive length. The proof of this reduction is given in [21]. The parameter \(\beta\) in (2c,d) and (3c,d), although it expands the problem formulation in [21], does not violate the proof. Note that as soon as a specific robot's path is chosen and fixed, the logical (disjunctive) conditions in Problem **P** acquire only one possible outcome; that is, they cease to be disjunctive. As a result, for each fixed robot route, Problem P is transformed into a special type of a linear programming problem, which reduces to a parametric shortest path problem as proven by the authors in [21]. Now we can solve Problem Q for all robot routes repeatedly using the parametric critical path algorithm [21]. This part of the algorithm requires a routine repeated computation of a cycle time in graph \(G_{P}\) for each available robot route, the total number of which is a small constant. Omitting the intermediate routine calculations for each candidate robot's routes, we obtain the minimum 1-cyclic time \(T=200.5\), which is obtained for the robot route \(R=(O_{0},\)\(O_{4},\)\(O_{1},\)\(O_{2},\)\(O_{3})\) and \(\beta=2\).