Job Shop Scheduling: what objectives are harder?

Question

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?

Answer 1

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).

Answer 2

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} $:

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.