Scheduling a Life Science High-Throughput Platform under Starvation Constraints Using Timed Transition Petri Nets and Heuristic Search
Tao Hong, Mo–Yuen Chow, Perry Haaland, Dylan Wilson, Robert Walker · 2007
High-throughput (HT) platforms have been increasingly used in the life science area for diverse bio-chemical experiments. This paper addresses the scheduling of HT platform based experiments under multiple constraints, such as operation constraints, resource constraints and starvation constraints. We use timed transition Petri nets (PN) to model the experimental process with constraints. We first propose the transition variant property of the PN model. We then propose the HCH (Hong-Chow-Haaland) algorithm, which is customized from A* algorithm, to find a feasible solution. HCH algorithm is more efficient than L1 algorithm and most other A* extended algorithms in identification of new markings when applied to the transition variant PN. We then applied HCH algorithm to two typical HT processes. The results show that HCH algorithm can be used to find optimal solutions with the time complexity of identifying new markings less than 2% of the L1 algorithm.