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.