Job Shop Scheduling

    {  Exmpl7.3-1_JobShopScheduling.mpl  }

    {  Applications of Optimization with Xpress-MP  }

    {  Chapter 7.3,  Job Shop Scheduling,  Size: 27x16,  Page 122 }


TITLE
   JobShopScheduling;

INDEX
   task := 1..8;
   task2 := task;

DATA
   Dur[task] := (45,20,12,10,17,10,34,28);
   Arc[task,task2] := [1,6,1,
                   4,2,1,
                   2,7,1,
                   8,3,1,
                   3,5,1];
   Disj[task,task2] := [1,2,1,
                        1,3,1,
                        2,3,1,
                        4,5,1,
                        6,7,1,
                        6,8,1,
                        7,8,1];
   BigM := SUM(task: Dur);

VARIABLE
   Start[task];
   Finish;
   y[task,task2] WHERE (Disj > 0);

MODEL
   MIN CompletionTime = Finish;

SUBJECT TO
   EndTime[task]: Start + Dur <= Finish;

   Precedence[task,task2] WHERE (Arc > 0):
    Start + Dur <= Start[task:=task2];

   Disjunction[task,task2>task] WHERE (Disj > 0):
    Start + Dur <= Start[task:=task2] + BigM * y;

   DisjunctionA[task,task2>task] WHERE (Disj > 0):
    Start[task:=task2] + Dur[task:=task2]
     <=
        Start + BigM * (1 - y);

BOUNDS
   Finish <= BigM;

BINARY
   y;