RAIRO-Theor. Inf. Appl.
Volume 46, Number 3, July-September 2012
|Page(s)||329 - 342|
|Published online||21 December 2011|
Job shop scheduling with unit length tasks
Accepted: 3 November 2011
In this paper, we consider a class of scheduling problems that are among the fundamental optimization problems in operations research. More specifically, we deal with a particular version called job shop scheduling with unit length tasks. Using the results of Hromkovič, Mömke, Steinhöfel, and Widmayer presented in their work Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms, we analyze the problem setting for 2 jobs with an unequal number of tasks. We contribute a deterministic algorithm which achieves a vanishing delay in certain cases and a randomized algorithm with a competitive ratio tending to 1. Furthermore, we investigate the problem with 3 jobs and we construct a randomized online algorithm which also has a competitive ratio tending to 1.
Mathematics Subject Classification: 68Q25
Key words: Online algorithms / competitive analysis / job shop scheduling
© EDP Sciences 2011
Initial download of the metrics may take a while.