Paper Title:
Online Scheduling on Two Parallel Identical Machines with a Non-Clairvoyant Disruption
  Abstract

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
Chapter
Chapter 5: Optimization and Scheduling
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, H. L. Wei, Y. F. Xu, M. Liu, "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
$32.00
Share

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

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

Authors: Li Zhao Liu, Yu Feng Chen, Tian Hua Zhang, Ying Wang, Mao Qing Li
Abstract:To solve the problem of calculating the maximum linear deviation in block cipher algorithm linear analysis, the paper has proposed a search...
293
Authors: Christina Reuter, Annika Hauptvogel, Felix Brambring, Jochen Hansen
Chapter 6: Organisation of Manufacturing
Abstract:In this paper, an approach to quantify the effects of disruptions in a complex job shop manufacturing is introduced. Key figures within this...
494
Authors: J.M. Ikome, S.P. Ayodeji, M.G. Kanakana
Chapter 10: Industrial Engineering
Abstract:Consistency and on timely delivery are among some of the factors that can keep a customer loyal and committed to a manufacturing industry....
1287