Job shop scheduling with unit length tasks

Meike Akveld; Raphael Bernhard

RAIRO - Theoretical Informatics and 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 46.3 (2012): 329-342. <http://eudml.org/doc/221998>.

@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},
keywords = {Online algorithms; competitive analysis; job shop scheduling; online algorithm},
language = {eng},
month = {8},
number = {3},
pages = {329-342},
publisher = {EDP Sciences},
title = {Job shop scheduling with unit length tasks},
url = {http://eudml.org/doc/221998},
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
DA - 2012/8//
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/221998
ER -

References

top
  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.  
  2. P. Brucker, An efficient algorithm for the job-shop problem with two jobs. Computing40 (1988) 353–359.  
  3. P. Brucker, Scheduling Algorithms, 4th edition. Springer-Verlag (2004).  
  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.  
  5. A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press (1998).  
  6. J. Hromkovič, Design and Analysis of Randomized Algorithms. Springer-Verlag (2006).  
  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.  
  9. D.D. Sleator and R.E. Tarjan, Amortized efficiency of list update and paging rules. Commun. ACM28 (1985) 202–208.  

NotesEmbed ?

top

You must be logged in to post comments.