## Sunday, April 13, 2014

### Playing with job shop problem ft10 (1)

As discussed in http://yetanothermathprogrammingconsultant.blogspot.com/2009/09/job-shop-scheduling.html a MIP solver like Gurobi can solve this difficult problem quite easily.

Here we show the performance with 1 and 4 threads:

The big advantage of using a MIP solver is that any time (after finding the first integer solution) we have both a best found (upper bound) and best possible or best bound (lower bound) available. This not only gives us a proven optimal solution at the end but a sense of the quality of the solution during the solution process. We can interrupt before the end using this information (e.g. by stopping on a small gap).

There are a few interesting observations:

• The 4 thread integer solutions are not uniformly better than their 1 thread counterparts: quite often the red line (top part of the graph) is below the blue line
• But in the end 4 threads wins big
• Most progress is achieved in the beginning w.r.t. to finding good integer solutions. So when in a hurry we can stop early.
• This also means that building a heuristic that finds a good solution quickly is of limited value: the MIP solver finds good solutions quickly on its own. I.e. such a heuristic helps where the MIP solver does not need much help.
• The plot was produced with R and ggplot. I think it looks quite nice.
##### GAMS model
 \$ontext     Job Shop Scheduling     Manne formulation     Alan Manne, "On the job-shop scheduling problem", Operations Research     vol 8, no 2 March-April 1960.     Data set ft10 is from:     H. Fisher, G. L. Thompson, Probabilistic learning combinations of     local job-shop scheduling rules, in: J. F. Muth, G. L. Thompson (eds.),     Industrial Scheduling, Prentice Hall, Englewood Cliffs, N.J., 1963.  job1:   0 29 ; 1 78 ; 2  9 ; 3 36 ; 4 49 ; 5 11 ; 6 62 ; 7 56 ; 8 44 ; 9 21  job2:   0 43 ; 2 90 ; 4 75 ; 9 11 ; 3 69 ; 1 28 ; 6 46 ; 5 46 ; 7 72 ; 8 30  job3:   1 91 ; 0 85 ; 3 39 ; 2 74 ; 8 90 ; 5 10 ; 7 12 ; 6 89 ; 9 45 ; 4 33  job4:   1 81 ; 2 95 ; 0 71 ; 4 99 ; 6  9 ; 8 52 ; 7 85 ; 3 98 ; 9 22 ; 5 43  job5:   2 14 ; 0  6 ; 1 22 ; 5 61 ; 3 26 ; 4 69 ; 8 21 ; 7 49 ; 9 72 ; 6 53  job6:   2 84 ; 1  2 ; 5 52 ; 3 95 ; 8 48 ; 9 72 ; 0 47 ; 6 65 ; 4  6 ; 7 25  job7:   1 46 ; 0 37 ; 3 61 ; 2 13 ; 6 32 ; 5 21 ; 9 32 ; 8 89 ; 7 30 ; 4 55  job8:   2 31 ; 0 86 ; 1 46 ; 5 74 ; 4 32 ; 6 88 ; 8 19 ; 9 48 ; 7 36 ; 3 79  job9:   0 76 ; 1 69 ; 3 76 ; 5 51 ; 2 85 ; 9 11 ; 6 40 ; 7 89 ; 4 26 ; 8 74  job10:  1 85 ; 0 13 ; 2 61 ; 6  7 ; 8 64 ; 9 76 ; 5 47 ; 3 52 ; 4 90 ; 7 45   Description: jobs need to follow a sequence of operations. The numbers indicate   machine number and processing time.   This is a well-known benchmark problem and the optimal obj=930. \$offtext set   j 'tasks' / job1*job10/   t 'stages'  /t1*t10/ ; table proctime(j,t) 'processing times for each stage'         t1    t2    t3    t4    t5    t6    t7    t8    t9   t10 job1    29    78     9    36    49    11    62    56    44   21 job2    43    90    75    11    69    28    46    46    72   30 job3    91    85    39    74    90    10    12    89    45   33 job4    81    95    71    99     9    52    85    98    22   43 job5    14     6    22    61    26    69    21    49    72   53 job6    84     2    52    95    48    72    47    65     6   25 job7    46    37    61    13    32    21    32    89    30   55 job8    31    86    46    74    32    88    19    48    36   79 job9    76    69    76    51    85    11    40    89    26   74 job10   85    13    61     7    64    76    47    52    90   45 ; table machine(j,t) 'machine numbers for each stage (zero based)'         t1  t2  t3  t4  t5  t6  t7  t8  t9  t10 job1    0    1   2   3   4   5   6   7   8   9 job2    0    2   4   9   3   1   6   5   7   8 job3    1    0   3   2   8   5   7   6   9   4 job4    1    2   0   4   6   8   7   3   9   5 job5    2    0   1   5   3   4   8   7   9   6 job6    2    1   5   3   8   9   0   6   4   7 job7    1    0   3   2   6   5   9   8   7   4 job8    2    0   1   5   4   6   8   9   7   3 job9    0    1   3   5   2   9   6   7   4   8 job10   1    0   2   6   8   9   5   3   4   7 ; alias (j,j2),(t,t2); set ovl(j,t,j2,t2) 'this subset of (j,t),(j2,t2) needs to be checked against overlap'; ovl(j,t,j2,t2)\$(ord(j)
##### R Code to create the plot

 `library(ggplot2)   setwd("C:/projects/tmp")# read csv filesd1<-read.csv("1thread.csv")d4<-read.csv("4thread.csv")# stack them into a single data framed<-rbind(d1,d4)# add a Threads column indicating the data setd\$Threads <- c(rep("1 thread",nrow(d1)),rep("4 threads",nrow(d4)))# convert factor to double ("na" will be converted to NA)d\$bestFound <- as.double(as.character(d\$bestFound))# actual plottingggplot(data=d)+geom_line(aes(group=Threads,x=seconds,y=bestBound,color=Threads))+geom_line(aes(group=Threads,x=seconds,y=bestFound,color=Threads))+ggtitle("Gurobi laptop performance on ft10.gms")+xlab("Time (seconds)")+ylab("Best Found (top), Best Bound (bottom)")` Created by Pretty R at inside-R.org

#### 1 comment:

1. Hi Erwin,
I am looking for an algorithm to deal with Job-shop scheduling as a constraint programming. I can't use commercial solvers.
Any chance you might have faced with this issue ?
I need to solve the large scale problem in a quick time (find a feasible solution no matter it is optimal or not)