Job shop scheduling with unit length tasks
Akveld, Meike ; Bernhard, Raphael
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012), p. 329-342 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2012-01-01
DOI : https://doi.org/10.1051/ita/2011132
Classification:  68Q25 
@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},
     volume = {46},
     year = {2012},
     pages = {329-342},
     doi = {10.1051/ita/2011132},
     mrnumber = {2981673},
     zbl = {1283.68158},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2012__46_3_329_0}
}

Akveld, Meike; Bernhard, Raphael. Job shop scheduling with unit length tasks. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 329-342. doi : 10.1051/ita/2011132. http://gdmltest.u-ga.fr/item/ITA_2012__46_3_329_0/

[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