A proof for the longest-job-first policy in one machine scheduling

A proof for the longest-job-first policy in one machine scheduling

0.00 Avg rating0 Votes
Article ID: iaor1992527
Country: United States
Volume: 38
Issue: 5
Start Page Number: 715
End Page Number: 720
Publication Date: Oct 1991
Journal: Naval Research Logistics
Authors: ,
Abstract:

The authors 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. The authors 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, they 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. The authors also prove that this property holds for a general class of unimodal penalty functions.

Reviews

Required fields are marked *. Your email address will not be published.