Scheduling in this sense means
taking a workflow description and a descriptions of a lab and
assigning timestamps and machines to the steps of the workflow
in an intelligent way.
Definition of the JSSP and our generalization¶
Standard JSSP¶
We begin with the usual definition of the Job Shop Scheduling Problem (JSSP). The task is to assign an optimal schedule to a pair of workflow and lab.
Standard JSSP
A JSSP of size \(n \times m\) with \(n, m \in \mathbb{N}\) consists of a lab of \(m\) machines \(M = M_1, \ldots, M_m\) and a workflow of \(n\) jobs \(J = J_1, \ldots, J_n\) which each job consisting of \(m\) operations \(J_j = o_{1j}, \ldots, o_{mj}\). Each operation has a duration \(d_{ij} > 0\). Each operation of one job is assigned to a different machine \(M_{ij}\), i.e. \(M_{kj} \neq M_{lj}\) for \(k \neq l\).
This means that every machine will process \(n\) operations. Any machine can only do one operation at a time. The operations of each job have to be done in order, but the order of assigned machines may differ between jobs.
Schedule
A schedule \(S = \left(t_{ij}\right)_{i=1, \ldots, m}^{j=1, \ldots, n} \in \mathbb{R}_+^{n \times m}\) is valid for a standard JSSP if and only if
The makespan of a schedule \(S\) is the finishing time of the last operation, i.e. \(\max_{ij} (t_{ij} + d_{ij})\). The optimal schedule in the standard setting is a valid schedule with minimal makespan.
Robotic Lab Scheduling Problem¶
Here, we formalize our scheduling problems in the lab. We start with a formal description of the classic JSSP:
Definition 1 (JSSP).
There are \(m\) machines \(M_1, \ldots, M_m\) and \(n\) jobs \(J_1, \ldots, J_n\). Each job is a sequence of \(m\) operations:
$\(
J_i = (o_{i,1}, \ldots, o_{i,m}).
\)$
The set of all operations is denoted by \(O\). Each operation \(o \in O\) has a duration \(d(o) \in \mathbb{R}^+\) and must be done by a specific machine \(M(o)\) with \(M(o_{i,k}) \ne M(o_{i,l})\) for \(l \ne k\), i.e., each job contains exactly one operation for each machine (but the order may differ between jobs).
A solution is a schedule \(S: O \rightarrow \mathbb{R}^+\) assigning a starting time to each operation such that the operations of any job are done in order, i.e., $\( S(o_{i,k}) + d(o_{i,k}) \leq S(o_{i,k+1}) \)$ and each machine executes at most one operation at a time.
The optimum is the minimal makespan of a schedule: $\( \text{Optimum} := \min_{S \text{ is solution}} \text{makespan}(S) := \min_{S \text{ is solution}} \left\{ \max_{o \in O} (S(o) + d(o)) \right\} \tag{1} \)$
To enable modeling the properties of scheduling processes in robotic labs, we create a modification of the JSSP, which we call Robotic Lab Scheduling Problem (RLSP).
The setting of the RLSP consists of a lab and a workflow. For structural purposes, we formally describe these two parts separately. We reuse the notation from the classic JSSP. We call the description of available devices in a lab a machine configuration, which generalizes the set of machines from the standard JSSP.
Definition 2 (Machine Configuration).
A machine configuration \(L = \{M_1, \ldots, M_m\},\ m \in \mathbb{N}\) is a set of machines. There are \(t\) machine types \(T_1, \ldots, T_t\). Each machine \(M \in L\) has the following properties:
A machine type \(T(M) \in \{T_1, \ldots, T_t\}\),
A spatial capacity \(c_s(M) \in \mathbb{N}\), i.e., number of pieces of labware that fit in,
A processing capacity \(c_p(M) \in \mathbb{N}\), i.e., number of operations that can be executed in parallel,
A minimum spatial capacity \(c_{\min}(M) \in \mathbb{N}\), i.e., minimum number of labware items that need to be inside for the machine to operate,
A flag \(l(M) \in \{0,1\}\) indicating whether labware can be (un-)loaded while the machine is operating (0 means no).
Definition 3 (Workflow).
A workflow in a machine configuration \(L\) is a DAG \((O, E)\) with \(O\) being a set of operations and \(E \subseteq O \times O\) being a set of edges that mark precedence constraints between operations.
Each operation \(o \in O\) has a duration \(d(o) \in \mathbb{R}^+\) and a machine type \(T(o) \in \{T_1, \ldots, T_t\}\). There is a subset \(\hat{O} \subseteq O\) denoting the set of transportation operations.
Each edge \(e = (o_i, o_j)\) has:
Waiting cost \(wc(e) \in \mathbb{R}^+\),
Minimal waiting time \(w_{\min}(e) \in \mathbb{R}^+\),
Maximal waiting time \(w_{\max}(e) \in \mathbb{R}^+\).
To enable users to enforce an operation to be executed by a specific one of multiple identical machines, an operation can optionally have an assigned machine \(\hat{M}(o) \in M\) instead of just the type \(T(o)\).
We now generalize the notion of valid schedules:
Each transportation operation moves one labware item from its origin machine to the target machine. The workflow begins with a given number of labware items in each machine.
Capacity Constraints:
(a) No transportation operation may be executed while the target machine \(M\) holds \(c_s(M)\) pieces of labware.
(b) No transportation operation may be executed while the target machine \(M\) executes an operation if \(l(M) = 0\).
(c) No machine \(M\) may execute an operation when it contains fewer than \(c_{\min}(M)\) labware items.
(d) No machine \(M\) may execute more than \(c_p(M)\) operations in parallel.
Definition 4 (Schedule).
Given a machine configuration \(L\) and a workflow \(W = (O, E)\), a valid schedule
$\(
S : O \to \mathbb{R}^+ \times L,\quad o \mapsto (S_s(o), S_M(o))
\)$
assigns a starting time and executing machine to each operation such that:
(i) \(T(o) = T(S_M(o))\) for all \(o \in O\),
(ii) \(\hat{M}(o) = S_M(o)\) if \(\hat{M}(o)\) is defined,
(iii) For all \(e = (o_i, o_j) \in E\), $\( w_{\min}(e) \leq S_s(o_j) - (S_s(o_i) + d(o_i)) \leq w_{\max}(e), \)$
(iv) Capacity constraints (a)–(d) are respected.
To cover partially executed workflows (e.g., rescheduling), we fix \(S_s(o)\) for past operations.
In JSSP literature, schedules are usually measured by their makespan as defined in Equation (1).
However, in a robotic lab, the biochemical context demands short waiting times between specific operations, while the overall makespan is less important.
We model this by defining the cost of a schedule as a combination of waiting cost and makespan:
where
and
The weighting factor ( \alpha \in \mathbb{R} ) allows balancing between waiting time and makespan.
Final Problem Definition¶
For a given machine configuration ( L ), workflow ( (O, E) ), and cost parameter ( \alpha ), we define the Robotic Lab Scheduling Problem (RLSP) as:
