Efficient Optimal Cyclic Scheduling of High Throughput Screening System for Enzyme-Linked Immunoassay
针对酶联免疫吸附试验的高通量筛选系统，提出一种多项式时间算法，通过Petri网建模和死锁避免策略，将调度问题转化为连续优化问题，从而高效求得最优循环调度方案。
Nowadays, biochemical and biomedical laboratories, and pharmaceutical industries widely adopt high throughput screening (HTS) systems for the development of new drugs and detection of new viruses. Different from a flow shop in manufacturing systems, in operating an HTS system, microplates are often required to be processed multiple times by some devices, resulting in complex microplate flows. Such flows make the system deadlock-prone and very difficult to deal with. Also, consistency is essential for its operation, requiring a one-microplate cyclic schedule for its operation. Generally, the scheduling problem of such systems is NP-hard due to their combinatorial nature. Thus, scheduling an HTS system is challenging. Antibody detection is an important complement to the nucleic acid test for response to the coronavirus disease pandemic and is adopted in many laboratories, which can be implemented by the enzyme-linked immunoassay (ELISA) via an HTS system. This article focuses on the problem of scheduling an HTS for ELISA and explores the possibility of a polynomial algorithm for finding an optimal one-microplate cyclic schedule. To do so, we model the system via a type of Petri nets and develop an optimal deadlock avoidance policy. As a result, the optimal activity sequence can be simply obtained. With the obtained sequence, the scheduling problem is converted to a continuous optimization problem that can be solved by determining the robot waiting time at the devices. Then, a one-microplate cyclic schedule can be efficiently found by solving a small-sized linear programming (LP) problem. Moreover, it is shown that, for many cases, one can quickly get an optimal solution by simply setting the robot waiting time without solving an LP problem. Consequently, we successfully present a polynomial algorithm to get an optimal cyclic schedule and show that the addressed problem is polynomial-time solvable. A practical example is used to show its applications.