------------------
Problem Definition
------------------

`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 {math}`n \times m` with {math}`n, m \in \mathbb{N}` consists of a lab of {math}`m` machines {math}`M = M_1, \ldots, M_m` and a workflow of {math}`n` jobs {math}`J = J_1, \ldots, J_n` which each job consisting of {math}`m` operations {math}`J_j = o_{1j}, \ldots, o_{mj}`. Each operation has a duration {math}`d_{ij} > 0`. Each operation of one job is assigned to a different machine {math}`M_{ij}`, i.e. {math}`M_{kj} \neq M_{lj}` for {math}`k \neq l`.

This means that every machine will process {math}`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_ {math}`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

```{math}
\begin{align*}
    t_{ij} + d_{ij} \leq& t_{i+1,j} \text{ for } i=1, \ldots, n-1 \text{ and } j=1, \ldots, n \\
    t_{ij} + d_{ij} \leq& t_{kl} \text{ for } M_{ij}=M_{kl} \text{ and } t_{ij} < t_{kl}
\end{align*}
```

The makespan of a schedule {math}`S` is the finishing time of the last operation, i.e. {math}`\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:

$$
\text{Cost}_\alpha(S) := \text{WaitCost}(S) + \alpha \cdot \text{makespan}(S)
$$

where

$$
\text{WaitCost}(S) := \sum_{(o_i, o_j) \in E} \left[ S_s(o_j) - (S_s(o_i) + d(o_i)) \right]
$$

and

$$
\text{makespan}(S) := \max_{o \in O} \left[ S_s(o) + d(o) \right]
$$

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:

$$
\text{RLSP} := \min_{S \text{ valid}} \text{Cost}_\alpha(S)
$$