RAIRO - Theoretical Informatics and Applications

Research Article

Job shop scheduling with unit length tasks

Meike Akvelda1 and Raphael Bernharda2

a1 Department of Mathematics, ETH Zürich, Zürich, Switzerland. akveld@math.ethz.ch

a2 Department of Information Technology and Electrical Engineering, ETH Zürich, Switzerland; beraphae@student.ethz.ch


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.

(Received September 1 2010)

(Accepted November 3 2011)

(Online publication December 21 2011)

Key Words:

  • Online algorithms;
  • competitive analysis;
  • job shop scheduling

Mathematics Subject Classification:

  • 68Q25