OPTIMAL PREEMPTIVE SEMI-ONLINE ALGORITHM FOR SCHEDULING TIGHTLY-GROUPED JOBS ON TWO UNIFORM MACHINES

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.

MoreLess

Year of publication:	2006
Authors:	JIANG, YIWEI ; HE, YONG
Published in:	Asia-Pacific Journal of Operational Research (APJOR). - World Scientific Publishing Co. Pte. Ltd., ISSN 1793-7019. - Vol. 23.2006, 01, p. 77-88
Publisher:	World Scientific Publishing Co. Pte. Ltd.
Subject:	Semi-online \| scheduling \| uniform machines \| preemption \| competitive ratio

More details

Extent:	application/pdf text/html
Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://ebvufind01.dmz1.zbw.eu/10005080678