On the fixed interval due-date scheduling problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 101-117 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 68 |
Issue number | 1-2 |
Publication status | Published - 12 Jun 1996 |
Externally published | Yes |
Link(s)
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.
In: Discrete Applied Mathematics, Vol. 68, No. 1-2, 12.06.1996, p. 101-117.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review