Near-optimal solutions and large integrality gaps for almost all instances of single-machine precedence-constrained scheduling
We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints in which all minimal jobs have unit processing time and zero weight, and all maximal jobs have zero processing time and unit weight. For various probability dist...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
INFORMS
2011
|
| Online Access: | http://hdl.handle.net/1721.1/67660 https://orcid.org/0000-0002-9595-459X |