12
$\begingroup$

It is well known that job shop scheduling problems are notoriously hard from a computational point of view. Many papers exist for the makespan objective, and some report on min sum objectives (like minimize weighted completion time, minimize earliness/tardiness penalties etc).

My question: does anyone know whether makespan or min sum objectives are computationally more difficult when using MILP approaches?

Improve this question
$\endgroup$
12
  • $\begingroup$ Not directly answering your question, but I believe that such objectives are generally hard for polyhedral approaches such as MILP. My guess is that, since the resource constraints on JSPs are disjunctive in nature, it makes it somewhat unavoidable to use using big M variables in MILP formulations. Ever in literature, we often find CP approaches fare better than MILP approaches for obtaining the optimal solution of JSPs. $\endgroup$
    – batwing
    Jan 23 '20 at 18:06
  • $\begingroup$ Thanks, I usually use "configuration" based formulations (that are solved by branch-and-price), so I can avoid the big $M$. But you are right, of course, MILP is not very suited -- yet, this is exactly what I am interested in (I edit my post, thanks!). $\endgroup$
    – Marco Lübbecke
    Jan 23 '20 at 18:33
  • 1
    $\begingroup$ It seems that for the decision problem it can be shown that the total lateness objective is at least as general as the makespan objective: Assume we want to know if there exists a schedule with a makespan of at most M. When setting the due dates of all jobs to M, a schedule with a makespan of at most M exists if there is a schedule with a total lateness of zero. I don't see such a reduction for the other direction. $\endgroup$
    – SebastianK
    Jan 24 '20 at 15:23
  • 1
    $\begingroup$ Another indicator why min sum objectives are computationally more difficult is that the makespan depends only on the completion time of the latest job, whereas for min sum objectives the completion times of all jobs might have an influence. $\endgroup$
    – SebastianK
    Jan 24 '20 at 15:23
  • 1
    $\begingroup$ @SebastianK, would you like to turn your comments into an answer? this is the best we have so far... $\endgroup$
    – Marco Lübbecke
    Jan 29 '20 at 12:05
5
$\begingroup$

Some observations why min sum objectives are computationally more difficult than the makespan objective:

  • For the decision problem, it can be shown that the total lateness objective is at least as general as the makespan objective: Assume we want to know if there exists a schedule with a makespan of at most $M$. When setting the due dates of all jobs to $M$, a schedule with a makespan of at most $M$ exists if there is a schedule with a total lateness of zero. I don't see such a reduction for the other direction.
  • Another indicator why min sum objectives are computationally more difficult is that the makespan depends only on the completion time of the latest job, whereas for min sum objectives the completion times of all jobs might have an influence. This is related to the following. In heuristics, solutions of are often represented using conjunctive graphs. In order to efficiently evaluate moves, one can estimate the impact of a move to the objective function instead of actually executing the move. Estimating the impact of a move is less complicated for the makespan in comparison to other regular criteria (such as the min sum objectives).
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.