| 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.