作者：Chan, LMA; Muriel, A; Simchi-Levi, D
作者单位：University of Toronto; University of Michigan System; University of Michigan; Northwestern University
摘要：In this paper we consider a class of parallel machine scheduling problems and their associated set-partitioning formulations. We show that the tightness of the linear programming relaxation of these formulations is directly related to the performance of a class of heuristics called parameter list scheduling heuristics. This makes it possible to characterize the worst possible gap between optimal solutions for the scheduling problems and the corresponding linear programming relaxations. In the ...
作者：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
摘要：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 ...
