Volume 72, Numbers 3-4, 355-363, DOI: 10.1007/s00607-003-0034-2

Semi-Online Algorithms for Parallel Machine Scheduling Problems

G. Dósa and Y. He

View Related Documents

Abstract

This paper considers two semi-online versions of scheduling problem P2||Cmax where one type of partial information is available and one type of additional algorithmic extension is allowed simultaneously. For the semi-online version where a buffer of length 1 is available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 5/4. We also show that it does not help that the buffer length is greater than 1. For the semi-online version where two parallel processors are available and the total size of all jobs is known in advance, we present an optimal algorithm with competitive ratio 6/5.

Keywords  scheduling - semi-online - approximation algorithm - competitive analysis

AMS Subject Classification  90B35 - 90C27

The second author is supported by TRAPOYT of China, National Natural Science Foundation of China (10271110). Corresponding author: Y. He.

Fulltext Preview

Image of the first page of the fulltext document