Semi-online algorithms for parallel machine scheduling problems
This paper considers two semi-online versions of scheduling problem P2\\C-max 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.
semi-online scheduling approximation algorithm competitive analysis