Abstract
The problem of nonpreemptively scheduling n independent tasks on m identical and parallel machines with the objective of minimizing the overall finishing time is considered. The problem has been shown to be NP-complete in the strong sense and hence there probably will not be any pseudo-polynomial time algorithm for solving this problem. It is shown that if the execution times are restricted to a fixed number, say k, of different values, then it can be solved in polynomial time.
| Original language | English (US) |
|---|---|
| Pages | 471-479 |
| Number of pages | 9 |
| State | Published - 1981 |
| Event | Proc Annu Allerton Conf Commun Control Comput 18th - Monticello, IL, USA Duration: Oct 8 1980 → Oct 11 1980 |
Conference
| Conference | Proc Annu Allerton Conf Commun Control Comput 18th |
|---|---|
| City | Monticello, IL, USA |
| Period | 10/8/80 → 10/11/80 |
All Science Journal Classification (ASJC) codes
- General Engineering