Minimizing the range of lateness on a single machine under generalized due dates

Minimizing the range of lateness on a single machine under generalized due dates

0.00 Avg rating0 Votes
Article ID: iaor19981673
Country: Canada
Volume: 35
Issue: 4
Start Page Number: 286
End Page Number: 296
Publication Date: Nov 1997
Journal: INFOR
Authors: ,
Keywords: networks: scheduling, manufacturing industries
Abstract:

The problem of scheduling non-preemptively a finite number of jobs on a single machine so as to minimize the difference between the maximum and minimum lateness is considered under the assumption that due dates are job independent. NP-completeness in the strong sense is established for several variants of the problem, and simple O(n log n) approximation algorithms are presented and analyzed.

Reviews

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