Optimal preemptive semi-online algorithm for scheduling tightly-grouped jobs on two uniform machines

Optimal preemptive semi-online algorithm for scheduling tightly-grouped jobs on two uniform machines

0.00 Avg rating0 Votes
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: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.