Sequencing and scheduling: Algorithms and complexity

Sequencing and scheduling'as a research area is motivated by questions that We review complexity results and'optimization and approximation algorithms The chapter is organized as follows. There are several survey papers that complement the present chapter. In this section, we will review the main points of this theory. NPcompleteness of a particular problem is strong evidence that a polynomial-lime algorithm for its solution is unlikely to exist. The wide applicability of the notion of NPcompleteness was observed by Karp, who proved that 21 basic problems are NPcomplete.