Randomized Online Scheduling with Delivery Times
Author: Seiden, S.
Source: Journal of Combinatorial Optimization, Volume 3, Number 4, December 1999 , pp. 399-416(18)
Abstract:We study one of the most basic online scheduling models, online one machine scheduling with delivery times where jobs arrive over time. We provide the first randomized algorithm for this model, show that it is 1.55370-competitive and show that this analysis is tight. The best possible deterministic algorithm is ≈ 1.61803-competitive. Our algorithm is a distribution between two deterministic algorithms. We show that any such algorithm is no better than 1.5-competitive. To our knowledge, this is the first lower bound proof for a distribution between two deterministic algorithms.
Document Type: Regular Paper
Affiliations: Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany. firstname.lastname@example.org
Publication date: 1999-12-01