Job Shop Scheduling
Encyclopedia
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 makespan. The makespan is 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.
Best problem instances for basic model with makespan objective are due to Taillard.
(1972) for uniform-length jobs is also optimum for two machines, and is -competitive. 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.
Taillard instances [7] has an important role in developing job shop scheduling with makespan objective.
In 1976 Garey provided a proof 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).
.)
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.
s.
Job Pi has two operations, of duration Pi1, Pi2, to be done on Machine M1, M2 in that sequence.
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.
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.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
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 makespan. The makespan is 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
Online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...
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
Competitive analysis (online algorithm)
Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance...
was presented, by Graham in 1966.
Best problem instances for basic model with makespan objective are due to Taillard.
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 -competitive, where m is the number of machines. Also, it was proved that List scheduling is optimum online algorithm for 2 and 3 machines. The Coffman–Graham algorithmCoffman–Graham algorithm
In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels...
(1972) for uniform-length jobs is also optimum for two machines, and is -competitive. 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.
Taillard instances [7] has an important role in developing job shop scheduling with makespan objective.
In 1976 Garey provided a proof that this problem is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
for m>2, that is, no optimal solution can be computed in polynomial time for three or more machines (unless P=NP).
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 problemBin packing problem
In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used....
.)
Hochbaum and Shmoys
David Shmoys
David Shmoys is currently a Professor in both the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984...
presented a polynomial-time approximation scheme
Polynomial-time approximation scheme
In computer science, a polynomial-time approximation scheme is a type of approximation algorithm for optimization problems ....
in 1987 that finds an approximate solution to the offline makespan minimisation problem with atomic jobs to any desired degree of accuracy.
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 algorithmGenetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s.
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. 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
- Dynamic programmingDynamic programmingIn mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
- Optimal controlOptimal controlOptimal control theory, an extension of the calculus of variations, is a mathematical optimization method for deriving control policies. The method is largely due to the work of Lev Pontryagin and his collaborators in the Soviet Union and Richard Bellman in the United States.-General method:Optimal...
- Genetic algorithm schedulingGenetic algorithm schedulingTo be competitive, corporations must minimize inefficiencies and maximize productivity. In manufacturing, productivity is inherently linked to how well you can optimize the resources you have, reduce waste and increase efficiency. Finding the best way to maximize efficiency in a manufacturing...
- Scheduling (production processes)Scheduling (production processes)Scheduling is an important tool for manufacturing and engineering, where it can have a major impact on the productivity of a process. In manufacturing, the purpose of scheduling is to minimize the production time and costs, by telling a production facility when to make, with which staff, and on...
- List of NP-complete problems
External links
- University of Vienna Directory of methodologies, systems and software for dynamic optimization.