Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331371 | Information Processing Letters | 2005 | 6 Pages |
Abstract
An extended version of the multiprocessor machine scheduling problem with makespan objective, which arises from single-hop multi-channel LANs, is presented in this paper. In this scheduling model, each job consists of two operations, and each operation may be processed by anyone of a given set of machines, while in the job shop scheduling problem, such a set contains only one machine. For this NP-complete problem, we first analyze the performance ratios of two simple strategies, List Scheduling and Longest Processing Time First, for the off-line cases, which have performance ratios (5/2â1/2m) and (2+1/2(m+1)), respectively, with (m+1) being the number of the machines. We also show that the competitive ratio of the List Scheduling strategy for the on-line cases is (7/2â1/2m).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Fengfeng Zhou, Yinlong Xu, Guoliang Chen,