| Issue |
RAIRO-Theor. Inf. Appl.
Volume 46, Number 3, July-September 2012
|
|
|---|---|---|
| Page(s) | 329 - 342 | |
| DOI | https://doi.org/10.1051/ita/2011132 | |
| Published online | 21 December 2011 | |
Job shop scheduling with unit length tasks
1
Department of Mathematics, ETH Zürich, Zürich, Switzerland
akveld@math.ethz.ch
2
Department of Information Technology and Electrical
Engineering, ETH
Zürich, Switzerland
beraphae@student.ethz.ch
Received:
1
September
2010
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.