SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automation
During laboratory automation of life science experiments, coordinating specialized instruments and human experimenters for various experimental procedures is important to minimize the execution time. In particular, the scheduling of life science experiments requires the consideration of time constra...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2023-08-01
|
| Series: | SLAS Technology |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2472630323000195 |
| _version_ | 1827871746706898944 |
|---|---|
| author | Yuya Arai Ko Takahashi Takaaki Horinouchi Koichi Takahashi Haruka Ozaki |
| author_facet | Yuya Arai Ko Takahashi Takaaki Horinouchi Koichi Takahashi Haruka Ozaki |
| author_sort | Yuya Arai |
| collection | DOAJ |
| description | During laboratory automation of life science experiments, coordinating specialized instruments and human experimenters for various experimental procedures is important to minimize the execution time. In particular, the scheduling of life science experiments requires the consideration of time constraints by mutual boundaries (TCMB) and can be formulated as the “scheduling for laboratory automation in biology” (S-LAB) problem. However, existing scheduling methods for the S-LAB problems have difficulties in obtaining a feasible solution for large-size scheduling problems at a time sufficient for real-time use. In this study, we proposed a fast schedule-finding method for S-LAB problems, SAGAS (Simulated annealing and greedy algorithm scheduler). SAGAS combines simulated annealing and the greedy algorithm to find a scheduling solution with the shortest possible execution time. We have performed scheduling on real experimental protocols and shown that SAGAS can search for feasible or optimal solutions in practicable computation time for various S-LAB problems. Furthermore, the reduced computation time by SAGAS enables us to systematically search for laboratory automation with minimum execution time by simulating scheduling for various laboratory configurations. This study provides a convenient scheduling method for life science automation laboratories and presents a new possibility for designing laboratory configurations. |
| first_indexed | 2024-03-12T16:15:18Z |
| format | Article |
| id | doaj.art-313a41062dcf48bebf841dc2ad2c95a7 |
| institution | Directory Open Access Journal |
| issn | 2472-6303 |
| language | English |
| last_indexed | 2024-03-12T16:15:18Z |
| publishDate | 2023-08-01 |
| publisher | Elsevier |
| record_format | Article |
| series | SLAS Technology |
| spelling | doaj.art-313a41062dcf48bebf841dc2ad2c95a72023-08-09T04:33:30ZengElsevierSLAS Technology2472-63032023-08-01284264277SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automationYuya Arai0Ko Takahashi1Takaaki Horinouchi2Koichi Takahashi3Haruka Ozaki4College of Biological Sciences, School of Life and Environmental Sciences, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki, 305-8575, Japan; Bioinformatics Laboratory, Faculty of Medicine, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki, 305-8575, JapanCollege of Biological Sciences, School of Life and Environmental Sciences, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki, 305-8575, JapanArtificial Intelligence Research Center, National Institute of Advanced Industrial Science and Technology, 2-4-7 Aomi, Koto-ku, Tokyo, 135-0064, Japan; Laboratory for Biologically Inspired Computing, RIKEN Center for Biosystems Dynamics Research, 6-2-3 Furuedai, Suita, Osaka, 565-0874, JapanLaboratory for Biologically Inspired Computing, RIKEN Center for Biosystems Dynamics Research, 6-2-3 Furuedai, Suita, Osaka, 565-0874, Japan; Graduate School of Media and Governance, Keio University, 5322 Endo, Fujisawa, Kanagawa, 252-0816, JapanCorresponding author.; Bioinformatics Laboratory, Faculty of Medicine, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki, 305-8575, Japan; Center for Artificial Intelligence Research, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki, 305-8577, JapanDuring laboratory automation of life science experiments, coordinating specialized instruments and human experimenters for various experimental procedures is important to minimize the execution time. In particular, the scheduling of life science experiments requires the consideration of time constraints by mutual boundaries (TCMB) and can be formulated as the “scheduling for laboratory automation in biology” (S-LAB) problem. However, existing scheduling methods for the S-LAB problems have difficulties in obtaining a feasible solution for large-size scheduling problems at a time sufficient for real-time use. In this study, we proposed a fast schedule-finding method for S-LAB problems, SAGAS (Simulated annealing and greedy algorithm scheduler). SAGAS combines simulated annealing and the greedy algorithm to find a scheduling solution with the shortest possible execution time. We have performed scheduling on real experimental protocols and shown that SAGAS can search for feasible or optimal solutions in practicable computation time for various S-LAB problems. Furthermore, the reduced computation time by SAGAS enables us to systematically search for laboratory automation with minimum execution time by simulating scheduling for various laboratory configurations. This study provides a convenient scheduling method for life science automation laboratories and presents a new possibility for designing laboratory configurations.http://www.sciencedirect.com/science/article/pii/S2472630323000195SchedulingLaboratory automationTime constraint by mutual boundaries (TCMB)Scheduling for laboratory automation in biology (S-LAB) problemSimulated annealing (SA)Greedy algorithm |
| spellingShingle | Yuya Arai Ko Takahashi Takaaki Horinouchi Koichi Takahashi Haruka Ozaki SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automation SLAS Technology Scheduling Laboratory automation Time constraint by mutual boundaries (TCMB) Scheduling for laboratory automation in biology (S-LAB) problem Simulated annealing (SA) Greedy algorithm |
| title | SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automation |
| title_full | SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automation |
| title_fullStr | SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automation |
| title_full_unstemmed | SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automation |
| title_short | SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automation |
| title_sort | sagas simulated annealing and greedy algorithm scheduler for laboratory automation |
| topic | Scheduling Laboratory automation Time constraint by mutual boundaries (TCMB) Scheduling for laboratory automation in biology (S-LAB) problem Simulated annealing (SA) Greedy algorithm |
| url | http://www.sciencedirect.com/science/article/pii/S2472630323000195 |
| work_keys_str_mv | AT yuyaarai sagassimulatedannealingandgreedyalgorithmschedulerforlaboratoryautomation AT kotakahashi sagassimulatedannealingandgreedyalgorithmschedulerforlaboratoryautomation AT takaakihorinouchi sagassimulatedannealingandgreedyalgorithmschedulerforlaboratoryautomation AT koichitakahashi sagassimulatedannealingandgreedyalgorithmschedulerforlaboratoryautomation AT harukaozaki sagassimulatedannealingandgreedyalgorithmschedulerforlaboratoryautomation |