None Notebook

This notebook contains material from CBE30338; content is available on Github.

< 9.2 State-Task Networks | Contents | Tag Index | A.0 Additional Python >

Open in Colab

Download

9.3 Machine Bottleneck

This notebook demonstrates the formulation and solution of the a machine bottleneck problem using Pyomo/GLPK. The task is to schedule a set of jobs on a single machine given the release time, duration, and due time for each job. Date for the example problem is from Christelle Gueret, Christian Prins, Marc Sevaux, "Applications of Optimization with Xpress-MP," Chapter 5, Dash Optimization, 2000.

9.3.1 Example

The problem is to schedule a sequence of jobs for a single machine. The data consists of a list of jobs. For each job, the data provides the time at which the job is released to the for machine processing, the expected duration of the job, and the due date. The problem is to sequence the jobs on the machine to meet the due dates, or show that no such sequence is possible.

The following data was presented in the Machine Bottleneck Example from Christelle Gueret, Christian Prins, Marc Sevaux, "Applications of Optimization with Xpress-MP," Chapter 5, Dash Optimization, 2000.

9.3.2 Modeling

9.3.2.1 Data

The data for this problem consists of a list of jobs. Each job is tagged with a unique ID along with numerical data giving the time at which the job will be released for machine processing, the expected duration, and the time at which it is due.

Symbol Description
$\text{ID}_{j}$ Unique ID for task $j$
$\text{due}_{j}$ Due time for task $j$
$\text{duration}_{j}$ Duration of task $j$
$\text{release}_{j}$ Time task $j$ becomes available for processing

9.3.2.2 Decision Variables

For a single machine, the essential decision variable is the start time at which the job begins processing.

Symbol Description
$\text{start}_{j}$ Start of task $j$
$\text{makespan}$ Time to complete all jobs.
$\text{pastdue}_{j}$ Time by which task $j$ is past due
$\text{early}_{j}$ Time by which task $j$ is finished early

A job cannot start until it is released for processing \begin{align*} \text{start}_{j} & \geq \text{release}_{j}\\ \end{align*}

Once released for processing, we assume the processing continues until the job is finished. The finish time is compared to the due time, and the result stored in either the early or pastdue decision variables. These decision variables are needed to handle cases where it might not be possible to complete all jobs by the time they are due.

\begin{align*} \text{start}_{j} + \text{duration}_{j} + \text{early}_{j} & = \text{due}_{j} + \text{pastdue}_{j}\\ \text{early}_{j} & \geq 0 \\ \text{pastdue}_{j} & \geq 0 \end{align*}

Finally, we include a single decision variable measuring the overall makespan for all jobs. \begin{align*} \text{start}_{j} +\text{duration}_{j} \leq \text{makespan} \end{align*}

The final set of constraints requires that, for any given pair of jobs $j$ and $k$, that either $j$ starts before $k$ finishes, or $k$ finishes before $j$ starts. The boolean variable $y_{jk} = 1$ indicates $j$ finishes before $k$ starts, and is 0 for the opposing case. Note that we only need to consider cases $j > k$

\begin{align*} \text{start}_{i}+\text{duration}_{i} & \leq \text{start}_{j}+My_{i,j}\\ \text{start}_{j}+\text{duration}_{j} & \leq \text{start}_{i}+M(1-y_{i,j}) \end{align*}

where $M$ is a sufficiently large enough to assure the relaxed constraint is satisfied for all plausible values of the decision variables.

9.3.3 Pyomo Model

9.3.4 Visualization

9.3.5 Multiple Machines

The case of multiple machines requires a modest extension of model described above. Given a set $M$ of machines, we introduce an additional decision binary variable $z_{j,m}$ indicating if job $j$ has been assigned to machine $m$. The additional constraints

\begin{align*} \sum_{m\in M}z_{j,m} = 1 \end{align*}

require each job to be assigned to exactly one machine for processing.

If both jobs $j$ and $k$ have been assigned to machine $m$, then the disjunctive ordering constraints must apply. This logic is equivalent to the following constraints for $j < k$.

\begin{align*} \text{start}_{i}+\text{duration}_{i} & \leq \text{start}_{j}+My_{i,j} + M(1-z_{j,m}) + M(1-z_{k,m})\\ \text{start}_{j}+\text{duration}_{j} & \leq \text{start}_{i}+M(1-y_{i,j} + M(1-z_{j,m}) + M(1-z_{k,m})) \end{align*}

< 9.2 State-Task Networks | Contents | Tag Index | A.0 Additional Python >

Open in Colab

Download