Jobshop Problem (jobshop1)

Run LPL Code  ,  PDF Document

Problem

The problem is explained in jobshop. Several MIP formulations are explained in my book Case Studies II.

Implement this problem as a permutation problem.

Modeling Steps

Given a set of jobs i I and a set of machines k K. The processing time of each job on each machine is given as pti,k, and the order of the job i on a machine k is ok,i. An (trivial) upper bound for the overall processing time is mS = i,kpti,k. Let n be the cardinality of the set I and m be the cardinality of the set K.

  1. The two variables are the starting time of a job on a machine: si,k and the permutation of the jobs on each machine: xk,i.

  2. The finishing time Fi,k of a job i on machine k is given as:

    Fi,k = si,k + pti,k   forall k ∈ K, i ∈ I
  3. The precedence constraint says that the starting time of a job i must be at least as large as the finishing time on the previous machine :

    si,oi,k ≥ Fi,oi,k- 1  k ∈ K, i ∈ I,k > 1
  4. The disjoint constraint says that on each machine k all the starting time of a job at position xk,i+1 must be larger or equal the finishing time of a job at position xk,i :

      ∧
      (sxk,i+1,k ≥ Fxk,i,k)   forall k ∈ K
i∈1..n-1
  5. The goal is to minimize the makespan:

    min  max  Fi,o
      i∈I     i,m

Listing 1: The Main Model implemented in LPL [2]
model jobshop "Jobshop Problem"; 
  set i  "a set of jobs"; 
      k  "a set of machines"; 
  parameter processingTime{i,k}; mOrder{i,k}; maxStart; 
  integer variable start{i,k} [0..maxStart]; 
  alldiff variable x{k,i} [1..#i]; 
  expression finish{i,k}: start + processingTime; 
  constraint Prec{i,k|k>1}: 
     start[i,mOrder[i,k]] >= finish[i,mOrder[i,k-1]]; 
  constraint Disj{k}: 
     and{i in 1..#i-1} (start[x[k,i+1],k] >= finish[x[k,i],k]); 
  minimize makespan: max{i} finish[i,mOrder[i,#k]]; 
end

Solution

The data model is


Listing 2: The Data Model
  model data; 
    string parameter File:='js-instances/la40.txt';   //opt=1222 
    --string parameter File:='js-instances/ft20.txt'; //opt=1165 
    parameter nJobs; nMach; 
    parameter t1{i,k}; 
    Read(File&',%1;1',nJobs,nMach); 
    i:=1..nJobs; 
    k:=1..nMach; 
    Read{i}('%1:Times',{k} t1); 
    Read{i}('%1:Machines',{k} mOrder); 
    {i,k} (processingTime[i,mOrder]:=t1); 
    maxStart:=sum{i,k} processingTime; 
  end

The LocalSolver returns a solution of 1284 (the optimum is 1222) after 10secs for the “la40.txt” instance. The Gantt diagram generated by the following output model is given in Figure 1.


Listing 3: The Output Model
  model output; 
    Writep(makespan); 
    Draw.Scale(1,40); 
    {i,k} Draw.Rect(i&'',start,k,processingTime,1,i+2,0); 
  end;

PIC

Figure 1: Near Optimal Solution of the instance “la40.txt”

References

[1]   MatMod. Homepage for Learning Mathematical Modeling :  https://matmod.ch.

[2]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.