An optimal online algorithm for single machine scheduling with bounded delivery times (Q1038322): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 23:45, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An optimal online algorithm for single machine scheduling with bounded delivery times |
scientific article |
Statements
An optimal online algorithm for single machine scheduling with bounded delivery times (English)
0 references
17 November 2009
0 references
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.
0 references
online scheduling
0 references
delivery times
0 references
single machine
0 references
competitive analysis
0 references