{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "*This notebook contains course material from [CBE40455](https://jckantor.github.io/CBE40455) by\n", "Jeffrey Kantor (jeff at nd.edu); the content is available [on Github](https://github.com/jckantor/CBE40455.git).\n", "The text is released under the [CC-BY-NC-ND-4.0 license](https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode),\n", "and code is released under the [MIT license](https://opensource.org/licenses/MIT).*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "< [Critical Path Method](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/04.01-Critical-Path-Method.ipynb) | [Contents](toc.ipynb) | [Job Shop Scheduling](http://nbviewer.jupyter.org/github/jckantor/CBE40455/blob/master/notebooks/04.03-Job-Shop-Scheduling.ipynb) >
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Machine Bottleneck\n", "\n", "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example\n", "\n", "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.\n", "\n", "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. " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", " | A | \n", "B | \n", "C | \n", "D | \n", "E | \n", "F | \n", "G | \n", "
---|---|---|---|---|---|---|---|
due | \n", "10 | \n", "21 | \n", "15 | \n", "10 | \n", "5 | \n", "15 | \n", "22 | \n", "
duration | \n", "5 | \n", "6 | \n", "8 | \n", "4 | \n", "2 | \n", "3 | \n", "2 | \n", "
release | \n", "2 | \n", "5 | \n", "4 | \n", "0 | \n", "0 | \n", "8 | \n", "9 | \n", "
\n", " | A | \n", "B | \n", "C | \n", "D | \n", "E | \n", "F | \n", "G | \n", "Total | \n", "
---|---|---|---|---|---|---|---|---|
due | \n", "10.0 | \n", "21.0 | \n", "15.0 | \n", "10.0 | \n", "5.0 | \n", "15.0 | \n", "22.0 | \n", "\n", " |
duration | \n", "5.0 | \n", "6.0 | \n", "8.0 | \n", "4.0 | \n", "2.0 | \n", "3.0 | \n", "2.0 | \n", "30 | \n", "
early | \n", "0.0 | \n", "1.0 | \n", "0.0 | \n", "4.0 | \n", "3.0 | \n", "1.0 | \n", "0.0 | \n", "9 | \n", "
finish | \n", "11.0 | \n", "20.0 | \n", "30.0 | \n", "6.0 | \n", "2.0 | \n", "14.0 | \n", "22.0 | \n", "\n", " |
ispastdue | \n", "1.0 | \n", "0.0 | \n", "1.0 | \n", "0.0 | \n", "0.0 | \n", "0.0 | \n", "0.0 | \n", "2 | \n", "
pastdue | \n", "1.0 | \n", "0.0 | \n", "15.0 | \n", "0.0 | \n", "0.0 | \n", "0.0 | \n", "0.0 | \n", "16 | \n", "
release | \n", "2.0 | \n", "5.0 | \n", "4.0 | \n", "0.0 | \n", "0.0 | \n", "8.0 | \n", "9.0 | \n", "\n", " |
start | \n", "6.0 | \n", "14.0 | \n", "22.0 | \n", "2.0 | \n", "0.0 | \n", "11.0 | \n", "20.0 | \n", "\n", " |
" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" } }, "nbformat": 4, "nbformat_minor": 2 }