###### Abstract  
High-throughput screening systems are robotic cells that automatically scan and analyze thousands of biochemical samples and reagents in real time. The problem under consideration is to find an optimal cyclic schedule of robot moves that ensures maximum cell performance. To address this issue, we proposed a new efficient version of the parametric PERT/CPM project management method that works in conjunction with a combinatorial subalgorithm capable of rejecting unfeasible schedules. The main result obtained is that the new fast PERT/CPM method finds optimal robust schedules for solving large size problems in strongly polynomial time, which cannot be achieved using existing algorithms. cyclic robot scheduling; high-throughput screening; parametric PERT/CPM; project management; polynomial time algorithm +
Footnote †: journal:  
0000-0001-5000-0000-0000-0000-0000-0000-0000-0000-0000-00000-00000-00000-00000-00000-00000-00000-00000-00000-  
microplate can re-enter the corresponding workstations (in scheduling theory, this type of process is called a re-entry flowshop). The microplate processing time of a workstation is the minimum time that a microplate must remain on a workstation before the robot moves it to the next workstation. While a microplate remains on the workstation, the next microplate cannot enter it; in scheduling theory, this condition is called blocking. The goal is to find a cyclic schedule of robot moves that minimizes cycle time, i.e., maximizes cell productivity. From the point of view of scheduling theory, the scheduling problem under consideration is a cyclic single-robot, multiple-machine flowshop scheduling problem with blocking and re-entry [5; 6; 7]. An HTS system with an optimal schedule can minimize the overall screening time, maximizing the throughput and hence reducing associated costs and enabling diagnosis of diseases and rapid discovery of new drugs [8; 9; 10]. The scheduling problem under consideration has a complex combinatorial structure and is difficult to solve. In recent decades, several popular methods, such as mixed integer programming (MIP), Petri nets, max-plus algebra, greedy heuristics, and genetic algorithms, have been used to find optimal schedules for HTS processes. However, many existing methods have prohibitively high exponential computational complexity in the worst case and therefore cannot be guaranteed to quickly find the optimal solution for large problem instances. This raises the question of whether there is a method for such scheduling problems that can find the optimal schedule for arbitrary data in polynomial time. In what follows, we give a positive answer to this question; namely, we develop a new efficient and practical version of the PERT/CPM project management method to solve this problem. To demonstrate the validity and practical usefulness of the new method, we focus on the theoretical and numerical analyses of the HTS process for enzymatic assays. Although the scheduling problem under consideration is complex and NP-hard, we solve it efficiently using the proposed method if the number of screening operations is limited, which is a condition usually encountered in practice [11; 12]. This result complements the original studies of [PERSON] et al. [11; 13] and [PERSON] et al. [12; 14], who used mixed integer programming and resource-oriented Petri nets, respectively, to model, analyze, and solve the HTS scheduling problem for enzymatic assays. The proposed PERT/CPM method works in conjunction with the prohibited intervals subalgorithm [15], which weeds out unfeasible solutions and finds the optimal schedule in strongly polynomial time (in the number of operations \(m\)), \(\mathrm{O}(m^{3}\) log \(m\)), which, as far as we know, cannot be achieved using existing algorithms. This worst-case polynomial complexity is a major advantage over the existing HTS scheduling algorithms mentioned above.