Job Shop Scheduling

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 only

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.

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.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Job shop scheduling — For other uses, see Scheduling. Job shop scheduling (or Job shop problem) 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… …   Wikipedia

  • Job shop — Job shops are typically small manufacturing operations that handle specialized manufacturing processes such as small customer orders or small batch jobs. Job shops typically move on to different jobs (possibly with different customers) when each… …   Wikipedia

  • Open shop scheduling — The open shop scheduling problem (OSSP) is a scheduling problem where, given n jobs and m workstations, each job has to visit a workstation at least once. The order in which this happens is not relevant (in contrast to the job shop problem, where …   Wikipedia

  • Scheduling — is the process of deciding how to commit resources between a variety of possible tasks. Time can be specified (scheduling a flight to leave at 8:00) or floating as part of a sequence of events.Scheduling may refer to: * I/O scheduling, the order… …   Wikipedia

  • Job scheduler — This article is about a class of software. For the mathematical problem in Computer Science, see Job Shop Scheduling. For other uses, see Scheduling (disambiguation). A job scheduler is a software application that is in charge of unattended… …   Wikipedia

  • Scheduling algorithm — In computer science, a scheduling algorithm is the method by which threads, processes or data flows are given access to system resources (e.g. processor time, communications bandwidth). This is usually done to load balance a system effectively or …   Wikipedia

  • Scheduling — Unter Scheduling (englisch für „Zeitplanerstellung“), auch Zeitablaufsteuerung genannt, versteht man die Erstellung eines Ablaufplanes (schedule), der Prozessen zeitlich begrenzt Ressourcen zuweist (Allokation). Scheduling findet hauptsächlich in …   Deutsch Wikipedia

  • Multiprocessor scheduling — In computer science, multiprocessor scheduling is an NP complete optimization problem. The problem statement is: Given a set J of jobs where job ji has length li and a number of processors mi, what is the minimum possible time required to… …   Wikipedia

  • Notation for theoretic scheduling problems — A convenient notation for theoretic scheduling problems was introduced by Ronald Graham, Eugene Lawler, Jan Karel Lenstra and Alexander Rinnooy Kan. It consists of three fields: α, β and γ. Each field may be a comma separated list of words. The α …   Wikipedia

  • Global Shop Solutions — is an Enterprise Resource Planning software (ERP) company that targets small to medium sized manufacturers, job shops, or make to order companies. Located in The Woodlands, Texas, Global Shop Solutions also has offices in Boston, Chicago, Los… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”