Abstract
Complexity theory is an important tool in scheduling research. When we are confronted with a new scheduling problem, the very first thing we try is to develop efficient algorithms for solving the problem. Unfortunately, very often, we could not come up with any algorithm more efficient than essentially an enumerative search, even though a considerable amount of time had been spent on the problem. In situations like this, the theory of NP-hardness may be useful to pinpoint that no efficient algorithms could possibly exist for the problem in hand. Therefore, knowledge of NP-hardness is absolutely essential for anyone interested in scheduling research.
| Original language | English (US) |
|---|---|
| Title of host publication | Handbook of Scheduling |
| Subtitle of host publication | Algorithms, Models, and Performance Analysis |
| Publisher | CRC Press |
| Pages | 2-1-2-14 |
| ISBN (Electronic) | 9780203489802 |
| ISBN (Print) | 9781584883975 |
| State | Published - Jan 1 2004 |
All Science Journal Classification (ASJC) codes
- General Engineering
- General Computer Science
- General Economics, Econometrics and Finance
- General Business, Management and Accounting