An optimal online algorithm for single machine scheduling with bounded delivery times (Q1038322): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4223058 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4821818 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Best Possible Deterministic On-Line Algorithm for Minimizing Maximum Delivery Time on a Single Machine / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A best on-line algorithm for single machine scheduling with small delivery times / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3995531 / rank | |||
Normal rank |
Latest revision as of 05:17, 2 July 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
0 references