Job Shop Scheduling

From Wikipedia, the free encyclopedia

 This article does not cite any references or sources. (March 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

Job Scheduling is a fundamental problem in Computer Science. The most basic version is as follows:

We are given n jobs J1, J2, ... Jn of varying sizes, which need to be scheduled on m identical machines, while trying to minimize the total length of the schedule (that is, when all the jobs have finished processing). Mostly, the problem is presented as an online problem, that is, each job is presented, and the online algorithm needs to make a decision about that job before the next job is presented.

This problem is one of the most well known online problems, and was the first problem for which Competitive analysis was presented, by Graham in 1966.

Contents

[edit] Problem Variations

Many variations of the problem exist, which can be summarized as follows:

  • Machines can be related, independent, equal
  • Machines can require a certain gap between jobs
  • Objective function can be to minimize the makespan, the Lp norm, etc
  • Jobs may have constraints, for example a job i needs to finish before job j can be started
  • Jobs and machines have mutual constraints, for example, certain jobs can be scheduled on some machines only

[edit] Major Results

Graham had already provided the List scheduling algorithm in 1966, which is (2 - 1/m)-competitive, where m is the number of machines. Also, it was proved that List scheduling is optimum online algorithm for 2 and 3 machines. In 1992, Bartal, Fiat, Karloff and Vohra presented an algorithm that is 1.986 competitive. A 1.945-competitive algorithm was presented by Karger, Philips and Torng in 1994. In 1992, Albers provided a different algorithm that is 1.923-competitive.
Currently, the best known result is an algorithm given by Fleischer and Wahl, which achieves a competitive ratio of 1.9201.

A lower bound of 1.852 was presented by Albers.
Currently, best known lower bound is 1.88, which was presented by Rudin in 2001.

[edit] See also

[edit] References