On-line scheduling of two parallel machines with a single server

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. © 2008 Elsevier Ltd. All rights reserved.