Premium
Scheduling to minimize release‐time resource consumption and tardiness penalties
Author(s) -
Li ChungLun,
Sewell Edward C.,
Cheng T. C. E.
Publication year - 1995
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199509)42:6<949::aid-nav3220420607>3.0.co;2-3
Subject(s) - tardiness , computer science , resource consumption , scheduling (production processes) , due date , mathematical optimization , job shop scheduling , operations research , time complexity , retard , mathematics , algorithm , schedule , psychology , ecology , psychiatry , biology , operating system
Abstract We consider the problem of scheduling a set of jobs with a common due‐date on a single‐machine where the release time of a job is related to the amount of resource consumed. The objective is to minimize the total resource consumption and the total tardiness. While the problem is strongly NP‐hard in general, we discuss two different special cases for which special properties are identified and used to develop efficient pseudo‐polynomial time algorithms. © 1995 John Wiley & Sons, Inc.