Article ID: | iaor20071718 |
Country: | Singapore |
Volume: | 23 |
Issue: | 1 |
Start Page Number: | 77 |
End Page Number: | 88 |
Publication Date: | Mar 2006 |
Journal: | Asia-Pacific Journal of Operational Research |
Authors: | He Yong, Jiang Yiwei |
In this paper, we consider a semi-online preemptive scheduling problem on two uniform machines, where we assume that all jobs have sizes between p and rp for some p > 0 and r ⩽ 1. The goal is to maximize the continuous period of time (starting from time zero) when both machines are busy. We present an optimal semi-online algorithm for any combination of the job size ratio r and machine speed ratio s.