2
$\begingroup$

I would like to know if anyone is aware of any Np-hard problems in scheduling or packing where there is total ordering between tasks or items to be packed together. The objective can be anything. For example there is cost that needs to be payed if some job finishes earlier than others.

Normally with total ordering problems like minimum makespan scheduling are easy to solve as there is no flexibility in this case and task orders are fixed.

$\endgroup$

1 Answer 1

3
$\begingroup$

Scheduling problems requiring a total ordering of the tasks are generally called sequencing problems in the OR literature. Car sequencing is one of the most famous ones. The car sequencing problem is known to be NP-hard. Check this paper for a short proof.

A point of interest with the car sequencing is that it can be modeled simply as an assignment (that is, matching) problem with a special, nonlinear objective function. Despite the constraint matrix being totally unimodular thanks to the matching structure, it is unlikely that an optimal solution will be an extreme point of the constraint polyhedron because the objective function is nonconvex.

Some sufficient conditions are identified in this paper to make the objective linear and then the problem polynomially solvable. These sufficient conditions can be exploited to search for a quality solution heuristically. Nevertheless, in the general case, the problem remains theoretically hard, and practically the linear relaxation of the problem is weak.

By reading the first mentioned, you will notice that the hardness is obtained from a polynomial reduction from the TSP. Total ordering problems can be viewed as sequencing problems, and vice versa. They all can be modeled as assignment (that is, matching) problems with nonlinear objective functions, and most of them can be proved NP-hard.

$\endgroup$
3
  • $\begingroup$ Interesting ! In the second paragraph, do you mean "because the objective function is NON convex" ? $\endgroup$
    – Kuifje
    Jun 23, 2022 at 7:23
  • $\begingroup$ @Kuifje Thanks a lot for pointing out this tragic typo :-) Now, the sentence is meaningful. $\endgroup$
    – Hexaly
    Jun 30, 2022 at 20:56
  • $\begingroup$ I read the article there. You want to sequence some cars where there is no ordering between them. I would like to know if there exists an example where you already know the total order who is first, second and so on. For example Consider a problem where the total task ordering is known. However you can only decide when to start a task and pay a cost everytime a task finishes before one of its predecessors. $\endgroup$ Jun 30, 2022 at 21:17

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.