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
0 otherwise
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:
$ontext variables |
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.
Notes:
- 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
0 otherwise - 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).
I get to 94 in about 3 minutes with Gurobi (on 8 threads). I removed the makespan and emakespan lines which are not used in the obj function.
ReplyDeleteI do not understand your model fully so this may not make sense, but I also used .prior based on duedate:
m1.prioropt = 1 ;
x.prior(i,j)=duedate(i) ;
I haven't let the program run for an hour so your solution might still be better.
In general I don't see much advantage in using priorities with the current best MIP solvers (i.e. they beat me). But of course there may be exceptions.
ReplyDeleteGurobi has very good heuristics, and they often find very good solutions very quickly, as you demonstrated.
I assume the bestbound is still 0?
A small terminology correction: the model minimizes "tardiness" rather than "lateness". According to my coauthor, scheduling researchers treat an early completion as negative lateness but zero tardiness.
ReplyDeleteI'm not sure I'm reading the GAMS code correctly, but it appears that your computation of M includes the sum of all possible setup times. If so, I think you can reduce that to the sum of the maximum setup into each job, and get a tighter M (which should help bounding).
Yes, I need to fix that M! Thanks.
ReplyDeleteSorry for being sloppy with terminology. I am used to assume whatever nomenclature is used by the client, and this may be very different from what is accepted in the research literature. At one conference I remember a whole discussion about what constitutes planning vs. scheduling. However when doing consultancy, you just use the words the client is familiar with and what they already use in their communication. As a result my terms are often used in a "flexible" way (i.e. imprecise or may be even wrong, strictly speaking).
The terminology is understandable. That sort of thing will happen when academic circles intersect with the real world (which, fortunately for us academics, is a rare occurrence).
ReplyDeleteI don't think that fixing M will push the lower bound much, but I'd be curious whether it had a noticeable effect. My experience was that bounds for this problem are pretty loose as a rule (barring something clever in either the model or the algorithm).