Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-05T12:57:26.986Z 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. [email protected]
Raphael Bernhard
Affiliation:
Department of Information Technology and Electrical Engineering, ETH Zürich, Switzerland; [email protected]
Get access

Abstract

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.

Keywords

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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