Hostname: page-component-7b7567c8c-lpg2g Total loading time: 0 Render date: 2026-11-15T12:34:47.925Z Has data issue: false hasContentIssue false
  • English
  • Français

Job shop scheduling with unit length tasks

Published online by Cambridge University Press:  21 December 2011

Meike Akveld and
Raphael Bernhard
Meike Akveld
Affiliation:
Department of Mathematics, ETH Zürich, Zürich, Switzerland. akveld@math.ethz.ch
Raphael Bernhard
Affiliation:
Department of Information Technology and Electrical Engineering, ETH Zürich, Switzerland; beraphae@student.ethz.ch

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper, we consider a class of scheduling problems that are among the fundamentaloptimization problems in operations research. More specifically, we deal with a particularversion called job shop scheduling with unit length tasks. Using theresults of Hromkovič, Mömke, Steinhöfel, and Widmayer presented in their work JobShop Scheduling with Unit Length Tasks: Bounds and Algorithms, we analyze theproblem setting for 2 jobs with an unequal number of tasks. We contribute a deterministicalgorithm which achieves a vanishing delay in certain cases and a randomized algorithmwith a competitive ratio tending to 1. Furthermore, we investigate the problem with 3 jobsand we construct a randomized online algorithm which also has a competitive ratio tendingto 1.

Keywords

Online algorithmscompetitive analysisjob shop scheduling

Information

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 46 , Issue 3 , July 2012, pp. 329 - 342
Copyright
© EDP Sciences 2011

References

Böckenhauer, H.-J., Komm, D., Královič, R., Královič, R. and Mömke, T., On the advice complexity of online problems, in Proc. of the 20th International Symposium on Algorithms and Computation (ISAAC 2009). Lect. Notes Comput. Sci. 5878 (2009) 331–340. Google Scholar
Brucker, P., An efficient algorithm for the job-shop problem with two jobs. Computing 40 (1988) 353–359. Google Scholar
P. Brucker, Scheduling Algorithms, 4th edition. Springer-Verlag (2004).
Hromkovič, J., Mömke, T., Steinhöfel, K. and Widmayer, P., Job shop scheduling with unit length tasks: bounds and algorithms. Algorithmic Oper. Res. 2 (2007) 1–14. Google Scholar
A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press (1998).
J. Hromkovič, Design and Analysis of Randomized Algorithms. Springer-Verlag (2006).
S. Irani and A.R. Karlin, On online computation, in Approximation Algorithms for NP-hard Problems, Chapter 13, edited by Hochbaum. PWS Publishing Company (1997) 521–564.
Komm, D. and Kálovič, R., Advice complexity and barely random algorithms. Theoret. Inform. Appl. 45 (2011) 249–267. Google Scholar
Sleator, D.D. and Tarjan, R.E., Amortized efficiency of list update and paging rules. Commun. ACM 28 (1985) 202–208. Google Scholar