Job shop scheduling with unit length tasks

Meike Akveld; Raphael Bernhard

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2012)

  • Volume: 46, Issue: 3, page 329-342
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Akveld, Meike, and Bernhard, Raphael. "Job shop scheduling with unit length tasks." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 46.3 (2012): 329-342. <http://eudml.org/doc/273072>.

@article{Akveld2012,
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.},
author = {Akveld, Meike, Bernhard, Raphael},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {online algorithms; competitive analysis; job shop scheduling; online algorithm},
language = {eng},
number = {3},
pages = {329-342},
publisher = {EDP-Sciences},
title = {Job shop scheduling with unit length tasks},
url = {http://eudml.org/doc/273072},
volume = {46},
year = {2012},
}

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
PB - EDP-Sciences
VL - 46
IS - 3
SP - 329
EP - 342
AB - 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.
LA - eng
KW - online algorithms; competitive analysis; job shop scheduling; online algorithm
UR - http://eudml.org/doc/273072
ER -

References

top
  1. [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. Zbl1272.68466
  2. [2] P. Brucker, An efficient algorithm for the job-shop problem with two jobs. Computing40 (1988) 353–359. Zbl0654.90036MR969653
  3. [3] P. Brucker, Scheduling Algorithms, 4th edition. Springer-Verlag (2004). Zbl0839.90059MR2061399
  4. [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. Zbl1186.90051MR2302153
  5. [5] A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press (1998). Zbl0931.68015MR1617778
  6. [6] J. Hromkovič, Design and Analysis of Randomized Algorithms. Springer-Verlag (2006). Zbl1083.68146MR2156292
  7. [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. [8] D. Komm and R. Kálovič, Advice complexity and barely random algorithms. Theoret. Inform. Appl.45 (2011) 249–267. Zbl1218.68090MR2811657
  9. [9] D.D. Sleator and R.E. Tarjan, Amortized efficiency of list update and paging rules. Commun. ACM28 (1985) 202–208. MR777385

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.