## 4 The Parametric PERT/CPM Method for Finding the Optimum Schedule
### The Prohibited Intervals Method B  
Once the optimal processing times of screening operations have been found by the PERT/CPM subalgorithm in the previous subsection, these values are then used as inputs for subalgorithm \(B\), described below. The main goal of this subalgorithm is to find an optimal 2-cyclic solution whose average cycle time is no less than the optimal 1-cyclic time and which, in addition, is robust, a useful property which will be discussed below. Let us start with a brief description of the corresponding method for solving scheduling problems, called the prohibited intervals method, which was discovered in the early 1960s by a group of Byelorussian mathematicians [28; 29; 30]. In [15], we improved this method and obtained a modification that optimally solves the problem in polynomial time. In this work, we develop and modify this method to highlight the features of HTS scheduling. Description of the prohibited intervals. Consider the processing sequence \(O=(O_{0},\,O_{1},\,O_{2},\,O_{3},\,O_{4},\,O_{5})\) for microplates, which was discussed in the problem definition in Section 2. The completion time for operation \(O_{k}\) for a microplate starting at time 0 is denoted by \(Z_{k}\). Evidently, the following relations hold:  
\[Z_{0}=p_{0};\,Z_{k}=Z_{k-1}+d_{k-1}+p_{k},\,k=1,\ldots,5,\]  
where the timing parameters \(d_{k}\) and \(p_{k}\) are as defined in Section 2. Suppose that some workstation performs an operation \(O_{j}\), and that this workstation carries out this operation sequentially on two microplates, one of which starts at time 0, and the other of which starts at time \(T\). This workstation can sequentially perform the considered operation on these two microplates without time overlapping in the case when  
\[Z_{j}\leq T+Z_{j}-p_{j},\,\text{i.e.,}\,p_{j}\leq T.\]  
Thus,  
\[Max\,p_{j}\leq T,\,j=0,\,1,\,2,\,4,\,5. \tag{5}\]  
Suppose now that some microplate begins the screening process at time \(T\). Then the operation \(O_{k}\) of this microplate is completed at time  
\[T+Z_{k},\,k=0,\,1,\ldots,5.\]  
Consider a pair of operations, denoted \(i\) and \(j\), where \(i<j\). Let operation \(i\) be carried out by the microplate starting at time \(T\), and operation \(j\) carried out by the microplate starting at time 0. Two cases are possible:  
Case 1: \(T+Z_{i}\leq Z_{j}\). In this case, the robot can transport the microplate that has completed operation \(O_{i}\), and then transport the microplate that has completed operation \(O_{j}\), if \(T+Z_{i}+d_{i}\leq Z_{j}\). Case 2: \(Z_{j}\leq T+Z_{i}\). In this case, the robot can transport the microplate that has completed operation \(O_{i}\), and then transport the microplate that has completed operation \(O_{i}\), if \(Z_{j}+d_{j}\leq T+Z_{i}\). Combining the above inequalities \(T+Z_{i}+d_{i}\leq Z_{j}\) and \(Z_{j}+d_{j}\leq T+Z_{i}\), we obtain that the time interval between any two microplates introduced into the screening process must satisfy the following resulting condition:  
\[T\
otin(Z_{j}-Z_{i}-d_{i},\,Z_{j}-Z_{i}+d_{j}),\,i<j;\,i,j=0,\,1,\ldots,4. \tag{6}\]  
The resulting intervals \((Z_{j}-Z_{i}-d_{i},\,Z_{j}-Z_{i}+d_{j})\), for all pairs \(i,j\) are called _prohibited_. The points within any of these intervals correspond to unfeasible values of the cycle time \(T\). Recall that after operation \(O_{5}\) is completed at workstation \(M_{0}\) (Cytomat2C), the microplate is delivered to the storage center by a special auxiliary device, and not by a robot. Therefore, the intervals in (6) do not include the variable \(Z_{5}\). Workstation \(M_{0}\) performs operations \(O_{0}\) and \(O_{5}\). These operations do not overlap in time on workstation \(M_{0}\) if: (1) a previous microplate has completed operation \(O_{5}\) earlier than the next microplate starts operation \(O_{0}\), i.e., \(Z_{5}\leq T+Z_{0}-p_{0}\); or (2) a previous microplate has started operation \(O_{5}\) after the next microplate has completed operation \(O_{0}\), \(T+Z_{0}\leq Z_{5}-p_{5}\).