Scheduling Unit-Time Open Shops with Deadlines

Thomas Tautenhahn
Additional contact information
Thomas Tautenhahn: Technische Universität Otto von Guericke, Magdeburg, Germany

Operations Research, 1994, vol. 42, issue 1, 189-192

Abstract: We consider open shop problems with unit processing times and due dates, where n jobs have to be processed on m machines. The order in which a given job is processed on the machines is not fixed. Such problems occur in testing components of an electronic system or doing repair work on automobiles. In an earlier paper, C. Y. Liu and R. L. Bulfin gave an O ( n 2 m ) algorithm to minimize total tardiness and the number of tardy jobs. We will give a polynomial algorithm to minimize the completion time of all jobs where a deadline is imposed for each job. The complexity of this problem is still open. Then we apply this solution to give improved algorithms to minimize the number of tardy jobs and the maximum lateness.

Keywords: production/scheduling:; open; shop (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.1.189 (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:42:y:1994:i:1:p:189-192

Access Statistics for this article

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