Mixed-Integer Programming Model for Scheduling with Dynamic Jobs

Question

I have an optimization problem for deliveries between production lines and a warehouse in a small facility. I need to know how many vehicles and utilities to buy, such that cost and downtime are minimized (downtime can be considered as a cost as well). The horizon is 8 hours.

It is some kind of scheduling/allocation problem, and I would like to formulate it as a mixed-integer programming problem. But I can't "visualize" this like other typical scheduling problems (e.g. job-shop or staff scheduling), so I don't know how to go about formulating the model. The kinds of scheduling problems I've seen all know their resources and jobs at the very start and just "arrange blocks" on a fixed timeline in the "best" way.

The "resources" in my case would be: vehicles, utilities, and workers. The "jobs" would be: warehouse workers loading boxes onto utilities, empty-handed vehicles traveling between lines and warehouse, vehicles transporting loaded utilities from the warehouse to a line, line workers unloading boxes from utilities, and vehicles transporting emptied utilities back to the warehouse.

Even if the number of resources were known, the jobs are still dynamic/unknown at the start. A chain of events would look like:

1. A line initiates an order for replenishment.
2. A worker in the warehouse (when available) would load a utility (when empty and present in warehouse) with the boxes ordered.
3. A vehicle (when available) would travel to the loaded utility in the warehouse, pick it up, travel to its destination line, and drop off the utility.
4. A worker at the line (when available) would unload all the boxes from the utility.
5. A vehicle (when available) would travel to the empty utility at the line, pick it up, travel to the warehouse, and drop off the empty utility.

While a worker is loading/unloading (fixed processing time), the worker is unavailable for other jobs. As soon as a utility has started to be loaded, the utility becomes unavailable. When a worker has finished loading/unloading, the worker becomes available and the loaded/empty utility waits for a vehicle. When a vehicle is traveling to pickup/dropoff a utility (fixed travelling time between warehouse and a line), the vehicle is unavailable for other jobs. When an empty utility is dropped off back at the warehouse, the utility becomes available.

So these chains of events all start from an order. But when the orders happen is not known at the very start. The example below shows that order points can vary based on when a line is running, when it goes down, and when it gets deliveries. Not stochastic, but depends on other time-related factors.

Definitions

$t \in T = \{0, 1, 2, ..., 1440\}$, set of time indices (minutes)
$m \in M = \{1, 2, ...\}$, set of components
$n \in N = \{1, 2, ...\}$, set of production lines
$j_{mn} = 1$ if component $m$ is used by line $n$, and $0$ otherwise (this is a fixed parameter table)
$q_m$, number of pieces of component $m$ in one box of $m$
$p_n$, production rate (seconds between when one piece of all components at line $n$ are simultaneously used)
$r_{mnt}$, number of pieces of $m$ remaining at line $n$ at time $t$
$b_{mnt}$, number of boxes of $m$ ordered by line $n$ at time $t$
$f_m$, maximum number of boxes of $m$ which can fit on a utility. Multiple boxes can be loaded onto a utility, but all boxes loaded on a utility can only be for a single $m$.

Example

---

$j_{11} = 1, j_{21} = 1, q_1 = 1000, q_2 = 40, p_1 = 15, f_1 = 1, f_2 = 3$

Say the line has no parts at all at $t = 0$, and makes its first order: $b_{1,1,0} = f_1 = 0, b_{2,1,0} = f_2 = 3$ (to ensure it can run for 30 minutes). Say at $t = 10, b_{1,1,0}$ arrives. Say at $t = 20, b_{2,1,0}$ arrives. At $t = 20$, the line starts. It knows it can run until it goes down at $t = 50$. With fixed lead time of $L = 10$, it will order "what it needs" at $t = 40$ i.e. only $b_{2,1,40} = 3$, as it does not need any boxes for $m = 1$ for $t \in [50, 80]$. Say the delivery arrives at $t = 60$. The line was down from $t \in [50, 60]$. At $t = 60$, $r_{1,1,60} = 880$ (remaining since $t = 50$), and $r_{2,1,60} = 120$ (replenished at $t = 60$). So from $t = 60$, the line knows it can run until it goes down at $t = 100$, and will order more $m = 2$ boxes at $t = 90$. The order points here are: $t = 0, 40, 90$.

---

So... because I can't visualize "all of the blocks" at the very start, I cannot really visualize "arranging blocks" in the first place... So I am stuck on trying to formulate an MIP model for this. I only have somewhat of an objective function below.

Objective Function

minimize cost: $C_V \sum_v x_v + C_U \sum_u y_u + C_W \sum_w z_w + \sum_n \sum_t c_n d_{nt}$

$C_V$, one-time cost for a single vehicle
$C_U$, one-time cost for a single utility
$C_W$, one-time cost for a single warehouse worker. All lines will have one worker, so not considering them as part of the cost function.
$c_n$, constant cost-per-minute for line $n$ being down.
$d_{nt} = 1$ if line $n$ is down during time $t$, and $0$ otherwise

$x_v = 1$ if vehicle $v$ is used at all in the horizon, and $0$ otherwise. Similar for $y_u$ and $z_w$. Here, I pick some reasonable/realistic upper bound for $v$, $u$, $w$, intending to "zero out" the unused $x_v$'s, $y_u$'s, and $z_w$'s... Not sure what other way there would be to find the optimal number of vehicles/utilities/workers as part of this scheduling problem.

Answer 1

To determine the number of AGVs in your production system, their working procedure should be exploded first based on the following states:

$$ \{ \text{Idle time, empty travel time, loading time, loaded travel time, unloading time, blocked time, and charging time} \}$$

The first three states usually can be predetermined, but the rest almost need to be estimated. Also, you still need to calculate two matrices. The first From-To matrix ($f_{i,j}$), and the second Distance matrix ($d_{i,j}$). (From pickup station $i$ to delivery station $j$). The required parameters to calculate the number of AGVs needed are:

• $L_{t}$: loading operation time
• $U_{t}$: unloading operation time
• $V$: vehicle speed
• $T$: planning horizon
• $e$: vehicle’s efficiency estimation
• $b$: percentage of the time the vehicle is blocked
• $c$: percentage of time the vehicle is idle
• $t_{b}$: time estimation the vehicle spends charging
• $f(T_{lt})$: empty travel time estimation as a function of the loaded travel time

$$ \text{number of vehicles (N)} = (required transfer capacity)/(planning horizon) $$

$$ N = ((\sum_{i} \sum_{j} f_{i,j} d_{i,j}/V) + f(T_{lt}) + (\sum_{i} \sum_{j} f_{i,j}(L_{t} + U_{t}))) / ( e(T - t_{b}) / 1 + b + c ) $$

The above function can either be applied directly or as a transfer function through the Monte-Carlo simulation to robust the represented parameters.

---

As a PIP the above problem can be written as follows:

• $f_{i,j,k}$: number of transfers required from node $i$ to node $j$ of flow type $k$
• $NF_{i,k}$: net flow at node $i$ of flow type $k$ per hour
• $CP_{i,j}$: number of transfers allowed on a path from node $i$ to node $j$ per hour
• $W_{i,j}$: maximum number of flow path lanes allowed between nodes $i$ and $j$
• $L_{i,j}$: lane installation cost from node $i$ and $j$
• $C$: cost per vehicle including software and hardware

\begin{align*} \ Min\ z = &\ \sum_i \sum_j \sum_k C(x_{i,j,k} f_{i,j,k})/V + \sum_i \sum_j L_{i,j} n_{i,j} \\ &\ \text{S.t:} \\ &\ \sum_j x_{i,j,k} - \sum_r x_{r,i,k} = NF_{i,k} \quad \forall i, \forall k \quad(1)\\ &\ n_{i,j} - \sum_k x_{i,j,k}/CP_{i,j} \geq 0 \quad \forall i,j \quad(2)\\ &\ n_{i,j} + n_{j,i} \leq W_{i,j} \quad \forall i,j \quad(3)\\ &\ x_{i,j,k} \ge 0 \in \mathbb{Z}^+, n_{i,j} \in \mathbb{B}\\ \end{align*}

The objective function minimizes the cost related to the number of vehicles needed and also the flow path network cost. The first constraint implies maintaining the flow in the system, the second constraint represents determining the number of flow path lanes required, and the third constraint controls the number of flow path lanes.

Also, for determining the optimal number of required workers, either simulation or mathematical modeling of rough cut capacity planning (RCCP) can be used.