A simple single machine scheduling model with sequence dependent setup times is a good example where MIP solvers are not very good yet.
The simplest formulation for the 15 job problem we show below, is probably where we use the following definition:
x(i,j) = 1 if job i is scheduled before job j
Obviously we don’t need the diagonal: x(i,i). Also if we know that x(i,j) = 1-x(j,i), so we don’t need both the lower- and upper-triangular part. A model now can look like:
We can find the optimal solution of 90 in about an hour or so (running on one thread):
However, as we can see we are far from proving this is indeed the optimal solution: the best bound has not moved at all.
- Constraint calcstart3 can be written as a bound. Of course these days, a MIP solver will do that for you in the pre-solve phase.
- The initial solution was constructed by ordering the jobs by due date.
- The Gantt chart for the machine can look like:
Here the late jobs are colored red.
- The model minimizes sum of
latenesstardiness. Additional objectives could be number of late jobs and total makespan.
- More difficult to model is this: scheduled downtime. If jobs can not be interrupted, this causes holes (idle time) in the schedule.
- A different, slightly more complicated formulation would result from:
x(i,j) = 1 if job i is scheduled immediately before job j
- IBM Ilog’s CP solver using OPL can model sequence dependent setup times directly (see: http://publib.boulder.ibm.com/infocenter/cosinfoc/v12r3/topic/ilog.odms.cpo.help/Content/Optimization/Documentation/Optimization_Studio/_pubskel/usrcpoptimizer2793.html).
- Many papers suggest a meta-heuristic (genetic algorithm etc.) to solve this.
- Of course a MIP model can still help to define the problem correctly and to solve small instances to optimality.
- Paper for data file is: “SCHEDULING IN A SEQUENCE DEPENDENT SETUP ENVIRONMENT WITH GENETIC SEARCH”, Paul A. Rubin, Gary L. Ragatz, Computers & Operations Research, 22, no 1, jan 1995, pp 85-99.
- The paper notes that according to a survey, 70% of scheduling problems may be subject to sequence dependent setup times (this number looks a little bit high to me).
- A generalization of setup times that are sequence dependent is to consider them history dependent, i.e. dependent on a number of preceding jobs. See for instance http://onlinelibrary.wiley.com/doi/10.1002/nav.21472/abstract.
PS. After the comment from Paul Rubin, I updated the big-M calculation. This reduces the size of M from 3819 to 1775. Although this is a better formulation, an example run with Cplex, 1 thread actually shows somewhat poorer performance of the new M. In the picture below we have M1 as the old M=3819 and M2 the results for M=1775.
Sometimes with a MIP we see that a better formulation can have worse performance on certain instances.
PS2. See comment below. Officially we have tardiness = max(0,lateness). I hardly use the term tardiness: “normal people” tend to use the more intuitive earliness and lateness (both nonnegative).