| Article ID: | iaor2000835 |
| Country: | Netherlands |
| Volume: | 21 |
| Issue: | 3 |
| Start Page Number: | 115 |
| End Page Number: | 122 |
| Publication Date: | Oct 1997 |
| Journal: | Operations Research Letters |
| Authors: | Wein Joel, Stein Cliff |
We give a simple proof that, for any instance of a very general class of scheduling problems, there exists a schedule of makespan at most twice that of the optimal possible and of total weighted completion time at most twice that of the optimal possible. We then refine the analysis, yielding variants of this theorem with improved constants, and give some algorithmic consequences of the technique.