Advertisement
Full Length Article|Articles in Press

SAGAS: Simulated annealing and greedy algorithm scheduler for laboratory automation

  • Yuya Arai
    Affiliations
    College 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, Japan
    Search for articles by this author
  • Ko Takahashi
    Affiliations
    College of Biological Sciences, School of Life and Environmental Sciences, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki, 305-8575, Japan
    Search for articles by this author
  • Takaaki Horinouchi
    Affiliations
    Artificial 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, Japan
    Search for articles by this author
  • Koichi Takahashi
    Affiliations
    Laboratory 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, Japan
    Search for articles by this author
  • Haruka Ozaki
    Correspondence
    Corresponding author.
    Affiliations
    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, Japan
    Search for articles by this author
Open AccessPublished:March 28, 2023DOI:https://doi.org/10.1016/j.slast.2023.03.001

      Abstract

      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.

      Keywords

      1. Introduction

      When complex experimental procedures and large numbers of experiments are required, automation of experimental operations is important to assure quality, reduce costs, and increase efficiency. Various specialized instruments have been developed for large-scale genome editing [
      • Wang Y.
      • Liu Y.
      • Liu J.
      • Guo Y.
      • Fan L.
      • Ni X.
      • Zheng X.
      • Wang M.
      • Zheng P.
      • Sun J.
      • Ma Y.
      MACBETH: multiplex automated corynebacterium glutamicum base editing method.
      ], library preparation for massively parallel sequencing [
      • Hess J.F.
      • Kohl T.A.
      • Kotrová M.
      • Rönsch K.
      • Paprotka T.
      • Mohr V.
      • Hutzenlaub T.
      • Brüggemann M.
      • Zengerle R.
      • Niemann S.
      • Paust N.
      Library preparation for next generation sequencing: a review of automation strategies.
      ], cell culture [
      • Matsumoto E.
      • Koide N.
      • Hanzawa H.
      • Kiyama M.
      • Ohta M.
      • Kuwabara J.
      • Takeda S.
      • Takahashi M.
      Fabricating retinal pigment epithelial cell sheets derived from human induced pluripotent stem cells in an automated closed culture system for regenerative medicine.
      ,
      • Nishimura A.
      • Nakajima R.
      • Takagi R.
      • Zhou G.
      • Suzuki D.
      • Kiyama M.
      • Nozaki T.
      • Owaki T.
      • Takahara T.
      • Nagai S.
      • Nakamura T.
      • Sugaya M.
      • Terada K.
      • Igarashi Y.
      • Hanzawa H.
      • Okano T.
      • Shimizu T.
      • Yamato M.
      • Takeda S.
      Fabrication of tissue-engineered cell sheets by automated cell culture equipment.
      ], omics measurements [
      • Jiang X.
      • Feng S.
      • Tian R.
      • Han G.
      • Jiang X.
      • Ye M.
      • Zou H.
      Automation of nanoflow liquid chromatography-tandem mass spectrometry for proteome analysis by using a strong cation exchange trap column.
      ,
      • Lopez M.F.
      • Kristal B.S.
      • Chernokalskaya E.
      • Lazarev A.
      • Shestopalov A.I.
      • Bogdanova A.
      • Robinson M.
      High-throughput profiling of the mitochondrial proteome using affinity fractionation and automation.
      ], and high-throughput assays [
      • Burns C.G.
      • Milan D.J.
      • Grande E.J.
      • Rottbauer W.
      • MacRae C.A.
      • Fishman M.C.
      High-throughput assay for small molecules that modulate zebrafish embryonic heart rate.
      ,
      • Huang D.
      • Ou B.
      • Hampsch-Woodill M.
      • Flanagan J.A.
      • Prior R.L.
      High-throughput assay of oxygen radical absorbance capacity (ORAC) using a multichannel liquid handling system coupled with a microplate fluorescence reader in 96-well format.
      ,
      • Supply P.
      • Lesjean S.
      • Savine E.
      • Kremer K.
      • van Soolingen D.
      • Locht C.
      Automated high-throughput genotyping for study of global epidemiology of mycobacterium tuberculosis based on Mycobacterial interspersed repetitive units.
      ,
      • Yoshimoto N.
      • Kida A.
      • Jie X.
      • Kurokawa M.
      • Iijima M.
      • Niimi T.
      • Maturana A.D.
      • Nikaido I.
      • Ueda H.R.
      • Tatematsu K.
      • Tanizawa K.
      • Kondo A.
      • Fujii I.
      • Kuroda S.
      An automated system for high-throughput single cell-based breeding.
      ] to meet the demands for current life sciences. Although versatile instruments such as liquid handling workstations and dual-arm humanoid robots have been developed [
      • Kanda G.N.
      • Tsuzuki T.
      • Terada M.
      • Sakai N.
      • Motozawa N.
      • Masuda T.
      • Nishida M.
      • Watanabe C.T.
      • Higashi T.
      • Horiguchi S.A.
      • Kudo T.
      • Kamei M.
      • Sunagawa G.A.
      • Matsukuma K.
      • Sakurada T.
      • Ozawa Y.
      • Takahashi M.
      • Takahashi K.
      • Natsume T.
      Robotic search for optimal cell culture in regenerative medicine.
      ,
      • Konagaya S.
      • Ando T.
      • Yamauchi T.
      • Suemori H.
      • Iwata H.
      Long-term maintenance of human induced pluripotent stem cells by automated cell culture system.
      ,
      • Ochiai K.
      • Motozawa N.
      • Terada M.
      • Horinouchi T.
      • Masuda T.
      • Kudo T.
      • et al.
      A variable scheduling maintenance culture platform for mammalian cells.
      ,
      • Yachie N.
      • Takahashi K.
      • Katayama T.
      • Sakurada T.
      • Kanda G.N.
      • Takagi E.
      • Hirose T.
      • Katsura T.
      • Moriya T.
      • Kitano H.
      • Tsujii J.
      • Shiraki T.
      • Kariyazaki H.
      • Kamei M.
      • Abe N.
      • Fukuda T.
      • Sawada Y.
      • Hashiguchi Y.
      • Matsukuma K.
      • Murai S.
      • Sasaki N.
      • Ipposhi T.
      • Urabe H.
      • Kudo T.
      • Umeno M.
      • Ono S.
      • Miyauchi K.
      • Nakamura M.
      • Kizaki T.
      • Suyama T.
      • Hatta T.
      • Natsume T.
      • Ohta T.
      • Ozawa Y.
      • Ihara S.
      • Tamaki S.
      • Antezana E.
      • Garcia-Castro A.
      • Perret J.-L.
      • Ishiguro S.
      • Mori H.
      • Evans-Yamamoto D.
      • Masuyama N.
      • Tomita M.
      • Katayama T.
      • Matsumoto M.
      • Nakayama H.
      • Shirasawa A.
      • Shimbo K.
      • Yamada N.
      • Nakayama K.I.
      • Shimizu T.
      • Saya H.
      • Yamashita S.
      • Matsushima T.
      • Asahara H.
      • Eguchi H.
      • Mikamori M.
      • Mori M.
      • Natsume T.
      Robotic crowd biology with Maholo LabDroids.
      ], a single instrument can rarely perform all the steps of an experimental procedure. As a result, it is usually necessary to use several different instruments to complete one experimental procedure [
      • Lehmann R.
      • Severitt J.C.
      • Roddelkopf T.
      • Junginger S.
      • Thurow K.
      Biomek cell workstation: a variable system for automated cell cultivation.
      ,
      • Vorberg E.
      • Fleischer H.
      • Junginger S.
      • Liu H.
      • Stoll N.
      • Thurow K.
      A highly flexible, automated system providing reliable sample preparation in element- and Structure-Specific measurements.
      ].
      In an automated laboratory consisting of multiple different types of instruments, a scheduling method allocates each operation to an instrument to process a large number of operations efficiently [
      • Schäfer R.
      Concepts for dynamic scheduling in the laboratory.
      ]. For instance, when multiple experimental procedures are performed in parallel, the execution time depends on the order and allocation of experimental procedures to the individual instruments. Various scheduling methods for laboratory automaton have been developed based on dedicated rule-based algorithms [
      • Shin S.H.
      • Choi B.J.
      • Ryew S.M.
      • Kim J.W.
      • Kim D.S.
      • Chung W.K.
      • et al.
      Development of an improved scheduling algorithm for lab test operations on a Small-Size bio robot platform.
      ,
      • Delaney N.F.
      • Rojas Echenique J.I.
      • Marx C.J.
      Clarity: an open-source manager for laboratory automation.
      ,
      • Burger B.
      • Maffettone P.M.
      • Gusev V.V.
      • Aitchison C.M.
      • Bai Y.
      • Wang X.
      • Li X.
      • Alston B.M.
      • Li B.
      • Clowes R.
      • Rankin N.
      • Harris B.
      • Sprick R.S.
      • Cooper A.I.
      A mobile robotic chemist.
      ] and mathematical optimization algorithms [
      • Cabrera C.
      • Fine-Morris M.
      • Pokross M.
      • Kish K.
      • Michalczyk S.
      • Cahn M.
      • Klei H.
      • Russo M.F.
      Dynamically optimizing experiment schedules of a laboratory robot system with simulated annealing.
      ,
      • Gu X.
      • Neubert S.
      • Stoll N.
      • Thurow K.
      Intelligent scheduling method for life science automation systems.
      ,
      • Neubert S.
      • Gu X.
      • Göde B.
      • Roddelkopf T.
      • Fleischer H.
      • Stoll N.
      • Thurow K.
      Workflow management system for the integration of mobile robots in future labs of life sciences.
      ,
      • Itoh T.D.
      • Horinouchi T.
      • Uchida H.
      • Takahashi K.
      • Ozaki H.
      Optimal scheduling for laboratory automation of life science experiments with time constraints.
      ]. Rule-based algorithms are simple for users to interpret and are tailored to specific scheduling problems [
      • Shin S.H.
      • Choi B.J.
      • Ryew S.M.
      • Kim J.W.
      • Kim D.S.
      • Chung W.K.
      • et al.
      Development of an improved scheduling algorithm for lab test operations on a Small-Size bio robot platform.
      ,
      • Delaney N.F.
      • Rojas Echenique J.I.
      • Marx C.J.
      Clarity: an open-source manager for laboratory automation.
      ,
      • Burger B.
      • Maffettone P.M.
      • Gusev V.V.
      • Aitchison C.M.
      • Bai Y.
      • Wang X.
      • Li X.
      • Alston B.M.
      • Li B.
      • Clowes R.
      • Rankin N.
      • Harris B.
      • Sprick R.S.
      • Cooper A.I.
      A mobile robotic chemist.
      ]. For instance, Delaney et al. created a dynamic scheduling program that selects the unfinished operation with the earliest prescribed time as the next operation to be executed [
      • Delaney N.F.
      • Rojas Echenique J.I.
      • Marx C.J.
      Clarity: an open-source manager for laboratory automation.
      ]. Similarly, Burger et al. performed scheduling so that the robot simultaneously begins the oldest queued work on instruments [
      • Burger B.
      • Maffettone P.M.
      • Gusev V.V.
      • Aitchison C.M.
      • Bai Y.
      • Wang X.
      • Li X.
      • Alston B.M.
      • Li B.
      • Clowes R.
      • Rankin N.
      • Harris B.
      • Sprick R.S.
      • Cooper A.I.
      A mobile robotic chemist.
      ]. On the other hand, mathematical optimization algorithms search for an ideal schedule that minimizes the whole execution time. Specifically, scheduling problems in laboratory automation have been successfully solved using metaheuristic algorithms, a class of stochastic search algorithms that balance intensification and diversification strategies, including simulated annealing [
      • Cabrera C.
      • Fine-Morris M.
      • Pokross M.
      • Kish K.
      • Michalczyk S.
      • Cahn M.
      • Klei H.
      • Russo M.F.
      Dynamically optimizing experiment schedules of a laboratory robot system with simulated annealing.
      ] and genetic algorithms [
      • Gu X.
      • Neubert S.
      • Stoll N.
      • Thurow K.
      Intelligent scheduling method for life science automation systems.
      ,
      • Neubert S.
      • Gu X.
      • Göde B.
      • Roddelkopf T.
      • Fleischer H.
      • Stoll N.
      • Thurow K.
      Workflow management system for the integration of mobile robots in future labs of life sciences.
      ].
      Furthermore, as experimental procedures in life sciences often deal with live cells and unstable biomolecules (RNA and enzymes), scheduling needs to consider time constraints by mutual boundaries (TCMB) to prevent cell damage, denaturation, or degradation of molecules. A TCMB is the upper limit of the time difference between an operation’s start or end (boundary) and the boundary of another [
      • Schäfer R.
      Concepts for dynamic scheduling in the laboratory.
      ]. TCMBs exist in many life science experimental protocols in various fields including metabolomics [
      • Canelas A.B.
      • ten Pierick A.
      • Ras C.
      • Seifar R.M.
      • van Dam J.C.
      • van Gulik W.M.
      • Heijnen J.J.
      Quantitative evaluation of intracellular metabolite extraction techniques for yeast metabolomics.
      ], RNA sequnencing [
      • Gallego Romero I.
      • Pai A.A.
      • Tung J.
      • Gilad Y.
      RNA-seq: impact of RNA degradation on transcript quantification.
      ], and cell culture [
      • Michl J.
      • Park K.C.
      • Swietach P.
      Evidence-based guidelines for controlling pH in mammalian live-cell culture systems.
      ]. Despite the importance of considering TCMBs, most of the previous scheduling algorithms for laboratory automation have not focused on TCMBs among operations [
      • Shin S.H.
      • Choi B.J.
      • Ryew S.M.
      • Kim J.W.
      • Kim D.S.
      • Chung W.K.
      • et al.
      Development of an improved scheduling algorithm for lab test operations on a Small-Size bio robot platform.
      ,
      • Delaney N.F.
      • Rojas Echenique J.I.
      • Marx C.J.
      Clarity: an open-source manager for laboratory automation.
      ,
      • Burger B.
      • Maffettone P.M.
      • Gusev V.V.
      • Aitchison C.M.
      • Bai Y.
      • Wang X.
      • Li X.
      • Alston B.M.
      • Li B.
      • Clowes R.
      • Rankin N.
      • Harris B.
      • Sprick R.S.
      • Cooper A.I.
      A mobile robotic chemist.
      ,
      • Cabrera C.
      • Fine-Morris M.
      • Pokross M.
      • Kish K.
      • Michalczyk S.
      • Cahn M.
      • Klei H.
      • Russo M.F.
      Dynamically optimizing experiment schedules of a laboratory robot system with simulated annealing.
      ,
      • Gu X.
      • Neubert S.
      • Stoll N.
      • Thurow K.
      Intelligent scheduling method for life science automation systems.
      ,
      • Neubert S.
      • Gu X.
      • Göde B.
      • Roddelkopf T.
      • Fleischer H.
      • Stoll N.
      • Thurow K.
      Workflow management system for the integration of mobile robots in future labs of life sciences.
      ]. Recently, Itoh et al. proposed formulating the “scheduling for laboratory automation in biology” (S-LAB) problem, a scheduling problem in automated laboratories considering the TCMB, as a mixed integer programming problem [
      • Itoh T.D.
      • Horinouchi T.
      • Uchida H.
      • Takahashi K.
      • Ozaki H.
      Optimal scheduling for laboratory automation of life science experiments with time constraints.
      ]. They also developed the software SLab.jl, which can obtain a schedule as an optimal solution for the S-LAB problem using the branch-and-bound method, an exact algorithm for mixed integer programming problems. However, the branch-and-bound method used in SLab.jl can hardly find a feasible solution (a schedule that satisfies the constraints) for scheduling problems with many jobs, steps, or instruments in a practicable time (e.g., for ordinary job-shop scheduling problems [
      • Brucker P.
      • Jurisch B.
      • Sievers B.
      A branch and bound algorithm for the job-shop scheduling problem.
      ]): Indeed, as we will see later, SLab.jl failed to find feasible solutions within the runtime thresholds for some S-LAB problems. This issue should be addressed in actually handling an automated laboratory.
      A faster scheduling method for S-LAB problems would be able to schedule various sets of experimental protocols with TCMBs. Reducing computation times also enables enhancements such as designing more efficient simulation-based laboratory configurations [
      • Itoh T.D.
      • Horinouchi T.
      • Uchida H.
      • Takahashi K.
      • Ozaki H.
      Optimal scheduling for laboratory automation of life science experiments with time constraints.
      ]. Approximation algorithms are one solution to scheduling problems, such as the S-LAB problem, which is difficult to solve with an exact algorithm using mathematical optimization. Metaheuristic algorithms such as simulated-annealing algorithms and genetic algorithms [
      • Oliva D.
      • Abd Elaziz M.
      • Hinojosa S.
      Metaheuristic optimization.
      ] have been used to search for a schedule that minimizes the execution time in scheduling problems that do not consider the TCMB in automated laboratories [
      • Cabrera C.
      • Fine-Morris M.
      • Pokross M.
      • Kish K.
      • Michalczyk S.
      • Cahn M.
      • Klei H.
      • Russo M.F.
      Dynamically optimizing experiment schedules of a laboratory robot system with simulated annealing.
      ,
      • Gu X.
      • Neubert S.
      • Stoll N.
      • Thurow K.
      Intelligent scheduling method for life science automation systems.
      ,
      • Thurow K.
      • Gu X.
      • Göde B.
      • Roddelkopf T.
      • Fleischer H.
      • Stoll N.
      • Neubert S.
      Integrating mobile robots into automated laboratory processes: a suitable workflow management system.
      ]. However, metaheuristic algorithms alone may not be able to find good schedules getting stuck in local optima. To overcome the problem, hybrid methods of metaheuristic and greedy algorithms have been proposed for ordinary job shop scheduling problems [
      • Naderi B.
      • Azab A.
      An improved model and novel simulated annealing for distributed job shop problems.
      ] as well as other optimization problems [
      • Lee S.
      • Kim S.B.
      Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning.
      ,
      • Yuan Y.
      • Tole K.
      • Ni F.
      • He K.
      • Xiong Z.
      • Liu J.
      Adaptive simulated annealing with greedy search for the circle bin packing problem.
      ], but the effectiveness of these methods for S-LAB problems is still unknown.
      This study aimed to verify whether approximation algorithms and hybrid methods can find feasible solutions to S-LAB problems at a time sufficient for real-time use. We proposed a new method, SAGAS (Simulated annealing and greedy algorithm scheduler), which is a fast schedule discovery method for the S-LAB problem. SAGAS uses both simulated annealing and the greedy algorithm to search for a schedule with the minimum execution time possible. We showed that SAGAS can find feasible or optimal solutions in practicable computation time for various S-LAB problems involving several jobs of different complexity based on real experimental protocols. Furthermore, we demonstrate that, by performing scheduling simulations for various laboratory configurations, SAGAS’s computation speed enables us to search for laboratory configurations that reduce the execution time.

      2. Materials and methods

      2.1 S-LAB problem

      An S-LAB problem, defined by Itoh et al. [
      • Itoh T.D.
      • Horinouchi T.
      • Uchida H.
      • Takahashi K.
      • Ozaki H.
      Optimal scheduling for laboratory automation of life science experiments with time constraints.
      ], is a scheduling problem for an automated laboratory, which consists of several types of instruments (laboratory configuration) and jobs that process multiple operations in a certain order (job definitions) (Mathematical formulation of S-LAB problems as mixed integer problems is provided in Supplemental Material Section 2 of [
      • Itoh T.D.
      • Horinouchi T.
      • Uchida H.
      • Takahashi K.
      • Ozaki H.
      Optimal scheduling for laboratory automation of life science experiments with time constraints.
      ]). Each operation has a processing time (τ), the instrument that processes it, and dependencies with other operations (Fig. 1A is an example). The TCMB is also set as the upper limit of the time difference between the start or end of one operation and the start or end of another (boundary). A solution (schedule) for an S-LAB problem is the start time of each operation and the allocation of processing instruments. The solution must satisfy the following constraints: (1) one instrument can process at most one operation at a time, (2) the order of operations follows the dependency of the operations, and (3) the time between operations follows the TCMBs. The objective function is the latest end time of all operations. Below we will explain the details of S-LAB problems.
      Fig. 1
      Fig. 1(A) A diagram of SAGAS’s important components and their organization. (B) A visual explanation of TempL computation.

      2.1.1 Laboratory configuration (L)

      • There are M instruments in a laboratory, each of which has an instrument type Tm(1mM,1TmK), where K is the number of different instrument types.
      • Each instrument has parking positions through which an instrument passes samples to transporters or receives them from transporters. Here, we assume that each instrument has a sufficient number of parking positions so that samples can wait if the instrument is being used by another operation.

      2.1.2 Job definition (J)

      J is consists of jobs, operations, and constraints.
      Jobs:
      • There are J jobs. The jth (1jJ) job is composed of Nj operations. In total, there are N=j=1JNj operations.
      Operations:
      • The a-th (1aN) operation Oa has a compatible instrument type Ca (1CaK); that is, the a-th operation needs to be processed by an instrument m with the instrument type Tm=Ca.
      • The a-th operation has process time τa, which is intrinsically determined by the combination of the nature of the operation and the instrument type Ca to process it.
      • There can be a dependency between one operation Oa and another Ob (a<b) in the same job; that is, Ob must start after Oa ends. The operation dependency graph G is a directed acyclic graph wherein each node represents an operation and each directed edge represents the dependency between a pair of operations.
        Ga,b={1,ifObmuststartafterOaends0,otherwise


        Note that such G can be obtained easily by topological sort of operation indices [
        • Cormen T.
        • Leisercon C.
        • Rivest R.
        • Stein C.
        Introduction to algorithms.
        ]. We also define ListG as the adjacency list of the transpose graph of G: ListG[b]={a,...} (a<b). For example, if ListG[5]={1,2,4}, then O5 must start after O1, O2 and O4 end.
      • Let ListTCMB[b] be the list of TCMBs between Oa (a<b) and Ob. A TCMB sets the upper limit α of the maximum tolerable difference between the start or end time of each of a pair of operations Oa and Ob [
        • Itoh T.D.
        • Horinouchi T.
        • Uchida H.
        • Takahashi K.
        • Ozaki H.
        Optimal scheduling for laboratory automation of life science experiments with time constraints.
        ,
        • Gu X.
        • Neubert S.
        • Stoll N.
        • Thurow K.
        Intelligent scheduling method for life science automation systems.
        ]. Each TCMB is represented as a 4-tuple (From,a,To,α). α can vary among different TCMBs. From and To indicate either “Start” or “End” of an operation. There are four pairs of From and To:
        • 1.
          Start - Start: The absolute difference between the start time of operation b and the start time of operation a must be less than or equal to α.
        • 2.
          End - Start: The absolute difference between the end time of operation b and the start time of operation a must be less than or equal to α.
        • 3.
          Start - End: The absolute difference between the start time of operation b and the end time of operation a must be less than or equal to α.
        • 4.
          End - End: The absolute difference between the end time of operation b and the end time of operation a must be less than or equal to α.
        For example, “ListTCMB[2]={Start,1,End,5}” means that O2 must start within 5 min before and after O1 ends.
      Constraints:
      • Constraint 1: When multiple instruments are allocated to multiple operations, one instrument can process at most one operation at a time.
      • Constraint 2: The order of operations defined by G needs to be maintained.
      • Constraint 3: The start and end time of all operations must satisfy TCMB.
      • Constraint 4: There must be a buffer time between a pair of operations consecutively processed on the same instrument. The length of the buffer time β (β>0) is determined by the user.

      2.1.3 Scheduling solutions

      • The start time for all operations is designated as S={Sa}(1aN).
      • An instrument allocation is E={Ea}(1aN,1EaM), where Ea is the instrument that processes Oa, chosen from the set of compatible instruments whose instrument type TEa=Ca. E is computed based on the laboratory configuration L, job definition J, the buffer time β, process time τ and the start time Sa. See Algorithm 5.
      • A schedule is defined by determining the start time Sa and the processor Ea for each Oa.
      • A scheduling solution that meets all the constraints is designated as a feasible solution. A feasible solution with the smallest objective function value (see 2.1.4) is designated as an optimal solution. A schedule that does not meet all the constraints is designated as an failed solution.

      2.1.4 Objective

      The objective of an S-LAB problem is to find the optimal schedule {S,E} that minimizes the entire execution time of the jobs, that is, the end time of the lastly processed operation.
      f(S)=maxa(Sa+τa)


      2.1.5 Mathematical formulation

      We need two additional terms Fa(m) and Qa,b(m) to describe all constraints:
      Fa(m)={1,ifEa=m,0,otherwisea,m.


      Qa,b(m)={1,ifEa=Eb=m,Sa<Sb0,otherwisea,b,m.


      Fa(m) is the Boolean equivalent of the m-th instrument which process Oa. Qa,b(m) is the Boolean equivalent of the m-th instrument which process Oa and Ob. If Oa and Ob are processed with the m-th instrument, Qa,b(m)=1. Using these terms, all constraints is rewritten as follows:
      • Constraints 1 and 4
        m=1MFa(m)=1a.


        Sa+τa+βSbifQa,b(m)=1a,b,m


      • Constraint 2
        Sa+τaSbifGa,b=1a,b


      • Constraint 3 (TCMB)
        For each TCMB(From,a,To,α) of ListTCMB[b] (see 2.1.2)
        • 1.
          |SaSb|α
        • 2.
          |Sa(Sb+τb)|α
        • 3.
          |(Sa+τa)(Sb)|α
        • 4.
          |(Sa+τa)(Sb+τb)|α

      2.2 SAGAS algorithm

      2.2.1 Overview of SAGAS algorithm

      We propose the SAGAS algorithm for solving the S-LAB problem. This algorithm combines simulated annealing and a greedy algorithm to search for a solution (schedule) that reduces the objective function. SAGAS is divided into three main steps (Fig. 1A). First, an initial solution is created based on the simulated annealing step (SA). The solution is then modified to create an improved solution in the final modification step (Mod). Further, the improved solution is compared with the solution obtained by the greedy algorithm step (Greedy), and the better one is the output (SAGAS). Finally, instrument allocation is performed.

      2.2.2 Simulated annealing step (SA)

      Simulated annealing is a meta-heuristic algorithm widely used for solving global and combinatorial optimization problems [
      • Oliva D.
      • Abd Elaziz M.
      • Hinojosa S.
      Metaheuristic optimization.
      ,
      • Kirkpatrick S.
      • Gelatt Jr C.D.
      • Vecchi M.P.
      Optimization by simulated annealing.
      ]. The simulated annealing step (SA) in SAGAS searches for a schedule that minimizes the modified version of the objective function fSA(S) (described below) by simulated annealing. SA uses a control parameter called temperature (min), which is gradually reduced from a higher temperature to a lower temperature. Starting with the generation of an initial solution (schedule), the next solution Snext is generated from the current solution Scurrent at each temperature and accepted or rejected based on temperature-dependent transition probabilities p(Scurrent,Snext) (described below). Finally, SA outputs SSA, the start time for all operations with the shortest execution time ever found during the simulated annealing calculation, and ScoreSA, the corresponding objective function value. Note that SSA is not guaranteed to meet all the constraints; it can be either a feasible or failed solution.
      The initial solution (Sinitial) is defined by the following steps: Jobs are scheduled in the order they are given. For the j-th job, all operations are scheduled in the order they are given. First, the start time of the first operation is set to the finish time of the previous job. Second, the start time of the remaining operations is set to the finish time of the previous operation.
      During the search of schedules, SA sometimes generates a candidate schedule that violates Constraints 1, 2, 3, or 4. To avoid the violations, penalties are imposed for such schedules, and the objective function value fSA(S) is modified as follows: Let TimepM be the sum of time when Constraint 1 is violated: Total time that each operation is unable to use the compatible instruments. Let TimepD be the sum of time when Constraint 2 is violated: a,b{a,bGa,b=1}max(0,Sa+τaSb). Let TimepT be the sum of time when Constraint 3 is violated. Then, with an arbitrary penalty weight wp (min) (>TempL, 108,000 in this study), fSA(S) is defined as follows:
      Timep=TimepD+TimepT+TimepMfSA(S)=f(S)+Timep×wp
      (1)


      A control parameter temperature Temp is defined to decrease linearly from the initial temperature TempS to the end temperature TempL. TempS is defined as the start time of the last operation in the initial solution. TempL is defined as the following equation, where STi is the sum of the processing time (τ + β) of all the operations using instruments type i and NMi is the number of instruments of Type i (Fig. 1B).
      TempL=max1iK(STiNMi)
      (2)


      When Temp becomes TempL or smaller, the calculation of SA stops and outputs SSA. To obtain a feasible solution at a time sufficient for real-world use, we introduced the user-provided runtime threshold of SA (SA_msec), in which the time Temp decreases to TempL. Strictly, using elapsed time (Elapsed_time) of SA and SA_msec, Temp is calculated as the following equation:
      Temp=TempS(TempSTempL)×Elapsed_timeSA_msec
      (3)


      The temperature-dependent transition probability p(Scurrent,Snext) is defined as follows:
      tremaining=TempTempL
      (4)


      Δscore=fSA(Scurrent)fSA(Snext)Probe=exp(Δscore/tremaining)p(Scurrent,Snext)=min(Probe,1)
      (5)


      Let Floora and Ceila be the earliest and latest time that satisfies the last entered constraint (dependency or TCMB) to the a-th operation, respectively. At each temperature, the start time of each operation a in the next solution Snext is determined based on the value sampled from a uniform distribution U(Floora,Ceila).
      The pseudo-code for SA is shown in Algorithm 1.
      Algorithm 1
      Algorithm 1Simulated annealing (SA).

      2.2.3 Final modification step (Mod)

      In the final modification step, adjustments are made to SSA, the scheduling solution obtained in SA, to shorten the execution time. When SSA is a feasible solution, the final modification step also outputs a feasible solution. When SSA is a failed solution, the final modification step outputs either a feasible or failed solution. The final modification is composed of the following three steps:
      • 1.
        First step
        • a.
          At the first step, it sets a criterion time tcriteria as 1.
        • b.
          After that, it decreases the start time of all operations, which is started after tcriteria by 1 and updates the schedule if the score improves.
        • c.
          After then, it increases tcriteria by 1.
        • d.
          If tcriteria is equal to the start time of the lastly processed operation, it sets a criterion time tcriteria as 1 again.
        • e.
          It repeats (b) and (d) until the score finishes improving.
      • 2.
        Second step
        • a.
          At the second step, it sets criterion time tcriteria as 1.
        • b.
          After that, it decreases the start time of all the operations of the j-th (1jJ) job, which is started after tcriteria by 1, and updates the schedule if the score improves.
        • c.
          After then, it increases tcriteria by 1 after checking the all jobs.
        • d.
          if tcriteria is equal to the start time of the lastly processed operation, it sets a criterion time tcriteria as 1 again.
        • e.
          It repeats (b) and (d) until the score finishes improving.
      • 3.
        Third step
        • a.
          At the third step, it updates the schedule if the score improves every time it decreases the start time of each operation by 1.
        • b.
          It repeats (a) until the score finishes improving.
      See Algorithm 2.
      Algorithm 2
      Algorithm 2Final modification (Mod).

      2.2.4 Greedy algorithm step (Greedy)

      A greedy algorithm is a heuristic algorithm [
      • Cormen T.H.
      • Leiserson C.E.
      • Rivest R.L.
      • Stein C.
      Introduction to algorithms.
      ]. The Greedy algorithm step (Greedy) attempts to assign the minimum possible start time to each operation in the input order (from 1 to N). Specifically, the following algorithm is applied to each operation Ob in each job in order:
      • 1.
        Let R and R+ be the minimum and maximum values for S[b], respectively, that satisfy Constraint 2 and 3. R and R+ are calculated by Algorithm 4.
      • 2.
        Starting from R to R+, Greedy assigns a tentative value to S[b] and test whether the value of S[b] meets all the constraints. When the value of S[b] meets all the constraints, do Step 1 for the next operation Ob+1.
      • 3.
        If any value of S[b] does not meet all of the constraints, Greedy tries shifting the start time of (Ov), the operation specifying R+, by 1.
      • 4.
        Then, if the value of S[v] exceeds wp defined in SA, the calculation exits with no solution; otherwise, do the Step 1 for Ov.
      From the above calculations, the Greedy step deterministically outputs the same solution to the same inputs because the algorithm does not involve stochastic samplings. See Algorithm 3.
      Algorithm 3
      Algorithm 3Greedy algorithm (Greedy).
      Algorithm 5
      Algorithm 5Instrument allocation.

      2.2.5 Instrument allocation

      After generating a solution, SAGAS allocates the laboratory instrument to the operations. For the a-th operation, it allocates an instrument which is available from S[a] to S[a]+τ[a]+β. See Algorithm 5. Note that, some instruments may not be allocated in the instrument allocation step.

      2.3 Implementation and code availability

      Language(s) used: C++17 (g++ (Homebrew GCC 11.2.0_3) 11.2.0)
      The code for running SAGAS in a local environment or on Google Colaboratory and the codes for data processing and visualization are available from the GitHub repository (https://github.com/bioinfo-tsukuba/SAGAS).

      2.4 Performance evaluation

      We performed simulated experiments based on the S-LAB problems described in Section 2.5 and evaluated the scheduling performance of SAGAS by two indices: (1) the execution time, which is the difference between the start time of the earliest scheduled operation and the end time of the latest scheduled operation, and (2) the computation time. In this study, the unit time of scheduling was min.
      The scheduling performance of SAGAS was compared with the following three algorithms: (1) SA, (2) SA followed by final modification (SA-Mod), a half part of the main algorithm of SAGAS, which is SAGAS without the comparison to greedy searching, (3) the greedy algorithm (Greedy), the other half part of the SAGAS. To evaluate the importance of each component on the performance, we implemented SA, SA-Mod, Greedy, and SAGAS as four different software (Fig. 1A).
      In this study, β was set as 1 min, respectively, for all the S-LAB problems described below. For SAGAS, SA, SA-Mod, SA_msec was set to 3 min.
      A MacBook Pro 18,4 (Apple M1 Max, 10 cores, 64 GB memory, macOS 12.1) was used for the simulation experiments.

      2.5 S-LAB problems for simulated experiments

      2.5.1 Gu et al. 2016 (Gu2016)

      We formulated a protocol based on that used by Gu et al. [
      • Gu X.
      • Neubert S.
      • Stoll N.
      • Thurow K.
      Intelligent scheduling method for life science automation systems.
      ], which is for a high-throughput screening involving coordination of multiple instruments, as an S-LAB problem (Fig. 3A, Suppl. Tables S5-S8). The protocol consists of seventeen experimental procedures, which are processed using five types of instruments (Reformatter, Motoman, Biomek2000.A3, Biomek2000.A4, and Transporters). We prepared the S-LAB problems Gu2016 ×1 and Gu2016 ×5, which consist of one and five jobs, respectively. The α value of the TCMBs was set to 10 min.

      2.5.2 RT-qPCR (qPCR)

      We formulated a protocol based on reverse transcription-quantitative polymerase chain reaction (RT-qPCR) involving coordination of multiple instruments using SARS-CoV-2 direct detection RT-qPCR kit (Takara Bio Inc., Shiga, Japan) [
      • Nagura-Ikeda M.
      • Imai K.
      • Tabata S.
      • Miyoshi K.
      • Murahara N.
      • Mizuno T.
      • Horiuchi M.
      • Kato K.
      • Imoto Y.
      • Iwata M.
      • Mimura S.
      • Ito T.
      • Tamura K.
      • Kato Y.
      Clinical evaluation of self-collected saliva by quantitative reverse transcription-PCR (RT-qPCR), direct RT-qPCR, reverse transcription-loop-mediated isothermal amplification, and a rapid antigen test to diagnose COVID-19.
      ,

      Takara Bio Inc.. Direct one-step RT-qPCR mix for SARS-CoV-2 protocol-at-a-glance. https://www.takarabio.com/resourcedocument/x225225, Accessed: 2022-7-7.

      ] as an S-LAB problem (Fig. 4A, Suppl. Tables S9-S12). The protocol consists of sixteen experimental procedures, which are processed by six types of instruments (Tecan (Type1), Tecan (Type2), Tecan (Type3), Plate Centrifuge, RT-qPCR, and Transporters). Note that the different experimental instruments are allocated to avoid cross-contamination between samples, which Tecan (Type 1) is for reagent preparation, Tecan (Type 2) is for sample preprocessing, Tecan (Type 3) is for adding nucleic acids as templates into PCR reaction solution. We prepared the S-LAB problem qPCR ×5, which consists of five jobs. The α value of the TCMBs was set to 5 min.

      2.5.3 Library preparation for RNA sequencing (RNAseq)

      We formulated a protocol for DNA library preparation of RNA sequencing as an S-LAB problem (Fig. 5A, Suppl. Tables S13-S16). The protocol consists of RNA extraction by LabDroid Maholo (Robotic Biology Institute Inc., Tokyo, Japan) [
      • Yachie N.
      • Takahashi K.
      • Katayama T.
      • Sakurada T.
      • Kanda G.N.
      • Takagi E.
      • Hirose T.
      • Katsura T.
      • Moriya T.
      • Kitano H.
      • Tsujii J.
      • Shiraki T.
      • Kariyazaki H.
      • Kamei M.
      • Abe N.
      • Fukuda T.
      • Sawada Y.
      • Hashiguchi Y.
      • Matsukuma K.
      • Murai S.
      • Sasaki N.
      • Ipposhi T.
      • Urabe H.
      • Kudo T.
      • Umeno M.
      • Ono S.
      • Miyauchi K.
      • Nakamura M.
      • Kizaki T.
      • Suyama T.
      • Hatta T.
      • Natsume T.
      • Ohta T.
      • Ozawa Y.
      • Ihara S.
      • Tamaki S.
      • Antezana E.
      • Garcia-Castro A.
      • Perret J.-L.
      • Ishiguro S.
      • Mori H.
      • Evans-Yamamoto D.
      • Masuyama N.
      • Tomita M.
      • Katayama T.
      • Matsumoto M.
      • Nakayama H.
      • Shirasawa A.
      • Shimbo K.
      • Yamada N.
      • Nakayama K.I.
      • Shimizu T.
      • Saya H.
      • Yamashita S.
      • Matsushima T.
      • Asahara H.
      • Eguchi H.
      • Mikamori M.
      • Mori M.
      • Natsume T.
      Robotic crowd biology with Maholo LabDroids.
      ] using Qiagen RNeasy mini kit (QIAGEN, Hilden, Germany) [], RNA quantification by Maholo using Qubit RNA HS Assay Kit (Thermo Fisher Scientific, Inc., Waltham, MA) [

      Probes M.. Qubit™dsDNA HS assay kits. 2010.

      ], and RNA-seq library preparation by the Freedom Evo 150 workstation (Tecan Group, Ltd., Männedorf, Switzerland) and a PCR instrument using Illumina TruSeq RNA sample preparation v2 (Illumina, Inc., San Diego, CA) []. The protocol consists of 28 experimental procedures, which are processed by four types of instruments (Maholo, Transporter, Tecan, and PCR). We prepared the S-LAB problem RNAseq ×5 and RNAseq ×10, which consist of five and ten jobs, respectively. The α value of the TCMBs was set to 5 min.

      2.5.4 Composite of qPCR and RNAseq

      We prepared a S-LAB problem which consists of two different types of jobs. qPCR ×5 RNAseq ×5 consists of five qPCR jobs (qPCR ×5) and five RNAseq jobs (RNAseq ×5). The jobs are processed by the nine types of instruments (Tecan (Type1), Tecan (Type2), Tecan (Type3), Plate Centrifuge, RT-qPCR, Transporters, Maholo, Transporter, Tecan, and PCR). The α value of the TCMBs was set to 5 min.

      3. Results

      3.1 SAGAS can find feasible solutions and optimal solutions for a simple S-LAB problem

      SLab.jl uses the branch-and-bound method, an exact algorithm, so can find an optimal solution for S-LAB problems. Thus, we define an optimal solution as one with the same execution time as the solution found by SLab.jl and satisfies all the constraints. SLab.jl had found an optimal solution (with an overall runtime of 87.0 min) in 1.6 s for an S-LAB problem Gu2016 ×1 (Fig. 2A) [
      • Itoh T.D.
      • Horinouchi T.
      • Uchida H.
      • Takahashi K.
      • Ozaki H.
      Optimal scheduling for laboratory automation of life science experiments with time constraints.
      ,
      • Gu X.
      • Neubert S.
      • Stoll N.
      • Thurow K.
      Intelligent scheduling method for life science automation systems.
      ], and we investigated whether SAGAS could find a feasible solution for the same problem in about 1.6 s. The results showed that SAGAS and SA-Mod found optimal solutions (Fig. 2B-E, Table S1), whereas greedy and SA found only scheduling results with longer execution times. This suggests that SAGAS can find feasible solutions and optimal solutions, as well as solutions that are equal to or better than Greedy.
      Fig. 2
      Fig. 2(A) Schematic diagram of the scheduling problem of Gu2016 ×1 (Suppl. Tables S1-S4 describe a detailed description). A gray box represents a transportation operation processed by a transporter. (B–E) Scheduling result of Gu2016 ×1 by SA (B), SA-Mod (C), Greedy (D), and SAGAS (E). A dotted line represents dependencies between operations. Each vertical black solid line represents the execution time of the optimal solution found by SLab.jl.
      Fig. 3
      Fig. 3(A) Schematic diagram of the scheduling problem of Gu2016 ×5 (Suppl. Tables S5-S8 describe a detailed description). A gray box represents a transportation operation processed by a transporter. (B) The execution time (min) of the feasible solutions found by each algorithm for Gu2016 ×5. Computation was performed one time for Greedy and five times for SA, SA-Mod, and SAGAS. Each dot represents each computation. Box plots show the minimum (lower whisker), lower quartile (lower hinge), median, upper quartile (upper hinge), and maximum (upper whisker). (C) The computation time (s) corresponding to the computation in (B). Each dot represents each computation and the bar plots show the mean. (E-G) Scheduling result of Gu2016 ×5 by SA-Mod (E), Greedy (F), and SAGAS (G). Because all the solutions from SA are failed solutions, the result of SA is not shown (D). A dotted line represents dependencies between operations.
      Fig. 4
      Fig. 4(A) Schematic diagram of the scheduling problem of qPCR ×5 (Suppl. Tables S9-S12 describe a detailed description). A gray box represents a transportation operation processed by a transporter. (B) The execution time (min) of the feasible solutions found by each algorithm for qPCR ×5. Computation was performed one time for Greedy and five times for SA, SA-Mod, and SAGAS. Each dot represents each computation. Box plots show the minimum (lower whisker), lower quartile (lower hinge), median, upper quartile (upper hinge), and maximum (upper whisker). (C) The computation time (s) corresponding to the computation in (B). Each dot represents each computation and the bar plots show the mean. (D–G) Scheduling result of qPCR ×5 by SA (D), SA-Mod (E), Greedy (F), and SAGAS (G). A dotted line represents dependencies between operations.
      Fig. 5
      Fig. 5(A) Schematic diagram of the scheduling problem of RNAseq ×5 (Suppl. Tables S13-S16 describe a detailed description). A gray box represents a transportation operation processed by a transporter. (B) The execution time (min) of the feasible solutions found by each algorithm for RNAseq ×5. Computation was performed one time for Greedy and five times for SA, SA-Mod, and SAGAS. Each dot represents each computation. Box plots show the minimum (lower whisker), lower quartile (lower hinge), median, upper quartile (upper hinge), and maximum (upper whisker). (C) The computation time (s) corresponding to the computation in (B). Each dot represents each computation and the bar plots show the mean. (D–G) Scheduling result of RNAseq ×5 by SA (D), SA-Mod (E), Greedy (F), and SAGAS (G). A dotted line represents dependencies between operations.

      3.2 SAGAS is effective for complex S-LAB problems

      In general, simulated annealing requires a sufficiently large computation time depending on the complexity of the problem to output a better solution [
      • Aarts E.
      • Korst J.
      • Michiels W.
      Simulated annealing.
      ,
      • van Laarhoven P.J.M.
      ]. Therefore, to confirm the versatility of SAGAS, we investigated whether SAGAS can find solutions to complex S-LAB problems in a practicable time. Assuming a real laboratory, we applied two types of complex problems: one involving multiple jobs of one type (five jobs of the Gu2016 job (Gu2016 ×5) (Fig. 3A, Suppl. Tables S5-S8), five jobs of the qPCR job (qPCR ×5) (Fig. 4A, Suppl. Tables S9-S12), and five Jobs of the RNAseq job (RNAseq ×5) (Fig. 5A, Suppl. Tables S13-S16)), and the other including multiple jobs of several types of jobs that share an instrument type (qPCR ×5 RNAseq ×5) (Fig. 6A, Suppl. Tables S17-S20) (see Materials and Methods). We repeated the calculations of SA, SA-Mod, and SAGAS five times because these are probabilistic algorithms. We note that SLab.jl was unable to find an optimum solution to these problems within one hour.
      Fig. 6
      Fig. 6(A) Schematic diagram of the scheduling problem of qPCR ×5 RNAseq ×5 (Suppl. Tables S17-S20 describe a detailed description). A gray box represents a transportation operation processed by a transporter. (B) The execution time (min) of the feasible solutions found by each algorithm for qPCR ×5 RNAseq ×5. Computation was performed one time for Greedy and five times for SA, SA-Mod, and SAGAS. Each dot represents each computation. Box plots show the minimum (lower whisker), lower quartile (lower hinge), median, upper quartile (upper hinge), and maximum (upper whisker). (C) The computation time (s) corresponding to the computation in (B). Each dot represents each computation and the bar plots show the mean. (D–G) Scheduling result of qPCR ×5 RNAseq ×5 by SA (D), SA-Mod (E), Greedy (F), and SAGAS (G). A dotted line represents dependencies between operations.
      For Gu2016 ×5, SAGAS and Greedy found the solution with the shortest execution time; SA-Mod found the next smallest solution, and SA did not output a solution (Fig. 3B). SAGAS adopted Greedy’s solution in all five calculations (Table S1). The computation times were 180, 181, 30.8, and 211 s for SA, SA-Mod, Greedy, and SAGAS, respectively (Fig. 3C). The minimum execution time of the solutions by Greedy and SAGAS was 386 min, while that of SA-Mod was 389 min. In addition, all SA solutions were failed solutions (solutions that did not meet all the constraints) (Fig. 3D–G). Note that the discrepancy between SA and SA-Mod results is probably due to the stochastic nature of the SA step and the potential for the final modification step to modify a failed SSA into a feasible SSAMod.
      For qPCR ×5, SAGAS and Greedy found the solution with the shortest execution time, followed by SA-Mod, with SA outputting the scheduling with the longest execution time (Fig. 4B). SAGAS adopted Greedy’s solutions for all five calculations (Table S1). The computation times for SA, SA-Mod, Greedy, and SAGAS were 180, 181, 0.069, and 182 s respectively (Fig. 4C). The minimum execution time output by Greedy and SAGAS was 152 min, while the minimum execution time output by SA and SA-Mod was 236 and 192 min, respectively (Fig. 4D–G).
      For RNAseq ×5, SAGAS, SA-Mod, Greedy, and SA found solutions with shorter execution times in that order (Fig. 5B). SAGAS adopted the SA-Mod solutions as the output for all five calculations (Table S1). The computation times were 180, 220, 0.813, and 199 s for SA, SA-Mod, Greedy, and SAGAS, respectively (Fig. 5C). The minimum execution times output by SA, SA-Mod, Greedy, and SAGAS were 3,129, 1,227, 1,682, and 1,153 min, respectively (Fig. 5D–G).
      Consequently, SAGAS can schedule large-size scheduling problems involving multiple jobs of one type in several minutes. Whether the execution time found by SAGAS is superior to Greedy depends on the problem (Basically, SAGAS (Greedy, SA-Mod) < SA holds). SA-Mod < SA generally held and the execution times shrank by 40% for RNAseq ×5 and by 81% for qPCR ×5 from SA to SA-Mod, indicating that the final modification step generally improves the execution time. The results also suggest that the hybrid of SA-Mod with Greedy enabled scheduling with a shorter execution time by SAGAS even when the SA (SA-Mod) step falls into local optima. For all of the above problems, SAGAS found feasible solutions with computation times shorter than 300 sec. These results indicate that practicable computation time solutions can be found for this level of complexity.
      Next, we performed simulations with an annealing time of 3 min for the problem involving several types of jobs that share some of the instruments: qPCR ×5 and RNAseq ×5 (qPCR ×5 RNAseq ×5) (Fig. 6A). The execution time of the solutions was shorter for SAGAS, SA-Mod, Greedy, and SA in that order (Fig. 6B). The computation times were 180, 439, 3.00, and 593 s for SA, SA-Mod, Greedy, and SAGAS, respectively (Fig. 6C). The scheduling results with the minimum execution times for SA (3,302 min), SA-Mod (1,261 min), Greedy (1,885 min), and SAGAS (1,186 min) were shown (Fig. 6D-G). These results suggested that it is possible to find a scheduling solution with as short an execution time as possible in a practicable time for scheduling problems consisting of multiple types of jobs that share the same type of instrument. SAGAS took 3.30 times more than 180 sec, or 594 s on average, to output. The greedy algorithm, meanwhile, took 3 s. This suggests that the final modification takes more time when the problem is more complex to some extent.

      3.3 SAGAS enables the simulation-based design of laboratory configuration

      In S-LAB problems, the laboratory configuration is usually fixed. On the other hand, searching for laboratory configurations that reduce execution time is important for automated laboratory design. Itoh et al. investigated how changing the number of a certain type of instrument affected the execution time [
      • Itoh T.D.
      • Horinouchi T.
      • Uchida H.
      • Takahashi K.
      • Ozaki H.
      Optimal scheduling for laboratory automation of life science experiments with time constraints.
      ]: They manually changed the laboratory configuration, iteratively performed scheduling as a simulation, and compared the execution time among different laboratory configurations [
      • Itoh T.D.
      • Horinouchi T.
      • Uchida H.
      • Takahashi K.
      • Ozaki H.
      Optimal scheduling for laboratory automation of life science experiments with time constraints.
      ]. In this study, by taking advantage of the execution time shortened by SAGAS, we next aimed to conduct a grid search of a large of possible laboratory configurations.
      We used the following problem setup: 10 Jobs of the RNAseq job (RNAseq ×10) with one of each type of instrument as the initial condition. SAGAS simulated the problem five times for each laboratory configuration (Fig. 7A). The total computation time for the grid search was 80,284 s. To investigate the impact of each instrument, we tabulated the minimum values for each combination of the numbers of the allocated instruments. As a result, the impact of increasing instrument type 1, 2, 3, and 4 by one was - 402 min, - 294 min, - 3110 min, and - 1794 min, respectively (Fig 7B–E, Suppl. Table S2). Accordingly, the highest-impact instrument is Instrument 3 in the scope of the search. Moreover, we should consider a trade-off between cost and reduced experimental time in actual situations. To evaluate this point, we calculated how many instruments would be required to reduce the execution time to be halved. The result of the execution time without additional instruments was 6,015 min, adding instrument types 3 and 4 one by one can reduce the execution time to 2,940 min (48.9%) (Fig. 7F). Hence, we demonstrated that SAGAS can perform a simulation-based laboratory configuration design by considering the trade-off between the number of instruments and the time saved by SAGAS.
      Fig. 7
      Fig. 7(A) An example of grid search for simulation-based laboratory configuration. (B) Schematic diagram of the scheduling problem of RNAseq ×1 and the variation range of the number of each instrument used in RNAseq ×10. RNAseq ×10 is an experiment composed of ten RNAseq ×1. (C) The effect of the number of each type of instrument on the execution time for the feasible solutions found by SAGAS for RNAseq ×10. Computation was performed five times. Box plots represent minimum (lower whisker), lower quartile (lower hinge), median, upper quartile (upper hinge), maximum (upper whisker), and violin plots represent the density of data points. (D) The complete result of the experiment. The x-axis shows the combination of the number of instruments for each laboratory configuration (For example, 2-1-3-4 means the numbers of instrument types 1, 2, 3, and 4 are 2, 1, 3, and 4, respectively).

      3.4 SAGAS depends on computation time and complexity of problem

      In this study, we tentatively defined the annealing time as 3 min. On the other hand, extending the annealing time could further reduce total execution time. Thus, we increased the annealing time from 3 min to 60 min for the S-LAB problems and investigated the reduction rate of the execution time. We found that only a slight reduction in overall run time (0.3% reduction (385 min) for Gu2016 ×5, no change for qPCR ×5, 3.2% reduction (1,055 min) for RNAseq ×5, and 2.7% shorter (1,114 min) for qPCR ×5 RNAseq ×5 against qPCR ×5 (Fig. S1). These results suggest that the 3 min of annealing time is sufficient for S-LAB problems with the degree of complexity discussed in this study.
      Conversely, for more complex S-LAB problems, we expected that a longer annealing time is required for the decrease in execution time to saturate. By SAGAS and greedy algorithm, we performed simulations for different annealing times (1 s, 3 s, 10 s, 30 s, 1 min, 3 min, 10 min, 30 min, 1 h, and 3 h) for S-LAB problems (RNAseq ×1, RNAseq ×5, RNAseq ×10, RNAseq ×15, RNAseq ×20, and RNAseq ×25). The results suggest that as the problem’s complexity increases, a longer annealing time is required for the reduction in execution time to saturate (Supplementary Figure 1).

      4. Discussion

      In this study, we proposed a scheduling algorithm SAGAS, combining simulated annealing, a metaheuristic algorithm, and the greedy algorithm to solve the S-LAB problem (Fig. 1A). The distinction between SLab.jl, previous work, and SAGAS lies in their objectives. Where SLab.jl aims to find an optimal solution, SAGAS utilizes a metaheuristic algorithm to find a sub-optimal solution that meets the constraints within a practicable time. Thus, SAGAS was able to output a solution to the S-LAB problems that satisfied the constraints, including TCMBs (Fig. 2, Fig. 3, Fig. 4, Fig. 5), even though SLab.jl, which uses an exact algorithm, did not finish the computation for the same problems in a practicable time. SAGAS was also effective for the complex S-LAB problem consisting of multiple types of jobs (Fig. 6). Therefore, SAGAS could apply to a wide range of S-LAB problems. Furthermore, due to the improved computation time of SAGAS, SAGAS could enable simulation-based laboratory configuration design [
      • Itoh T.D.
      • Horinouchi T.
      • Uchida H.
      • Takahashi K.
      • Ozaki H.
      Optimal scheduling for laboratory automation of life science experiments with time constraints.
      ] using grid search by iteratively performing scheduling S-LAB problems with different laboratory configurations (Fig. 7).
      Two major reasons could explain the high performance of SAGAS (Table 1). One reason is that SAGAS is a hybrid algorithm. Depending on the problem setup, sometimes Greedy’s solutions were chosen (Figs. 3 and 4), and sometimes SA-Mod’s solutions were chosen (Figs. 5 and 6) by SAGAS. These results indicate that both Greedy’s and SA-Mod steps are important for the performance of SAGAS. The other is that SAGAS makes the final modification to the SA solution. In all simulations, SA-Mod found shorter execution times than SA did (e.g., focusing on the mean value of the solution, up to 61.7% reduction in execution time was observed in SA-Mod compared to SA for qPCR ×5 RNAseq ×5). This result suggests that improving SA solutions by the final modification step also explains why SAGAS can obtain better solutions despite its relatively short computation time.
      Table 1Summary of the simulated experiment results for Gu ×1, Gu ×5, qPCR ×5, RNAseq ×5, qPCR ×5 RNAseq ×5: The numbers in parentheses indicate the number of results used in the calculation, while the number of computation times is calculated using all results, and the number of execution times is calculated using only non-failed results. N indicates the number of all operations in each S-LAB problem.
      S-LAB problemSchedulerMinimum execution time (min)Avarge execution time (min)Avarage computation time (min)
      Gu ×1Greedy90 (1)90 (1)0.000 (1)
      N=17SA111 (4)118 (4)0.025 (5)
      SAGAS87 (5)87 (5)0.025 (5)
      SA-Mod87 (4)88 (4)0.025 (5)
      Gu ×5Greedy386 (1)386 (1)0.513 (1)
      N=17×5SANA(0)NA(0)3.000 (5)
      SAGAS386 (5)386 (5)3.518 (5)
      SA-Mod389 (1)389 (1)3.028 (5)
      qPCR ×5Greedy152 (1)152 (1)0.001 (1)
      N=16×5SA236 (5)256 (5)3.000 (5)
      SAGAS152 (5)152 (5)3.026 (5)
      SA-Mod192 (5)200 (5)3.012 (5)
      RNAseq ×5Greedy1682 (1)1682 (1)0.014 (1)
      N=28×5SA2417 (5)2810 (5)3.000 (5)
      SAGAS1090 (5)1118 (5)3.320 (5)
      SA-Mod1053 (5)1152 (5)3.675 (5)
      qPCR ×5Greedy1885 (1)1885 (1)0.050 (1)
      RNAseq ×5SA3163 (5)3303 (5)3.000 (5)
      N=16×5+28×5SAGAS1145 (5)1187 (5)9.890 (5)
      SA-Mod1160 (5)1261 (5)7.322 (5)
      In addition to scheduling experiments for a single fixed laboratory configuration, it is important to design efficient laboratory configurations by scheduling simulations, especially for automated experiments that involve multiple specialized and general-purpose instruments. Automated laboratories consist of not only single-purpose instruments [
      • Wang Y.
      • Liu Y.
      • Liu J.
      • Guo Y.
      • Fan L.
      • Ni X.
      • Zheng X.
      • Wang M.
      • Zheng P.
      • Sun J.
      • Ma Y.
      MACBETH: multiplex automated corynebacterium glutamicum base editing method.
      ,
      • Burns C.G.
      • Milan D.J.
      • Grande E.J.
      • Rottbauer W.
      • MacRae C.A.
      • Fishman M.C.
      High-throughput assay for small molecules that modulate zebrafish embryonic heart rate.
      ,
      • Huang D.
      • Ou B.
      • Hampsch-Woodill M.
      • Flanagan J.A.
      • Prior R.L.
      High-throughput assay of oxygen radical absorbance capacity (ORAC) using a multichannel liquid handling system coupled with a microplate fluorescence reader in 96-well format.
      ,
      • Supply P.
      • Lesjean S.
      • Savine E.
      • Kremer K.
      • van Soolingen D.
      • Locht C.
      Automated high-throughput genotyping for study of global epidemiology of mycobacterium tuberculosis based on Mycobacterial interspersed repetitive units.
      ,
      • Yoshimoto N.
      • Kida A.
      • Jie X.
      • Kurokawa M.
      • Iijima M.
      • Niimi T.
      • Maturana A.D.
      • Nikaido I.
      • Ueda H.R.
      • Tatematsu K.
      • Tanizawa K.
      • Kondo A.
      • Fujii I.
      • Kuroda S.
      An automated system for high-throughput single cell-based breeding.
      ] but also general-purpose instruments [
      • Kanda G.N.
      • Tsuzuki T.
      • Terada M.
      • Sakai N.
      • Motozawa N.
      • Masuda T.
      • Nishida M.
      • Watanabe C.T.
      • Higashi T.
      • Horiguchi S.A.
      • Kudo T.
      • Kamei M.
      • Sunagawa G.A.
      • Matsukuma K.
      • Sakurada T.
      • Ozawa Y.
      • Takahashi M.
      • Takahashi K.
      • Natsume T.
      Robotic search for optimal cell culture in regenerative medicine.
      ,
      • Konagaya S.
      • Ando T.
      • Yamauchi T.
      • Suemori H.
      • Iwata H.
      Long-term maintenance of human induced pluripotent stem cells by automated cell culture system.
      ,
      • Ochiai K.
      • Motozawa N.
      • Terada M.
      • Horinouchi T.
      • Masuda T.
      • Kudo T.
      • et al.
      A variable scheduling maintenance culture platform for mammalian cells.
      ,
      • Yachie N.
      • Takahashi K.
      • Katayama T.
      • Sakurada T.
      • Kanda G.N.
      • Takagi E.
      • Hirose T.
      • Katsura T.
      • Moriya T.
      • Kitano H.
      • Tsujii J.
      • Shiraki T.
      • Kariyazaki H.
      • Kamei M.
      • Abe N.
      • Fukuda T.
      • Sawada Y.
      • Hashiguchi Y.
      • Matsukuma K.
      • Murai S.
      • Sasaki N.
      • Ipposhi T.
      • Urabe H.
      • Kudo T.
      • Umeno M.
      • Ono S.
      • Miyauchi K.
      • Nakamura M.
      • Kizaki T.
      • Suyama T.
      • Hatta T.
      • Natsume T.
      • Ohta T.
      • Ozawa Y.
      • Ihara S.
      • Tamaki S.
      • Antezana E.
      • Garcia-Castro A.
      • Perret J.-L.
      • Ishiguro S.
      • Mori H.
      • Evans-Yamamoto D.
      • Masuyama N.
      • Tomita M.
      • Katayama T.
      • Matsumoto M.
      • Nakayama H.
      • Shirasawa A.
      • Shimbo K.
      • Yamada N.
      • Nakayama K.I.
      • Shimizu T.
      • Saya H.
      • Yamashita S.
      • Matsushima T.
      • Asahara H.
      • Eguchi H.
      • Mikamori M.
      • Mori M.
      • Natsume T.
      Robotic crowd biology with Maholo LabDroids.
      ]. Accordingly, multiple types of specialized and general-purpose instruments would increasingly be highly integrated to complete even a single experimental procedure [
      • Lehmann R.
      • Severitt J.C.
      • Roddelkopf T.
      • Junginger S.
      • Thurow K.
      Biomek cell workstation: a variable system for automated cell cultivation.
      ,
      • Vorberg E.
      • Fleischer H.
      • Junginger S.
      • Liu H.
      • Stoll N.
      • Thurow K.
      A highly flexible, automated system providing reliable sample preparation in element- and Structure-Specific measurements.
      ]. To design efficient laboratory configurations, it is important to consider involves the number of the same type of instruments and what and how many additional instruments should be added to the experiment to make the execution of experiments more efficient. By exhaustively simulating scheduling for different instrument configurations, SAGAS helps us to design laboratory configurations balancing the cost and the benefit. For example, SAGAS has shown that adding two of the four types of instruments, one at a time, can reduce experimental time by 50% (Fig. 7F). In addition, deciding which instruments to introduce in a group of experiments becomes increasingly important, as not only one but several laboratories share the same type of instruments. Simulation-based laboratory configuration design will become increasingly important as the complexity of such automated experiments increases.
      SAGAS could find accurate solutions for a simple problem as fast as the branch-and-bound method, an exact algorithm, and had stable computation times for several complex problems where SLab.jl could not find a solution. SAGAS found the optimal solution for the simple S-LAB problem Gu2016 ×1 in about the same computation time as the branch-and-bound method, an exact algorithm, suggesting that SAGAS can find accurate solutions for simple problems faster. Furthermore, the computation times for Gu2016 ×5, RNA ×5, and qPCR ×5 were stable, with a maximum computation time of 5 min in the RNAseq ×5 SA-Mod (Fig. 3, Fig. 4, Fig. 5). On the other hand, the more complex qPCR×5 RNAseq×5 showed more variability, with a maximum computation time of 20 min (Fig. 6). Therefore, it is expected that the complexity of the problem would increase the computation time, as the entire computation time would be greatly influenced by the final modification, whose computation time is indefinite.
      There are several potential limitations to this study. To shorten the execution time within a practicable computation time, the threshold of the annealing time was set to 3 min in this study. However, the appropriate computation time might vary from situation to situation. In SAGAS implementations, depending on the desired situation, users can limit the computation time by setting the runtime threshold SA_msec or execute only the Greedy step to reduce the computation time even further. Second, this study assumes that the sample transport time between instruments is fixed across all combinations of instruments. In practice, however, we have to consider the transport times according to the physical spatial arrangement of the instruments, especially in the design of laboratory configuration. Extension of SAGAS to simultaneously determine the sample transport time considering physical laboratory environments is desired in future developments. Third, the complexity of the problem is not well-defined. Currently, we do not know in advance whether SA-Mod and Greedy solutions are chosen for a certain S-LAB problem. Besides, it is generally not clear what size of the S-LAB problem is the limit for SA-Mod to find a feasible solution in a reasonable time. For example, the number of operations, dependencies, and TCMBs do not necessarily determine whether SA-Mod or Greedy solutions is adopted as the output for SAGAS (Supplementary Figure 2, Suppl. Table S21). Systematic evaluation based on simulation experiments for a wide variety of S-LAB problems of various sizes will be necessary to understand the relationship between the size of S-LAB problems and the computation performance of SAGAS. Fourth, dynamic scheduling is not considered in this study. Dynamic scheduling is essential when accidents occur in an automated laboratory and experimental procedures cannot be executed according to a predetermined schedule. To achieve dynamic scheduling, it is worth considering extending SAGAS to allow the rescheduling of failed operations or jobs while taking into account operations that have already finished or are in progress.
      We proposed the scheduler SAGAS, which can output feasible solutions for complex S-LAB problems for which the exact algorithm does not finish the calculation in a reasonable time, and proposed a method for simulation-based laboratory configuration design using SAGAS. Laboratory automation requires high-quality feasible solutions to be output in a short time, and SAGAS can achieve this objective. Thus, it can find solutions for different types of S-LAB problems practically. In particular, the proposed laboratory configuration allows multiple laboratories to use common instruments according to the desired experimental time, leading to increased productivity. The source code of SAGAS is freely available on GitHub and run locally or on Google Colaboratory, ensuring affordability to the wide range of automated laboratories.

      Funding

      The authors disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the JST-Mirai Program (grant number JPMJMI18G4).

      Data availability

      The data for Fig. 2B-E, Fig. 3B-G, Fig. 4B-G, Fig. 5B-G, Fig. 6B-G, Fig. 7A, C, and D are available at the GitHub repository (https://github.com/bioinfo-tsukuba/SAGAS_paper).

      Declaration of Competing Interest

      The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

      Acknowledgments

      We thank T.D. Itoh, G.N. Kanda, and T. Tsuzuki for helpful discussion.

      Appendix A. Supplementary materials

      • Supplementary Data S3

        Supplementary Table 1: List of operations of one job in the simulated experiment Gu2016 ×1.

        Supplementary Table 2: List of instruments used in the simulated experiment Gu2016 ×1.

        Supplementary Table 3: List of the dependencies among the operations of one job in the simulated experiment Gu2016 ×1.

        Supplementary Table 4: List of the TCMBs among the operations of one job in the simulated experiment Gu2016 ×1.

        Supplementary Table 5: List of operations of one job in the simulated experiment Gu2016 ×5.

        Supplementary Table 6: List of instruments used in the simulated experiment Gu2016 ×5.

        Supplementary Table 7: List of the dependencies among the operations of one job in the simulated experiment Gu2016 ×5.

        Supplementary Table 8: List of the TCMBs among the operations of one job in the simulated experiment Gu2016 ×5.

        Supplementary Table 9: List of operations of one job in the simulated experiment qPCR ×5.

        Supplementary Table 10: List of instruments used in the simulated experiment qPCR ×5.

        Supplementary Table 11: List of the dependencies among the operations of one job in the simulated experiment qPCR ×5.

        Supplementary Table 12: List of the TCMBs among the operations of one job in the simulated experiment qPCR ×5.

        Supplementary Table 13: List of operations of one job in the simulated experiment RNAseq ×5.

        Supplementary Table 14: List of instruments used in the simulated experiment RNAseq ×5.

        Supplementary Table 15: List of the dependencies among the operations of one job in the simulated experiment RNAseq ×5.

        Supplementary Table 16: List of the TCMBs among the operations of one job in the simulated experiment RNAseq ×5.

        Supplementary Table 17: List of operations of one job in the simulated experiment qPCR ×5 RNAseq ×5.

        Supplementary Table 18: List of instruments used in the simulated experiment qPCR ×5 RNAseq ×5.

        Supplementary Table 19: List of the dependencies among the operations of one job in the simulated experiment qPCR ×5 RNAseq ×5.

        Supplementary Table 20: List of the TCMBs among the operations of one job in the simulated experiment qPCR ×5 RNAseq ×5.

        Supplementary Table 21: List of the number of times the Greedy step and SA-Mod step were chosen for SAGAS output, operations, dependencies, and TCMBs for the different S-LAB problems.

        Supplementary Raw Research Data. This is open data under the CC BY license http://creativecommons.org/licenses/by/4.0/

      References

        • Wang Y.
        • Liu Y.
        • Liu J.
        • Guo Y.
        • Fan L.
        • Ni X.
        • Zheng X.
        • Wang M.
        • Zheng P.
        • Sun J.
        • Ma Y.
        MACBETH: multiplex automated corynebacterium glutamicum base editing method.
        Metab Eng. 2018; 47: 200-210
        • Hess J.F.
        • Kohl T.A.
        • Kotrová M.
        • Rönsch K.
        • Paprotka T.
        • Mohr V.
        • Hutzenlaub T.
        • Brüggemann M.
        • Zengerle R.
        • Niemann S.
        • Paust N.
        Library preparation for next generation sequencing: a review of automation strategies.
        Biotechnol Adv. 2020; 41: 107537
        • Matsumoto E.
        • Koide N.
        • Hanzawa H.
        • Kiyama M.
        • Ohta M.
        • Kuwabara J.
        • Takeda S.
        • Takahashi M.
        Fabricating retinal pigment epithelial cell sheets derived from human induced pluripotent stem cells in an automated closed culture system for regenerative medicine.
        PLOS ONE. 2019; 14: e0212369
        • Nishimura A.
        • Nakajima R.
        • Takagi R.
        • Zhou G.
        • Suzuki D.
        • Kiyama M.
        • Nozaki T.
        • Owaki T.
        • Takahara T.
        • Nagai S.
        • Nakamura T.
        • Sugaya M.
        • Terada K.
        • Igarashi Y.
        • Hanzawa H.
        • Okano T.
        • Shimizu T.
        • Yamato M.
        • Takeda S.
        Fabrication of tissue-engineered cell sheets by automated cell culture equipment.
        J Tissue Eng Regen Med. 2019; 13: 2246-2255
        • Jiang X.
        • Feng S.
        • Tian R.
        • Han G.
        • Jiang X.
        • Ye M.
        • Zou H.
        Automation of nanoflow liquid chromatography-tandem mass spectrometry for proteome analysis by using a strong cation exchange trap column.
        Proteomics. 2007; 7: 528-539
        • Lopez M.F.
        • Kristal B.S.
        • Chernokalskaya E.
        • Lazarev A.
        • Shestopalov A.I.
        • Bogdanova A.
        • Robinson M.
        High-throughput profiling of the mitochondrial proteome using affinity fractionation and automation.
        Electrophoresis. 2000; 21: 3427-3440
        • Burns C.G.
        • Milan D.J.
        • Grande E.J.
        • Rottbauer W.
        • MacRae C.A.
        • Fishman M.C.
        High-throughput assay for small molecules that modulate zebrafish embryonic heart rate.
        Nat Chem Biol. 2005; 1: 263-264
        • Huang D.
        • Ou B.
        • Hampsch-Woodill M.
        • Flanagan J.A.
        • Prior R.L.
        High-throughput assay of oxygen radical absorbance capacity (ORAC) using a multichannel liquid handling system coupled with a microplate fluorescence reader in 96-well format.
        J Agric Food Chem. 2002; 50: 4437-4444
        • Supply P.
        • Lesjean S.
        • Savine E.
        • Kremer K.
        • van Soolingen D.
        • Locht C.
        Automated high-throughput genotyping for study of global epidemiology of mycobacterium tuberculosis based on Mycobacterial interspersed repetitive units.
        J Clin Microbiol. 2001; 39: 3563-3571
        • Yoshimoto N.
        • Kida A.
        • Jie X.
        • Kurokawa M.
        • Iijima M.
        • Niimi T.
        • Maturana A.D.
        • Nikaido I.
        • Ueda H.R.
        • Tatematsu K.
        • Tanizawa K.
        • Kondo A.
        • Fujii I.
        • Kuroda S.
        An automated system for high-throughput single cell-based breeding.
        Sci Rep. 2013; 3: 1191
        • Kanda G.N.
        • Tsuzuki T.
        • Terada M.
        • Sakai N.
        • Motozawa N.
        • Masuda T.
        • Nishida M.
        • Watanabe C.T.
        • Higashi T.
        • Horiguchi S.A.
        • Kudo T.
        • Kamei M.
        • Sunagawa G.A.
        • Matsukuma K.
        • Sakurada T.
        • Ozawa Y.
        • Takahashi M.
        • Takahashi K.
        • Natsume T.
        Robotic search for optimal cell culture in regenerative medicine.
        Elife. 2022; 11
      1. 2020.11.25.392936
        • Konagaya S.
        • Ando T.
        • Yamauchi T.
        • Suemori H.
        • Iwata H.
        Long-term maintenance of human induced pluripotent stem cells by automated cell culture system.
        Sci Rep. 2015; 5: 16647
        • Ochiai K.
        • Motozawa N.
        • Terada M.
        • Horinouchi T.
        • Masuda T.
        • Kudo T.
        • et al.
        A variable scheduling maintenance culture platform for mammalian cells.
        SLAS Technol. 2020;
      2. 247263032097210
        • Yachie N.
        • Takahashi K.
        • Katayama T.
        • Sakurada T.
        • Kanda G.N.
        • Takagi E.
        • Hirose T.
        • Katsura T.
        • Moriya T.
        • Kitano H.
        • Tsujii J.
        • Shiraki T.
        • Kariyazaki H.
        • Kamei M.
        • Abe N.
        • Fukuda T.
        • Sawada Y.
        • Hashiguchi Y.
        • Matsukuma K.
        • Murai S.
        • Sasaki N.
        • Ipposhi T.
        • Urabe H.
        • Kudo T.
        • Umeno M.
        • Ono S.
        • Miyauchi K.
        • Nakamura M.
        • Kizaki T.
        • Suyama T.
        • Hatta T.
        • Natsume T.
        • Ohta T.
        • Ozawa Y.
        • Ihara S.
        • Tamaki S.
        • Antezana E.
        • Garcia-Castro A.
        • Perret J.-L.
        • Ishiguro S.
        • Mori H.
        • Evans-Yamamoto D.
        • Masuyama N.
        • Tomita M.
        • Katayama T.
        • Matsumoto M.
        • Nakayama H.
        • Shirasawa A.
        • Shimbo K.
        • Yamada N.
        • Nakayama K.I.
        • Shimizu T.
        • Saya H.
        • Yamashita S.
        • Matsushima T.
        • Asahara H.
        • Eguchi H.
        • Mikamori M.
        • Mori M.
        • Natsume T.
        Robotic crowd biology with Maholo LabDroids.
        Nat Biotechnol. 2017; 35: 310-312
        • Lehmann R.
        • Severitt J.C.
        • Roddelkopf T.
        • Junginger S.
        • Thurow K.
        Biomek cell workstation: a variable system for automated cell cultivation.
        J Lab Autom. 2016; 21: 439-450
        • Vorberg E.
        • Fleischer H.
        • Junginger S.
        • Liu H.
        • Stoll N.
        • Thurow K.
        A highly flexible, automated system providing reliable sample preparation in element- and Structure-Specific measurements.
        SLAS Technol. 2016; 21: 682-692
        • Schäfer R.
        Concepts for dynamic scheduling in the laboratory.
        J Assoc Lab Autom. 2004; 9: 382-397
        • Shin S.H.
        • Choi B.J.
        • Ryew S.M.
        • Kim J.W.
        • Kim D.S.
        • Chung W.K.
        • et al.
        Development of an improved scheduling algorithm for lab test operations on a Small-Size bio robot platform.
        JALA J Assoc LabAutom. 2010; 15: 15-24
        • Delaney N.F.
        • Rojas Echenique J.I.
        • Marx C.J.
        Clarity: an open-source manager for laboratory automation.
        J Lab Autom. 2013; 18: 171-177
        • Burger B.
        • Maffettone P.M.
        • Gusev V.V.
        • Aitchison C.M.
        • Bai Y.
        • Wang X.
        • Li X.
        • Alston B.M.
        • Li B.
        • Clowes R.
        • Rankin N.
        • Harris B.
        • Sprick R.S.
        • Cooper A.I.
        A mobile robotic chemist.
        Nature. 2020; 583: 237-241
        • Cabrera C.
        • Fine-Morris M.
        • Pokross M.
        • Kish K.
        • Michalczyk S.
        • Cahn M.
        • Klei H.
        • Russo M.F.
        Dynamically optimizing experiment schedules of a laboratory robot system with simulated annealing.
        J Lab Autom. 2014; 19: 517-527
        • Gu X.
        • Neubert S.
        • Stoll N.
        • Thurow K.
        Intelligent scheduling method for life science automation systems.
        2016 IEEE International conference on multisensor fusion and integration for intelligent systems (MFI). 2016: 156-161
        • Neubert S.
        • Gu X.
        • Göde B.
        • Roddelkopf T.
        • Fleischer H.
        • Stoll N.
        • Thurow K.
        Workflow management system for the integration of mobile robots in future labs of life sciences.
        Chem Ing Tech. 2019; 91: 294-304
        • Itoh T.D.
        • Horinouchi T.
        • Uchida H.
        • Takahashi K.
        • Ozaki H.
        Optimal scheduling for laboratory automation of life science experiments with time constraints.
        SLAS Technol. 2021; 26: 650-659
        • Canelas A.B.
        • ten Pierick A.
        • Ras C.
        • Seifar R.M.
        • van Dam J.C.
        • van Gulik W.M.
        • Heijnen J.J.
        Quantitative evaluation of intracellular metabolite extraction techniques for yeast metabolomics.
        Anal Chem. 2009; 81: 7379-7389
        • Gallego Romero I.
        • Pai A.A.
        • Tung J.
        • Gilad Y.
        RNA-seq: impact of RNA degradation on transcript quantification.
        BMC Biol. 2014; 12: 42
        • Michl J.
        • Park K.C.
        • Swietach P.
        Evidence-based guidelines for controlling pH in mammalian live-cell culture systems.
        Commun Biol. 2019; 2: 144
        • Brucker P.
        • Jurisch B.
        • Sievers B.
        A branch and bound algorithm for the job-shop scheduling problem.
        Discrete Appl Math. 1994; 49: 107-127
        • Oliva D.
        • Abd Elaziz M.
        • Hinojosa S.
        Metaheuristic optimization.
        in: Oliva D. Abd Elaziz M. Hinojosa S. Metaheuristic algorithms for image segmentation: theory and applications. Springer International Publishing, Cham2019: 13-26
        • Cabrera C.
        • Fine-Morris M.
        • Pokross M.
        • Kish K.
        • Michalczyk S.
        • Cahn M.
        • Klei H.
        • Russo M.F.
        Dynamically optimizing experiment schedules of a laboratory robot system with simulated annealing.
        J Lab Autom. 2014; 19: 517-527
        • Gu X.
        • Neubert S.
        • Stoll N.
        • Thurow K.
        Intelligent scheduling method for life science automation systems.
        2016 IEEE International conference on multisensor fusion and integration for intelligent systems (MFI). 2016: 156-161
        • Thurow K.
        • Gu X.
        • Göde B.
        • Roddelkopf T.
        • Fleischer H.
        • Stoll N.
        • Neubert S.
        Integrating mobile robots into automated laboratory processes: a suitable workflow management system.
        SLAS Technol. 2020;
      3. 2472630320967620
        • Naderi B.
        • Azab A.
        An improved model and novel simulated annealing for distributed job shop problems.
        Int J Adv Manuf Technol. 2015; 81: 693-703
        • Lee S.
        • Kim S.B.
        Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning.
        IEEE Trans Knowl Data Eng. 2020; 32: 1157-1166
        • Yuan Y.
        • Tole K.
        • Ni F.
        • He K.
        • Xiong Z.
        • Liu J.
        Adaptive simulated annealing with greedy search for the circle bin packing problem.
        Comput Oper Res. 2022; 144: 105826
        • Cormen T.
        • Leisercon C.
        • Rivest R.
        • Stein C.
        Introduction to algorithms.
        3rd ed. The MIT Press, 2009
        • Kirkpatrick S.
        • Gelatt Jr C.D.
        • Vecchi M.P.
        Optimization by simulated annealing.
        Science. 1983; 220: 671-680
        • Cormen T.H.
        • Leiserson C.E.
        • Rivest R.L.
        • Stein C.
        Introduction to algorithms.
        4th ed. MIT Press, 2022
        • Nagura-Ikeda M.
        • Imai K.
        • Tabata S.
        • Miyoshi K.
        • Murahara N.
        • Mizuno T.
        • Horiuchi M.
        • Kato K.
        • Imoto Y.
        • Iwata M.
        • Mimura S.
        • Ito T.
        • Tamura K.
        • Kato Y.
        Clinical evaluation of self-collected saliva by quantitative reverse transcription-PCR (RT-qPCR), direct RT-qPCR, reverse transcription-loop-mediated isothermal amplification, and a rapid antigen test to diagnose COVID-19.
        J Clin Microbiol. 2020; 58
      4. Takara Bio Inc.. Direct one-step RT-qPCR mix for SARS-CoV-2 protocol-at-a-glance. https://www.takarabio.com/resourcedocument/x225225, Accessed: 2022-7-7.

      5. Qiagen N.V.. RNeasy kits, QIAGEN. https://www.qiagen.com/us/products/discovery-and-translational-research/dna-rna-purification/rna-purification/total-rna/rneasy-kits/, Accessed: 2022-7-7.

      6. Probes M.. Qubit™dsDNA HS assay kits. 2010.

      7. Illumina, Inc.. TruSeq® RNA sample preparation v2 guide. https://support.illumina.com/content/dam/illumina-support/documents/documentation/chemistry_documentation/samplepreps_truseq/truseqrna/truseq-rna-sample-prep-v2-guide-15026495-f.pdf, Accessed: 2022-7-7.

        • Aarts E.
        • Korst J.
        • Michiels W.
        Simulated annealing.
        in: Burke E.K. Kendall G. Search methodologies: introductory tutorials in optimization and decision support techniques. Springer US, Boston, MA2005: 187-210
        • van Laarhoven P.J.M.
        Theoretical and computational aspects of simulated annealing. 1988 (Ph.D. thesis)