| - | ||||
|
|
Near-Optimal Solutions and Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling
Andreas S. Schulz (schulz Abstract: We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints where all minimal jobs have unit processing time and zero weight, and all maximal jobs have zero processing time and unit weight. This NP-hard scheduling problem can be equivalently viewed as a graph orientation problem on a mixed complete bipartite graph. For various probability distributions over these instances--including the uniform distribution--we show several "almost all"-type results, including that for almost all instances, every feasible solution is arbitrarily close to optimal. To the best of our knowledge, our results are the first of their kind for scheduling and graph orientation problems. Keywords: Category 1: Combinatorial Optimization Category 2: Applications -- OR and Management Sciences (Scheduling ) Citation: Working Paper, August 2008. Revised February 2009, May 2009. Download: [PDF] Entry Submitted: 08/21/2008 Modify/Update this entry | ||
| Visitors | Authors | More about us | Links | |
|
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
|
||||