Rescheduling to minimize makespan on a changing number of identical processors
CA Tovey - Naval research logistics quarterly, 1986 - Wiley Online Library
Naval research logistics quarterly, 1986•Wiley Online Library
We consider the problem of rescheduling n jobs to minimize the makespan on m parallel
identical processors when m changes value. We show this problem to be NP‐hard in
general. Call a list schedule totally optimal if it is optimal for all m= 1,…, n. When n is less
than 6, there always exists a totally optimal schedule, but for n≥ 6 this can fail. We show that
an exact solution is less robust than the largest processing time first (LPT) heuristic and
discuss implications for polynomial approximation schemes and hierarchical planning …
identical processors when m changes value. We show this problem to be NP‐hard in
general. Call a list schedule totally optimal if it is optimal for all m= 1,…, n. When n is less
than 6, there always exists a totally optimal schedule, but for n≥ 6 this can fail. We show that
an exact solution is less robust than the largest processing time first (LPT) heuristic and
discuss implications for polynomial approximation schemes and hierarchical planning …
Abstract
We consider the problem of rescheduling n jobs to minimize the makespan on m parallel identical processors when m changes value. We show this problem to be NP‐hard in general. Call a list schedule totally optimal if it is optimal for all m = 1, …,n. When n is less than 6, there always exists a totally optimal schedule, but for n ≥ 6 this can fail. We show that an exact solution is less robust than the largest processing time first (LPT) heuristic and discuss implications for polynomial approximation schemes and hierarchical planning models.