@inproceedings{3bd7da610a1b48508977ccce7fdb3165,
title = "Online scheduling on two parallel identical machines with a non-clairvoyant disruption",
abstract = "This paper studies two parallel machine scheduling with a non-clairvoyant disruption such that there happens one disruption on one machine at time 0 and its duration length can only be known at its end. As in [1], we introduce transportation time in the environment of disruption, aiming to minimize the maximum deviation of jobs' planned and actual completion times. We adopt online theory to describe the problem and focus on the case of unit length of job. We first show that a greedily waiting strategy is 2-competitive. Our main result is a 3/2-competitive strategy BD which makes use of job transportation. We also prove a matching lower bound, implying that BD is an optimal strategy.",
keywords = "Competitive ratio, Disruption, Online strategy, Scheduling",
author = "Feifeng Zheng and Honglong Wei and Yinfeng Xu and Ming Liu",
year = "2011",
doi = "10.4028/www.scientific.net/AMM.88-89.264",
language = "英语",
isbn = "9783037852361",
series = "Applied Mechanics and Materials",
pages = "264--268",
booktitle = "Computer-Aided Design, Manufacturing, Modeling and Simulation, CDMMS 2011",
note = "International Conference on Computer-Aided Design, Manufacturing, Modeling and Simulation, CDMMS 2011 ; Conference date: 13-09-2011 Through 16-09-2011",
}