Resource constrained chain scheduling of UET jobs on two machines
成果类型：
Article
署名作者：
Kubiak, W; Blazewicz, J; Dror, M; Katoh, N; Rock, H
署名单位：
Memorial University Newfoundland; Poznan University of Technology; University of Arizona; University of Hyogo; Kobe University; University of Rostock
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.46.5.742
发表日期：
1998
页码：
742-746
关键词：
摘要：
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.