Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475925 | Computers & Operations Research | 2009 | 25 Pages |
Abstract
In this paper, we consider the on-line scheduling of two parallel identical machines sharing a single server with the objective of minimizing the latest completion time of all jobs. Each job has to be setup by the server before being processed on one of the machines. Three special cases: equal length jobs, equal processing times and regular equal setup times are considered and the asymptotic competitive ratios of list scheduling are determined. Also, a lower bound for the equal length job case is given, and two heuristics with tight asymptotic competitive ratios for the other two cases are proposed.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Lele Zhang, Andrew Wirth,