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.

• Periodical: Applied Mechanics and Materials (Volumes 88-89)
• Pages: 264-268
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.88-89.264
• Online since: August 2011
• Authors: Fei Feng Zheng, Hong Long Wei, Yin Feng Xu, Ming Liu
• Keywords: Competitive Ratio, Disruption, Online Strategy, Scheduling

References

[1] C.Y. Lee, J.Y.T. Leung and G. Yu, Two machine scheduling under disruption with transportation considerations, Journal of Scheduling, vol. 9, pp.35-48 (2006).

DOI: 10.1007/s10951-006-5592-7

[2] X.T. Qi, J.F. Bard, and G. Yu, Disruption management for machine scheduling: The case of SPT schedules, vol. 103, pp.166-184 (2006).

DOI: 10.1016/j.ijpe.2005.05.021

[3] S. Albers, G. Schmidt, Scheduling with unexpected machine breakdowns, Discrete Applied Mathematics, vol. 110, pp.85-99 (2001).

DOI: 10.1016/s0166-218x(00)00266-3

[4] G. Schmidt, Scheduling on semi-identical processors, Mathematical Methods of Operations Research, vol. 28, pp.153-162 (1984).

DOI: 10.1007/bf01920917

[5] S.W. Wu, R.H. Storer, and P.C. Chang, One-machine rescheduling heuristics with efficiency and stability as criteria, Computers & Operations Research, vol. 20, pp.1-14 (1993).

DOI: 10.1016/0305-0548(93)90091-v

[6] C.C. Wu, W.C. Lee, Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single, Information Processing Letters, vol. 87, pp.89-93 (2003).

DOI: 10.1016/s0020-0190(03)00262-x

[7] C.Y. Lee, G. Yu, Single machine scheduling under potential disruption, Operations Research Letters, vol. 35, pp.541-548 (2007).

DOI: 10.1016/j.orl.2006.08.005

[8] B. Kalyanasundaram, K.P. Pruhs, Fault-tolerant scheduling, Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp.115-124.

DOI: 10.1145/195058.195115

[9] C.Y. Lee, Z.L. Chen, Machine scheduling with transportation considerations, Journal of Scheduling, vol. 4, pp.3-24 (2001).

[10] N.G. Hall, C.N. Potts, Supply Chain scheduling: Batching and Delivery, Operations Research, vol. 51, pp.566-584 (2003).

DOI: 10.1287/opre.51.4.566.16106

[11] M.L. Pinedo, Scheduling: Theory, Algorithms and Systems, 2nd Edition, Prentice-Hall, Englewood Cliffs, NJ (2002).

[12] A. Borodin, R. El-yaniv, Online computation and competitive analysis, England: Cambridge University Press (1998).