- Job Shop Scheduling
Job Shop Scheduling is an optimization problem in
computer science in which ideal jobs are assigned to resources at particular times. 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.
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 onlyMajor 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.
References
*cite journal|last=Albers|first=Susanne|title=Better bounds for online scheduling
journal=SIAM Journal of Computing|volume=29|number=2|pages= 459–473|year=1999|doi=10.1137/S0097539797324874.See also
* Competitive analysis
*List accessing problem
Wikimedia Foundation. 2010.