Job shop scheduling with unit length tasks
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 3, pp. 329-342.

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.

DOI : https://doi.org/10.1051/ita/2011132
Classification : 68Q25
Mots clés : online algorithms, competitive analysis, job shop scheduling
@article{ITA_2012__46_3_329_0,
     author = {Akveld, Meike and Bernhard, Raphael},
     title = {Job shop scheduling with unit length tasks},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {329--342},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {3},
     year = {2012},
     doi = {10.1051/ita/2011132},
     zbl = {1283.68158},
     mrnumber = {2981673},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2011132/}
}
TY  - JOUR
AU  - Akveld, Meike
AU  - Bernhard, Raphael
TI  - Job shop scheduling with unit length tasks
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2012
DA  - 2012///
SP  - 329
EP  - 342
VL  - 46
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011132/
UR  - https://zbmath.org/?q=an%3A1283.68158
UR  - https://www.ams.org/mathscinet-getitem?mr=2981673
UR  - https://doi.org/10.1051/ita/2011132
DO  - 10.1051/ita/2011132
LA  - en
ID  - ITA_2012__46_3_329_0
ER  - 
Akveld, Meike; Bernhard, Raphael. Job shop scheduling with unit length tasks. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 3, pp. 329-342. doi : 10.1051/ita/2011132. http://www.numdam.org/articles/10.1051/ita/2011132/

[1] H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič and T. Mömke, 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. | Zbl 1272.68466

[2] P. Brucker, An efficient algorithm for the job-shop problem with two jobs. Computing 40 (1988) 353-359. | MR 969653 | Zbl 0654.90036

[3] P. Brucker, Scheduling Algorithms, 4th edition. Springer-Verlag (2004). | MR 2061399 | Zbl 0839.90059

[4] J. Hromkovič, T. Mömke, K. Steinhöfel and P. Widmayer, Job shop scheduling with unit length tasks: bounds and algorithms. Algorithmic Oper. Res. 2 (2007) 1-14. | MR 2302153 | Zbl 1186.90051

[5] A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press (1998). | MR 1617778 | Zbl 0931.68015

[6] J. Hromkovič, Design and Analysis of Randomized Algorithms. Springer-Verlag (2006). | MR 2156292 | Zbl 1083.68146

[7] 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.

[8] D. Komm and R. Kálovič, Advice complexity and barely random algorithms. Theoret. Inform. Appl. 45 (2011) 249-267. | Numdam | MR 2811657 | Zbl 1218.68090

[9] D.D. Sleator and R.E. Tarjan, Amortized efficiency of list update and paging rules. Commun. ACM 28 (1985) 202-208. | MR 777385

Cité par Sources :