Dynamically Optimizing Experiment Schedules of a Laboratory Robot System with Simulated Annealing

• Published in: Journal of Laboratory Automation 2014-12, Vol.19 (6), p.517-527
• Main Authors: Cabrera, Cristina, Fine-Morris, Morgan, Pokross, Matthew, Kish, Kevin, Michalczyk, Stephen, Cahn, Matthew, Klei, Herbert, Russo, Mark F.
• Format: Article
• Language: English
• Subjects: automated biology; engineering; informatics and software; programming; structural biology; systems
• ISSN: 2472-6303; 2211-0682; 2472-6311; 1540-2452
• DOI: 10.1177/2211068214546493

A scheduler has been developed for an integrated laboratory robot system that operates in an always-on mode. The integrated system is designed for imaging plates containing protein crystallization experiments, and it allows crystallographers to enter plates at any time and request that they be imaged at multiple time points in the future. The scheduler must rearrange tasks within the time it takes to image one plate, trading off the quality of the schedule for the speed of the computation. For this reason, the scheduler was based on a simulated annealing algorithm with an objective function that makes use of a linear programming solver. To optimize the scheduler, extensive computational simulations were performed involving a difficult but representative scheduling problem. The simulations explore multiple configurations of the simulated annealing algorithm, including both geometric and adaptive annealing schedules, 3 neighborhood functions, and 20 neighborhood diameters. An optimal configuration was found that produced the best results in less than 60 seconds, well within the window necessary to dynamically reschedule imaging tasks as new plates are entered into the system.