a1 Department of Mathematics, ETH Zürich, Zürich, Switzerland. email@example.com
a2 Department of Information Technology and Electrical Engineering, ETH Zürich, Switzerland; firstname.lastname@example.org
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)
Mathematics Subject Classification: