An optimal online algorithm for single machine scheduling with bounded delivery times
type: Item
instance of: scholarly article
title: An optimal online algorithm for single machine scheduling with bounded delivery times
zbMATH Open document ID: 1177.90173
author: Ming Liu
author: Chengbin Chu
author: Feifeng Zheng
author: Yinfeng Xu
published in: European Journal of Operational Research
publication date: 2009-11-17T00:00:00Z
review text: The online single machine problem \(1|\text{online },r_j, \beta q_j \leq p_j| L_{\max}\) is studied. Given is a set of jobs \(j=1,\ldots,n\) with processing times \(p_j\), release dates \(r_j\) and delivery times \(q_j\) which are bounded by the processing times (i.e. \(\beta q_j \leq p_j\) for all jobs \(j\) for some constant \(\beta \geq 0.5\)). All these jobs have to be processed on a single machine without preemption such that the time when all jobs are delivered is minimized. The problem is considered in an online version where it is assumed that all characteristics of each job become only known at its release date. After providing the lower bound \(0.5 ( \sqrt{5+\beta^2+2 \beta}+1-\beta)\) for the competitive ratio of any online algorithm, an optimal online algorithm achieving this bound is presented.
reviewed by: Sigrid Knust
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 5634700
zbMATH Keywords: online scheduling
zbMATH Keywords: delivery times
zbMATH Keywords: single machine
zbMATH Keywords: competitive analysis
Wikidata QID: Q57185721
MaRDI profile type: Publication
full work available at URL: j.ejor.2009.03.028
OpenAlex ID: W2077224639
cites work: Q4223058
cites work: Q4821818
cites work: A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
cites work: A best on-line algorithm for single machine scheduling with small delivery times
cites work: PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
cites work: Q3995531
DOI: 10.1016/J.EJOR.2009.03.028
Recommended article: A best on-line algorithm for single machine scheduling with small delivery times
Recommended article: An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time
Recommended article: Online Algorithms for Batch Machines Scheduling with Delivery Times
Recommended article: An optimal online algorithm for single machine scheduling to minimize total general completion time
Recommended article: A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times
Recommended article: Optimal on-line algorithms for single-machine scheduling
Recommended article: Online scheduling on a single machine with linear deteriorating processing times and delivery times
Recommended article: A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine
Recommended article: An improved on-line algorithm for single parallel-batch machine scheduling with delivery times
Recommended article: Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time
description: scientific article; zbMATH DE number 5634700