Top

Journal of Combinatorial Optimization

Published in:

09-03-2020

Online scheduling on a single machine with linear deteriorating processing times and delivery times

Authors: Xing Chai, Wenhua Li, Hang Yuan, Libo Wang

Published in: Journal of Combinatorial Optimization | Issue 3/2022

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

search-config

AI-assisted search

Off

Abstract

This paper considers a class of problems with linear deteriorating jobs. Jobs are released over time and become known to the online scheduler until their release times. Jobs are with deteriorating processing times or deteriorating delivery times. The objective is to minimize the time by which all jobs are delivered. We consider five different models on a single machine, and present an optimal online algorithm in competitiveness for each model, respectively.

previous article An approximation algorithm for the maximum spectral subgraph problem

next article A primal-dual algorithm for the minimum power partial cover problem

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

Alidaee B, Womer NK (1999) Scheduling with time dependent processing times: review and extensions. J Oper Res Soc 50(7):711–720CrossRef

Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, CambridgeMATH

Browne S, Yechiali U (1990) Scheduling deteriorating jobs on a single processor. Oper Res 38(3):495–498CrossRef

Cheng MB, Sun SJ (2007) A heuristic MBLS algorithm for the two semi-online parallel machine scheduling problems with deterioration jobs. J Shanghai Univ 11(5):451–456MathSciNetCrossRef

Cheng TCE, Ding Q, Lin BMT (2004) A concise survey of scheduling with time-dependent processing times. Eur J Oper Res 152(1):1–13MathSciNetCrossRef

Fang Y, Lu XW, Liu PH (2011) Online batch scheduling on parallel machines with delivery times. Theor Comput Sci 412:5333–5339MathSciNetCrossRef

Gupta JND, Gupta SK (1988) Single facility scheduling with nonlinear processing times. Comput Ind Eng 14(4):387–393CrossRef

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

Kunnathur AS, Gupta SK (1990) Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. Eur J Oper Res 47(1):56–64MathSciNetCrossRef

Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1993) Sequencing and scheduling: algorithms and complexity. In: Graves SC, Zipkin PH, Rinnooy Kan AHG (eds) Handbooks in operation research and management science, vol 4. Logistics of production and inventory. North-Holland, Amsterdam, pp 445–522

Liu PH, Lu XW (2015a) Online unbounded batch scheduling on parallel machines with delivery times. J Comb Optim 29:228–236MathSciNetCrossRef

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

Liu M, Zheng FF, Wang SJ, Huo JZ (2012) Optimal algorithms for online single machine scheduling with deteriorating jobs. Theor Comput Sci 445:75–81MathSciNetCrossRef

Mosheiov G (1994) Scheduling jobs under simple linear deterioration. Comput Oper Res 21(6):653–659CrossRef

Tian J, Fu RY, Yuan JJ (2007) Online scheduling with delivery time on a single batch machine. Theor Comput Sci 374:49–57CrossRef

Tian J, Cheng TCE, Ng CT, Yuan JJ (2012) An improved on-line algorithm for single parallel-batch machine scheduling with delivery times. Discrete Appl Math 160:1191–1210MathSciNetCrossRef

Tian J, Fu RY, Yuan JJ (2014) Online over time scheduling on parallel-batch machines: a survey. J Oper Res Soc China 2:445–454MathSciNetCrossRef

Yu S, Wong PWH (2013) Online scheduling of simple linear deteriorating jobs to minimize the total general completion time. Theor Comput Sci 487:95–102MathSciNetCrossRef

Yuan JJ, Li SS, Tian J, Fu RY (2009) A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times. J Comb Optim 17:206–213MathSciNetCrossRef

Title: Online scheduling on a single machine with linear deteriorating processing times and delivery times
Authors: Xing Chai
Wenhua Li
Hang Yuan
Libo Wang
Publication date: 09-03-2020
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 3/2022
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00557-5

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 3/2022

From packing rules to cost-sharing mechanisms

Randomized selection algorithm for online stochastic unrelated machines scheduling

On the approximability of Time Disjoint Walks

Error-correcting codes based on partial linear maps of finite-dimensional vector spaces

Fast computation of global solutions to the single-period unit commitment problem

Exact algorithms for finding constrained minimum spanning trees

Premium Partner