The Job Scheduling Problem

Prerequisites

The mathematical Model

Sets:
\begin{array}{l} J = \text{Set of }j\text{ Jobs}\newline S = \text{Set of }s\text{ Setup times}\newline R = \text{Set of }r\text{ Ranks}\newline T = \text{Set of }t\text{ Tasks}\newline T_m^M = \text{Set of }t_m\text{ Tasks supported by Machine }m\newline M = \text{Set of }m\text{ Machines} \end{array}

Parameters:
$$d_t = \text{duration of task }t$$ $$due_j = \text{due time of job }j$$ $$bigM = \sum\limits_{t\in T} d_t$$ $$c_m = \text{cost of using machine }m$$ $$st_j = \text{setup time of job }j\text{ is 0 if consecutive tasks are performed on the same machine}$$

Variables:
$$s_{t,m,r} = \text{start time of task }t\text{ with rank }r\text{ on machine }m$$ $$y_{t,m,r} = \begin{cases} 1, \text{ if task }t\text{ is assigned to machine }m \text{ with rank }r \newline 0, \text{ else} \end{cases}$$ $$d_j = \text{delay of job }j$$ $$l_{end} = \text{latest end time for completing all jobs and their tasks}$$

Objective:
$$\text{min } l_{end} + \sum\limits_{m \in M} \sum\limits_{r \in R} \sum\limits_{t \in T} ( (y_{t,m,r} c_m * 0.001) + (s_{t,m,r} * 0.01)$$

Restrictions:
\begin{array}{l} \sum\limits_{m\in M: t\in T_m^M} \sum\limits_{r\in R} y_{t,m,r} = 1 & \forall t \in T & \text{(each task must be done on one machine)}\newline \sum\limits_{t\in T_m^M} y_{t,m,r} \le 1 & \forall m \in M, r\in R & \text{(each machine has one task on every rank)}\newline \sum\limits_{m \in M: t \in T_m^M} s_{t,m,r} \le \sum\limits_{m \in M: t \in T_m^M} s_{t+1,m,r+1} + d_{t} & \forall j \in J, t \in T & \text{(tasks on the same machine observe timely order)}\newline s_{t,m,r} \le bigM y_{t,m,r} & \forall t \in T, m \in M: t \in T_m^M, r \in R & \text{(setting of start time leads to task assignment)}\newline s_{t+1,m,r} + y_{t+1,m,r-1} t_d + st_j \le s_{t,m,r} + (1 - y_{t,m,r}) bigM & \forall t \in T, m \in M: t \in T_m^M, r \in R & \text{(preserve order of the tasks / ranks)}\newline s_{t,m,r} + d_t - due_j \le d_j & \forall j \in J, m \in M, r \in R & \text{(calculate delays)}\newline s_{t,m,r} + d_t \le l_{end} & \forall r \in R, t \in T, m \in M: t \in T_m^M & \text{(find latest end)}\newline \sum\limits_{m\in M: t\in T_m^M} y_{t,m,r} = \sum\limits_{m\in M: t\in T_m^M} y_{t,m,r-1} & \forall r \in R, m \in M & \text{(tuning - no free ranks)} \end{array}

The Job Scheduling Problem