Wednesday, September 12, 2012

Preemptive jobs

When doing some background research on a scheduling problem I was looking at the paper The model formulation is:




The first minor issue is notational. I suspect si,lm should really be variable with three indices: si,l,m. I am unsure why the second and third indices are concatenated. In equations (2)-(5) we see that also a 2 index version is used.

The second problem I see is equation (6). I suspect this should read:


Equation (7) does not look correct to me either. Could be they really mean:


Equation (10) introduces suddenly a xi,j,m which probably just should read xi,m. This equation is nonlinear as presented but probably can be linearized easily. In general the capacity constraint for renewable resources is indexed by t, but here in eq (10) the authors propose to sum over t. This cannot be correct either.

To make things worse, the presented solution is of the small sample problem is incorrect. They show:


When we look at s(2,v,2) we see:

job part mode start time
2 1 2 0
2 2 2 0
2 3 2 1

I.e. part 1 and 2 are executed in the same time slot.

This is a small model but these typos do not make it very easy to reproduce results.

Update: similar mistakes are found in an earlier paper: So these are not just typos. I suspect the model was done in Excel, for the following reasons:

  • Excel models are always very messy
  • they are often difficult to translate one-to-one to a well formulated mathematical model
  • Excel handles non-linear models
  • Excel has a 2d grid, which may explain there preference for 2d variables.

When developing a non-trivial model it is often a good idea to use a modeling language such as AMPL or GAMS, as this in sense will check your formulation. The above mistakes would probably not have been made in that case. Excel provides very limited support for more complex models, and from experience I can say Excel models are difficult to understand and debug. This may well be another piece of support for this.

Anyway, this is a good example how not to publish models. Of course in journals with better reviewers a paper like this would probably not have been accepted. The presented model equations and results are incorrect.

My solution looks like:


The model has no penalty on preemption, so there is no incentive to make jobs as much as possible uninterrupted.

No comments:

Post a Comment