NP-Hard Problems

This chapter establishes the NP-hardiness of a number of scheduling problems. To prove that a given Problem B is NP-hard, we use the following scheme. The decision Problem B’ corresponding to Problem B is formulated, and a Problem A is shown to be polynomially reducible to B’ where A is one of the standard problems, i.e., a decision problem known to be NP-complete. If Problem A is NP-complete in the strong sense, then sometimes it is shown to be pseudopolynomially reducible to Problem B’.