Job shop scheduling


Job shop 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 J1J2, ..., Jn of varying sizes, which need to be scheduled on m identical machines, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing). Mostly[citation needed], 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.[1] Best problem instances for basic model with makespan objective are due to Taillard.

Contents

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
  • Machines can have sequence-dependent setups
  • 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.[1] Also, it was proved that List scheduling is optimum online algorithm for 2 and 3 machines. The Coffman–Graham algorithm (1972) for uniform-length jobs is also optimum for two machines, and is (2 − 2/m)-competitive.[2][3] In 1992, Bartal, Fiat, Karloff and Vohra presented an algorithm that is 1.986 competitive.[4] A 1.945-competitive algorithm was presented by Karger, Philips and Torng in 1994.[5] In 1992, Albers provided a different algorithm that is 1.923-competitive.[6] Currently, the best known result is an algorithm given by Fleischer and Wahl, which achieves a competitive ratio of 1.9201.[citation needed]

A lower bound of 1.852 was presented by Albers.[7] Currently, best known lower bound is 1.88, which was presented by Rudin in 2001.[citation needed] Taillard instances [7] has an important role in developing job shop scheduling with makespan objective.

In 1976 Garey provided a proof[8] that this problem is NP-complete for m>2, that is, no optimal solution can be computed in polynomial time for three or more machines (unless P=NP).

Offline makespan minimisation

Atomic jobs

The simplest form of the offline makespan minimisation problem deals with atomic jobs, that is, jobs that are not subdivided into multiple operations. It is equivalent to packing a number of items of various different sizes into a fixed number of bins, such that the maximum bin size needed is as small as possible. (If instead the number of bins is to be minimised, and the bin size is fixed, the problem becomes a different problem, known as the bin packing problem.)

Hochbaum and Shmoys presented a polynomial-time approximation scheme in 1987 that finds an approximate solution to the offline makespan minimisation problem with atomic jobs to any desired degree of accuracy.[9]

Jobs consisting of multiple operations

The basic form of the problem of scheduling jobs with multiple (M) operations, over M machines, such that all of the first operations must be done on the first machine, all of the second operations on the second, etc., and a single job cannot be performed in parallel, is known as the open shop scheduling problem. Various algorithms exist, including genetic algorithms.[10]

Johnson's algorithm

A heuristic algorithm by S.M. Johnson can be used to solve the case of a 2 machine N job problem when all jobs are to be processed in the same order.[11] The steps of algorithm are as follows:

Job Pi has two operations, of duration Pi1, Pi2, to be done on Machine M1, M2 in that sequence.

  • Step 1. List A = { 1, 2, …, N }, List L1 = {}, List L2 = {}.
  • Step 2. From all available operation durations, pick the minimum.

If the minimum belongs to Pk1,

Remove K from list A; Add K to end of List L1.

If minimum belongs to Pk2,

Remove K from list A; Add K to beginning of List L2.

  • Step 3. Repeat Step 2 until List A is empty.
  • Step 4. Join List L1, List L2. This is the optimum sequence.

Johnson's method only works optimally for two machines. However, since it is optimal, and easy to compute, some researchers have tried to adopt it for M machines, (M > 2.)

The idea is as follows: Imagine that each job requires m operations in sequence, on M1, M2 … Mm. We combine the first m/2 machines into an (imaginary) Machining center, MC1, and the remaining Machines into a Machining Center MC2. Then the total processing time for a Job P on MC1 = sum( operation times on first m/2 machines), and processing time for Job P on MC2 = sum(operation times on last m/2 machines).

By doing so, we have reduced the m-Machine problem into a Two Machining center scheduling problem. We can solve this using Johnson's method.

See also

References

  1. ^ a b Graham, R. (1966). "Bounds for certain multiprocessing anomalies" (PDF). Bell System Technical Journal 45: 1563–1581. http://www.math.ucsd.edu/~ronspubs/66_04_multiprocessing.pdf. 
  2. ^ Coffman, E. G., Jr.; Graham, R. L. (1972), "Optimal scheduling for two-processor systems", Acta Informatica 1: 200–213, MR0334913, http://www.math.ucsd.edu/~ronspubs/72_04_two_processors.pdf .
  3. ^ Lam, Shui; Sethi, Ravi (1977), "Worst case analysis of two scheduling algorithms", SIAM Journal on Computing 6 (3): 518–536, doi:10.1137/0206037, MR0496614 .
  4. ^ Bartal, Y.; A. Fiat, H. Karloff, R. Vohra (1992). "New Algorithms for an Ancient Scheduling Problem". Proc. 24th ACM Symp.. Theory of Computing. pp. 51–58. doi:10.1145/129712.129718. http://doi.acm.org/10.1145/129712.129718. 
  5. ^ Karger, D.; S. Phillips, E. Torng (1994). "A Better Algorithm for an Ancient Scheduling Problem". Proc. Fifth ACM Symp.. Discrete Algorithms. http://portal.acm.org/citation.cfm?doid=314464.314487. 
  6. ^ Albers, Susanne; Torben Hagerup (1992). "Improved parallel integer sorting without concurrent writing". Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms. pp. 463–472. http://portal.acm.org/citation.cfm?id=139404.139491. 
  7. ^ Albers, Susanne (1999). "Better bounds for online scheduling". SIAM Journal of Computing 29 (2): 459–473. doi:10.1137/S0097539797324874. 
  8. ^ Garey, M.R. (1976). "The Complexity of Flowshop and Jobshop Scheduling". Mathematics of Operations Research 1 (2): 117–129. doi:10.1287/moor.1.2.117. http://www.jstor.org/pss/3689278. 
  9. ^ Hochbaum, Dorit; Shmoys, David (1987). "Using dual approximation algorithms for scheduling problems: theoretical and practical results" (PDF). Journal of the ACM 34 (1): 144–162. doi:10.1145/7531.7535. http://www.columbia.edu/~cs2035/courses/ieor6400.F07/hs.pdf. 
  10. ^ Khuri, Sami; Miryala, Sowmya Rao (1999). "Genetic Algorithms for Solving Open Shop Scheduling Problems". Proceedings of the 9th Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence. London: Springer Verlag. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.4699&rep=rep1&type=pdf. Retrieved 11 April 2011. 
  11. ^ S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.

7. Taillard instances [1]

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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… …   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