A proof for the longest-job-first policy in one-machine scheduling
✍ Scribed by T. C. E. Cheng; H. G. Kahlbacher
- Publisher
- John Wiley and Sons
- Year
- 1991
- Tongue
- English
- Weight
- 256 KB
- Volume
- 38
- Category
- Article
- ISSN
- 0894-069X
No coin nor oath required. For personal study only.
✦ Synopsis
We consider a one-machine scheduling problem with earliness and tardiness penalties. All jobs are assigned a common due date and the objective is to minimize the total penalty due to job earliness and tardiness. We are interested in finding the optimal combination of the common due-date value and the job sequence. Despite the fact that this problem in general is very hard to solve, we prove that there exists at least a common property for all optimal solutions: The first job in an optimal sequence is one of the longest jobs. We also prove that this property holds for a general class of unimodal penalty functions.