Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
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.
