A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times

Hiroshi Kise, Toshihide Ibaraki and Hisashi Mine
Additional contact information
Hiroshi Kise: Kyoto Institute of Technology, Kyoto, Japan
Toshihide Ibaraki: Kyoto University, Kyoto, Japan
Hisashi Mine: Kyoto University, Kyoto, Japan

Operations Research, 1978, vol. 26, issue 1, 121-126

Abstract: We consider a class of n -job one-machine scheduling problems with ready time r ( i ), processing time p ( i ), and due time d ( i ) for each job i . Preemption is not allowed, and precedence constraints among jobs are not assumed. For this problem we show that there is a 0( n 2 )-time algorithm to find a schedule that minimizes the number of tardy jobs, under the assumption that r ( i ) r ( j ) implies d ( i ) ≤ d ( j ).

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.26.1.121 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:26:y:1978:i:1:p:121-126

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().