Resource Constrained Chain Scheduling of UET Jobs on Two Machines

W. Kubiak, J. Błażewicz, M. Dror, N. Katoh and H. Rock
Additional contact information
W. Kubiak: Memorial University of Newfoundland, St. John's, Canada
J. Błażewicz: Politechnika Poznańska, Poznan, Poland
M. Dror: University of Arizona, Tucson, Arizona
N. Katoh: Kobe University of Commerce, Kobe, Japan
H. Rock: Universität Rostock, Rostock, Germany

Operations Research, 1998, vol. 46, issue 5, 742-746

Abstract: A well-known technique for solving scheduling problems with two identical parallel processors and unit execution time jobs under a makespan minimization criteria involves finding maximum cardinality matchings in the graph associated with the problem, and then using these matchings to create optimal schedules. For some problem instances, however, this method will not work, since the problems are NP-hard. In this note, a previously open problem involving additional resource constraints is shown to have a polynomial algorithm using cardinality matching method.

Keywords: Analysis of algorithms; computational complexity; Networks/graphs; matchings; Scheduling; sequencing; deterministic (search for similar items in EconPapers)
Date: 1998
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.5.742 (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:46:y:1998:i:5:p:742-746

Access Statistics for this article

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