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$
13
  • $\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
    Commented Jan 23, 2020 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
    Commented Jan 23, 2020 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
    Commented Jan 24, 2020 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
    Commented Jan 24, 2020 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
    Commented Jan 29, 2020 at 12:05

2 Answers 2

Reset to default
6
$\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$
2
$\begingroup$

In addition to the above answer, the following might be worthwhile too.

Often, an algorithm for one scheduling problem can be applied to another scheduling problem as well. For example, $ 1|| \sum c_{j} $ is a special case of $ 1|| \sum w_{j}c_{j} $ and a procedure for this can also be used for the first one. In complexity terms, it is said that $ 1|| \sum c_{j} $ reduces to $ 1|| \sum w_{j}c_{j} $. Based on this concept a chain of reductions can be established. For example:

$$ (1|| \sum c_{j}) \rightarrow (1|| \sum w_{j}c_{j}) \rightarrow (P_{m} || \sum w_{j}c_{j}) \rightarrow (Q_{m} |prec| \sum w_{j}c_{j}))$$

As an example of hard and easy problem, $ 1 || C_{max} $, $ P_{2} || C_{max} $, $ F_{2} || C_{max} $, $ J_{m} || C_{max} $, and $ FF_{c} || C_{max} $:

enter image description here

Of course, there are also many problems that are not comparable with one another. For example, $ P_{m} || \sum w_{j}T_{j}$ is not comparable to $ J_{m}|| C_{max} $.

A considerable effort has been made to establish a problem hierarchy describing the relationships between the hundreds of scheduling problems. In the comparisons between the complexities of the different scheduling problems, it is of interest to know how a change in a single element in the classification of a problem affects its complexity. The following graph helps determine the complexity hierarchy of deterministic scheduling problems based on the different objective functions.

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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