Top

Journal of Combinatorial Optimization

Published in:

24-04-2020

An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown

Authors: Ji Tian, Yan Zhou, Ruyan Fu

Published in: Journal of Combinatorial Optimization | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider a semi-online scheduling problem on a single machine with an unexpected breakdown period. In the problem, each job has a processing time and a subsequent delivery time. All these data are known in the beginning. The scheduler has to determine a sequence S of these jobs for processing. After S is given, a machine unavailability period may occur where its starting time and length are not known in advance. The objective is to minimize the time by which all jobs are delivered. We present an online algorithm with a competitive ratio of \(\frac{\sqrt{5}+1}{2}\approx 1.618\), which improves the previously known algorithm with \(\frac{2+\sqrt{2}}{2}\approx 1.707\)-competitive.

previous article Classification optimization for training a large dataset with Naïve Bayes

next article New restrictions on defective coloring with applications to steinberg-type graphs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Akker MVD, Hoogeveen H, Vakhania N (2000) Restarts can help in the online minimization of the maximum delivery time on a single machine. J Sched 3:333–341MathSciNetCrossRef

Hall LA, Shmoys DB (1992) Jackson’s rule for single machine scheduling: making a good heuristic better. Math Oper Res 17:22–35MathSciNetCrossRef

Hoogeveen JA, Vestjean APA (2002) A best possible deterministic online algorithm for minimizing maximum delivery times on a single machine. SIAM J Discret Math 13:56–63CrossRef

Huo Y, Reznichenko B, Zhao H (2014) Minimizing total weighted completion time with an unexpected machine unavailable interval. J Sched 17(2):161–172MathSciNetCrossRef

Jackson JR (1955) Scheduling a production line to minimize maximum tardiness. Research report 43, Mgmt Sci Research Project, UCLA

Kacem I (2009) Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval. J Comb Optim 17(2):117–133MathSciNetCrossRef

Kacem I, Haouari M (2009) Approximation algorithms for single machine scheduling with one unavailability period. 4OR-Q J Oper Res 7:79–92MathSciNetCrossRef

Kacem I, Kellerer H (2016) Semi-online scheduling on a single machine with unexpected breakdown. Theor Comput Sci 646:40–48MathSciNetCrossRef

Kacem I, Kellerer H, Seifaddini M (2016) Efficient approximation schemes for the maximum delivery time minimization on a single machine with a fixed operator or machine non-availability interval. J Comb Optim 32(3):970–981 MathSciNetCrossRef

Kise H, Ibaraki T, Mine H (1979) Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times. J Oper Res Soc Jpn 22:205–224MathSciNetCrossRef

Lee CY (1996) Machine scheduling with an availability constraints. J Global Optim 9:363–384MathSciNetCrossRef

Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discret Math 1:343–362MathSciNetCrossRef

Liu PH, Lu XW (2015) Online scheduling on two parallel machines with release dates and delivery times. J Comb Optim 30(2):347–359MathSciNetCrossRef

Liu M, Chu C, Xu Y, Zheng F (2010) An optimal online algorithm for single machine scheduling with bounded delivery times. Eur J Oper Res 201(3):693–700MathSciNetCrossRef

Potts CN (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper Res 28:1436–1441MathSciNetCrossRef

Tan Z, He Y (2002) Optimal online algorithm for scheduling on two identical machines with machine availability constraints. Inf Process Lett 83:323–329MathSciNetCrossRef

Tian J, Fu RY, Yuan JJ (2008) A best online algorithm for single machine scheduling with small delivery times. Theor Comput Sci 393:287–293CrossRef

Yuan JJ, Shi L, Ou JW (2008) Single machine scheduling with forbidden intervals and job delivery times. Asia Pac J Oper Res 25(3):317–325MathSciNetCrossRef

Title: An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown
Authors: Ji Tian
Yan Zhou
Ruyan Fu
Publication date: 24-04-2020
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00572-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

A -approximation algorithm for coloring rooted subtrees of a degree 3 tree

Approximating the asymmetric p-center problem in parameterized complete digraphs

A variation of DS decomposition in set function optimization

Analysis of Divide-and-Conquer strategies for the 0–1 minimization knapsack problem

Secure domination of honeycomb networks

Planar graphs without 4- and 6-cycles are (7 : 2)-colorable

Premium Partner