×

An optimal online algorithm for single machine scheduling with bounded delivery times. (English) Zbl 1177.90173

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.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Borodin, A.; El-Yaniv, R., Online Computation and Competitive Analysis (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0931.68015
[2] K. Pruhs, J. Sgall, E. Torng, Online scheduling, in: J.Y.-T. Leung (Ed.), Handbook of Scheduling: Algorithms, Models, and Performance Analysis, 2004.; K. Pruhs, J. Sgall, E. Torng, Online scheduling, in: J.Y.-T. Leung (Ed.), Handbook of Scheduling: Algorithms, Models, and Performance Analysis, 2004.
[3] Hoogeveen, J. A.; Vestjens, A. P.A., A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine, SIAM Journal on Discrete Mathematics, 13, 56-63 (2000) · Zbl 0944.90020
[4] Tian, Ji; Fu, Ruyan; Yuan, Jinjiang, A best on-line algorithm for single machine scheduling with small delivery times, Theoretical Computer Science, 393, 287-293 (2008) · Zbl 1136.68017
[5] Kise, H.; Iberaki, T.; Mine, H., Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times, Journal of Operation Research Society Japan, 22, 205-224 (1979) · Zbl 0427.90049
[6] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: Algorithms and complexity, (Graves, S. C.; Zipkin, P. H.; Rinnooy Kan, A. H.G., Logistics of Production and Inventory. Logistics of Production and Inventory, Handbooks of Operation Research Management Science, vol. 4 (1993), North-Holland: North-Holland Amsterdam), 445-522
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.