Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates

C. Y. Liu and R. L. Bulfin
Additional contact information
C. Y. Liu: National Sun Yat-Sen University, Kao Hsiung, Taiwan, Republic of China
R. L. Bulfin: Auburn University, Auburn, Alabama

Operations Research, 1988, vol. 36, issue 4, 553-559

Abstract: We examine the problem of scheduling n jobs, each of which must be processed by m machines. If the order in which a given job is processed on the machines is not fixed, the system is called an open shop. This situation might occur in testing components of an electronic system or doing repair work on an automobile. The computational difficulty of solving most open shop problems is known, with the majority being NP-hard. The computational difficulty of a few special cases is unknown, most notably when the jobs have identical processing time and the measure of performance is a function of job due dates. We reduce this uncertainty by developing polynomial algorithms to minimize the total tardiness and the number of tardy jobs in an open shop with identical processing time jobs.

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

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.4.553 (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:36:y:1988:i:4:p:553-559

Access Statistics for this article

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