37 lines
1.9 KiB
Markdown
37 lines
1.9 KiB
Markdown
## scheduling problem defined by:
|
|
1. $m$ specialized machines
|
|
2. tasks $\tau$ of the form $(e, i)$ with $t \in \mathbb{N}$ the execution time and $i \in \{1,2,\dots,m\}$ the machine the task has to run on
|
|
3. $n$ jobs $T_k$ with $\forall T_k:$ linear order of tasks, with $k \in \{1,2,\dots,n\}$
|
|
4. Additionally, a multiset $\Omega$ of arbitrary but fixed size that contains wait states $\omega := (1, i)$ with $i \in \{1,2,\dots,m\}$ the blocked machine.
|
|
|
|
The goal is to find the fastest feasible schedule $\sigma_{min}$.
|
|
|
|
## evaluative function
|
|
- minimize the execution time of $\sigma$
|
|
- upper bound: largest processing time first
|
|
- lower bound: max sum of execution times on one machine
|
|
|
|
## solutions
|
|
- list of tuples $(t, \tau)$ with $t \in \mathbb{N}$ the scheduled begin of $\tau$
|
|
|
|
## operations
|
|
- $\operatorname{ins}(\omega, t)$: block a machine at time $t$ for $w$ time steps.
|
|
- $\operatorname{xchg}(\tau_1,\tau_2)$: exchange the position of two tasks.
|
|
|
|
Both operations require that the start times are recomputed.
|
|
|
|
## neighbourhood of solution
|
|
|
|
- $\operatorname{neighbours}(\sigma) = \{x \in \Sigma | \delta(\sigma, x) \leq n\}$ with $\Sigma$ the set of all feasible schedules.
|
|
- $\delta$: $\delta ( \sigma )=0$, $\delta ( \operatorname{op}(x)) = \delta (x) + 1$ (ass. ins has the same penalty xchg has), $x$ either op($y$) or $\sigma$
|
|
|
|
## constraints
|
|
- only schedule new $\tau$ if another $\tau$ is finished
|
|
- only schedule $\tau \in T_k$ that has no unscheduled predecessor in $T_k$
|
|
- only one task on a machine any given time
|
|
|
|
## implementation in Python
|
|
- translate problem into list of jobs, jobs into lists of tasks, ie problem = [$T_0, T_1,\dots,T_{k-1}$], $T_i$ = [$\tau_1,\tau_2,\dots$]
|
|
- address tasks based on their indices, ie [0][1] is the second task of the first job.
|
|
- compute only one possible next solution, rate, drop/accept. $\delta$ is computed iteratively during generation
|