\n", " The task is to schedule a set of jobs on a single machine given\n", " the release time, duration, and due time for each job.\n", "
\n" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "MathProg Model" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The model uses a 'Big M' implementation of disjunctive constraints to avoid conflicts for a single machine. Big M should be larger than the longest time horizon for the completion of all jobs. A bound on the longest horizon is the maximum release plus the sum of durations for all jobs." ] }, { "cell_type": "code", "collapsed": false, "input": [ "%%writefile Bottleneck.mod\n", "\n", "/* Machine Bottleneck Example */\n", "\n", "set JOBS;\n", "\n", "param rel{JOBS} default 0; # Time a job is available to the machine\n", "param dur{JOBS}; # Job duration\n", "param due{JOBS}; # Job due time\n", "\n", "/* Data Checks */\n", "check {k in JOBS}: rel[k] + dur[k] <= due[k];\n", "\n", "/* The model uses a 'Big M' implementation of disjunctive constraints\n", "to avoid conflicts for a single machine. Big M should be larger than\n", "the longest time horizon for the completion of all jobs. A bound\n", "on the longest horizon is the maximum release plus the sum of\n", "durations for all jobs. */\n", "\n", "param BigM := (max {k in JOBS} rel[k] ) + sum{k in JOBS} dur[k];\n", "\n", "/* Decision variables are the start times for each job, and a\n", "disjunctive variable y[j,k] which is 1 if job j precedes job k on\n", "the machine. */\n", "\n", "var start{JOBS} >= 0;\n", "var pastdue{JOBS} >= 0;\n", "var y{JOBS,JOBS} binary;\n", "\n", "/* There are many possible objectives, including total pastdue, maximum\n", "pastdue (i.e., tardiness), number of jobs pastdue. */\n", "\n", "minimize OBJ : sum {k in JOBS} pastdue[k];\n", "\n", "/* Order Constraints */\n", "\n", "s.t. START {k in JOBS}: start[k] >= rel[k];\n", "s.t. FINIS {k in JOBS}: start[k] + dur[k] <= due[k] + pastdue[k];\n", "\n", "/* Machine Conflict Constraints */\n", "\n", "s.t. DA {j in JOBS, k in JOBS : j < k}:\n", " start[j] + dur[j] <= start[k] + BigM*(1-y[j,k]);\n", "s.t. DB {j in JOBS, k in JOBS : j < k}:\n", " start[k] + dur[k] <= start[j] + BigM*y[j,k];\n", "\n", "solve;\n", "\n", "/* Create Tables */\n", "\n", "table tout {k in JOBS} OUT \"CSV\" \"Schedule.csv\" \"table\":\n", " k~Job, rel[k]~Release, start[k]~Start, start[k]+dur[k]~Finish, due[k]~Due;\n", "\n", "/* Print Report */\n", "\n", "printf \" Task Rel Dur Due Start Finish Pastdue\\n\";\n", "printf {k in JOBS} \"%5s %7g %7g %7g %7g %7g %7g\\n\",\n", " k,rel[k],dur[k],due[k],start[k],start[k]+dur[k],pastdue[k];\n", "\n", "end;" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Overwriting Bottleneck.mod\n" ] } ], "prompt_number": 2 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Machine Bottleneck Example from Christelle Gueret, Christian Prins,\n", "Marc Sevaux, \"Applications of Optimization with Xpress-MP,\" Chapter 5,\n", "Dash Optimization, 2000." ] }, { "cell_type": "code", "collapsed": false, "input": [ "%%script glpsol -m Bottleneck.mod -d /dev/stdin -y results.txt --out output\n", "\n", "param: JOBS : rel dur due :=\n", " A 2 5 10\n", " B 5 6 21\n", " C 4 8 15\n", " D 0 4 10\n", " E 0 2 5\n", " F 8 3 15\n", " G 9 2 22 ;\n", "\n", "end;" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 6 }, { "cell_type": "code", "collapsed": false, "input": [ "print(open('results.txt').read())" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ " Task Rel Dur Due Start Finish Pastdue\n", " A 2 5 10 6 11 1\n", " B 5 6 21 14 20 0\n", " C 4 8 15 22 30 15\n", " D 0 4 10 2 6 0\n", " E 0 2 5 0 2 0\n", " F 8 3 15 11 14 0\n", " G 9 2 22 20 22 0\n", "\n" ] } ], "prompt_number": 7 }, { "cell_type": "code", "collapsed": false, "input": [ "import pandas\n", "\n", "pandas.read_csv(\"Schedule.csv\")" ], "language": "python", "metadata": {}, "outputs": [ { "html": [ "\n", " | Job | \n", "Release | \n", "Start | \n", "Finish | \n", "Due | \n", "
---|---|---|---|---|---|
0 | \n", "A | \n", "2 | \n", "6 | \n", "11 | \n", "10 | \n", "
1 | \n", "B | \n", "5 | \n", "14 | \n", "20 | \n", "21 | \n", "
2 | \n", "C | \n", "4 | \n", "22 | \n", "30 | \n", "15 | \n", "
3 | \n", "D | \n", "0 | \n", "2 | \n", "6 | \n", "10 | \n", "
4 | \n", "E | \n", "0 | \n", "0 | \n", "2 | \n", "5 | \n", "
5 | \n", "F | \n", "8 | \n", "11 | \n", "14 | \n", "15 | \n", "
6 | \n", "G | \n", "9 | \n", "20 | \n", "22 | \n", "22 | \n", "
7 rows \u00d7 5 columns
\n", "