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 : 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},
     mrnumber = {2981673},
     zbl = {1283.68158},
     language = {en},
     url = {http://archive.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
SP  - 329
EP  - 342
VL  - 46
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2011132/
DO  - 10.1051/ita/2011132
LA  - en
ID  - ITA_2012__46_3_329_0
ER  - 
%0 Journal Article
%A Akveld, Meike
%A Bernhard, Raphael
%T Job shop scheduling with unit length tasks
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2012
%P 329-342
%V 46
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2011132/
%R 10.1051/ita/2011132
%G en
%F 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) no. 3, pp. 329-342. doi : 10.1051/ita/2011132. http://archive.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

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

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

[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 | Zbl

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

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

[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 | Zbl

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

Cité par Sources :