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

Lele Zhang, Andrew Wirth

Research output: Contribution to journalArticleResearchpeer-review

21 Citations (Scopus)


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 oil 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.
Original languageEnglish
Pages (from-to)1529 - 1553
Number of pages25
JournalComputers and Operations Research
Issue number5
Publication statusPublished - 2009
Externally publishedYes

Cite this