Name
Abstract | ||
|---|---|---|
A set of tasks has to be scheduled on three processors and each task requires that a set of the processors be available for a given processing time. The objective of the problem is to determine a nonpreemptive schedule with minimum makespan. The problem is known to be NP-hard in the strong sense. A normal schedule is such that all tasks requiring the same set of processors are scheduled consecutively. We show that, under a certain (uniform) probability distribution on the problem instances, in more than 95% of the instances the best normal schedule is optimal when the number of tasks grows to infinity. For the hard cases it is shown that the relative error produced by the best normal schedule is bounded by 5 4 . This result improves the bound of 4 3 known in the literature and the improved bound is shown to be tight. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0012-365X(97)84781-4 | Discrete Mathematics |
Keywords | Field | DocType |
approximation algorithms,nonpreemptive scheduling,dedicated processor,normal schedule,probabilistic analysis,graph theoretical models,normal schedules,probability distribution,relative error | Approximation algorithm,Discrete mathematics,Mathematical optimization,Job shop scheduling,Infinity,Probabilistic analysis of algorithms,Probability distribution,Schedule,Mathematics,Approximation error,Bounded function | Journal |
Volume | Issue | ISSN |
164 | 1 | Discrete Mathematics |
ISBN | Citations | PageRank |
0012-365X | 13 | 1.19 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| P. Dell'Olmo | 1 | 151 | 15.33 |
| M. G. Speranza | 2 | 294 | 19.55 |
| Zs Tuza | 3 | 367 | 64.48 |