Online Scheduling on Two Parallel Identical Machines with a Non-Clairvoyant Disruption

Abstract:

Article Preview

This paper studies two parallel machine scheduling with a non-clairvoyantdisruption such that there happens one disruption on one machine at time 0 and its du-ration length can only be known at its end. As in [1], we introduce transportation timein the environment of disruption, aiming to minimize the maximum deviation of jobs'planned and actual completion times. We adopt online theory to describe the problemand focus on the case of unit length of job. We rst show that a greedily waiting strategyis 2-competitive. Our main result is a 3/2-competitive strategy BD which makes useof job transportation. We also prove a matching lower bound, implying that BD is anoptimal strategy.

Info:

Periodical:

Edited by:

Xingui He, Ertian Hua, Yun Lin and Xiaozhu Liu

Pages:

264-268

DOI:

10.4028/www.scientific.net/AMM.88-89.264

Citation:

F. F. Zheng et al., "Online Scheduling on Two Parallel Identical Machines with a Non-Clairvoyant Disruption", Applied Mechanics and Materials, Vols. 88-89, pp. 264-268, 2011

Online since:

August 2011

Export:

Price:

$35.00

In order to see related information, you need to Login.

In order to see related information, you need to Login.