On the fixed interval due-date scheduling problem

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

8 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)101-117
Journal / PublicationDiscrete Applied Mathematics
Volume68
Issue number1-2
Publication statusPublished - 12 Jun 1996
Externally publishedYes

Abstract

We consider the nonpreemptive single machine scheduling problem with multiple due-dates (delivery dates), where the time between two consecutive due-dates is a constant. Given a set of jobs, we are interested in scheduling the jobs such that the sum of the total due-date cost and the total earliness cost is minimized with the constraint that each job must be finished at or before its due-date. We show that this problem is strongly NP-hard in general. We then analyze the problem where the number of due-dates is bounded by a given constant. We describe a pseudo-polynomial dynamic programming algorithm for this restricted problem. A heuristic is also provided and worst-case analysis is performed. An efficient algorithm is developed to solve the special case where all the job processing times are identical.

Research Area(s)

  • Delivery dates, Scheduling, Single machine

Bibliographic Note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Citation Format(s)

On the fixed interval due-date scheduling problem. / Lee, Chung-Yee; Li, Chung-Lun.
In: Discrete Applied Mathematics, Vol. 68, No. 1-2, 12.06.1996, p. 101-117.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review