HOME

TheInfoList



OR:

Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an
optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...
in
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
and
operations research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
. It is a variant of
optimal job scheduling Optimal job scheduling is a class of optimization problems related to scheduling. The inputs to such problems are a list of ''jobs'' (also called ''processes'' or ''tasks'') and a list of ''machines'' (also called ''processors'' or ''workers''). The ...
. In a general job scheduling problem, we are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of varying processing times, which need to be scheduled on ''m'' machines with varying processing power, while trying to minimize the
makespan In operations research, the makespan of a project is the length of time that elapses from the start of work to the end. This type of multi-mode resource constrained project scheduling problem (MRCPSP) seeks to create the shortest logical project sc ...
– the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as ''job-shop scheduling'', each job consists of a set of ''operations'' ''O''1, ''O''2, ..., ''On'' which need to be processed in a specific order (known as ''precedence constraints''). Each operation has a ''specific machine'' that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop, where each operation can be processed on any machine of a given ''set'' (the machines in each set are identical). The name originally came from the scheduling of jobs in a
job shop Job shops are typically small manufacturing systems that handle job production, that is, custom/bespoke or semi-custom/bespoke manufacturing processes such as small to medium-size customer orders or batch jobs. Job shops typically move on to diffe ...
, but the theme has wide applications beyond that type of instance. This problem is one of the best known
combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
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. In the standard three-field notation for optimal job scheduling problems, the job-shop variant is denoted by J in the first field. For example, the problem denoted by " J3, p_, C_\max" is a 3-machines job-shop problem with unit processing times, where the goal is to minimize the maximum completion time.


Problem variations

Many variations of the problem exist, including the following: * Machines can have duplicates (flexible job shop with duplicate machines) or belong to groups of identical machines (flexible job shop). * Machines can require a certain gap between jobs or no idle-time. * Machines can have sequence-dependent setups. * Objective function can be to minimize the makespan, the ''Lp'' norm, tardiness, maximum lateness etc. It can also be multi-objective optimization problem. * Jobs may have constraints, for example a job ''i'' needs to finish before job ''j'' can be started (see
workflow A workflow consists of an orchestrated and repeatable pattern of activity, enabled by the systematic organization of resources into processes that transform materials, provide services, or process information. It can be depicted as a sequence of ...
). Also, the objective function can be multi-criteria. * Set of jobs can relate to different set of machines. * Deterministic (fixed) processing times or probabilistic processing times.


NP-hardness

Since the
traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
is
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
, the job-shop problem with sequence-dependent setup is clearly also NP-hard since the TSP is a special case of the JSP with a single job (the cities are the machines and the salesman is the job).


Problem representation

The
disjunctive graph In the mathematical modeling of job shop scheduling problems, disjunctive graphs are a way of modeling a system of tasks to be scheduled and timing constraints that must be respected by the schedule. They are mixed graphs, in which vertices (repres ...
is one of the popular models used for describing the job-shop scheduling problem instances. A mathematical statement of the problem can be made as follows: Let M = \ and J = \ be two
finite Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marke ...
sets. On account of the industrial origins of the problem, the \displaystyle M_ are called machines and the \displaystyle J_ are called jobs. Let \displaystyle \ \mathcal denote the set of all sequential assignments of jobs to machines, such that every job is done by every machine exactly once; elements x \in \mathcal may be written as n \times m matrices, in which column \displaystyle i lists the jobs that machine \displaystyle M_ will do, in order. For example, the matrix : x = \begin 1 & 2 \\ 2 & 3 \\ 3 & 1 \end means that machine \displaystyle M_ will do the three jobs \displaystyle J_, J_, J_ in the order \displaystyle J_, J_, J_, while machine \displaystyle M_ will do the jobs in the order \displaystyle J_, J_, J_. Suppose also that there is some cost function C : \mathcal \to , + \infty/math>. The cost function may be interpreted as a "total processing time", and may have some expression in terms of times C_ : M \times J \to , + \infty/math>, the cost/time for machine \displaystyle M_ to do job \displaystyle J_. The job-shop problem is to find an assignment of jobs x \in \mathcal such that \displaystyle C(x) is a minimum, that is, there is no y \in \mathcal such that \displaystyle C(x) > C(y).


Scheduling efficiency

Scheduling efficiency can be defined for a schedule through the ratio of total machine idle time to the total processing time as below: C'=1+= Here l_i is the idle time of machine i, C is the makespan and m is the number of machines. Notice that with the above definition, scheduling efficiency is simply the makespan normalized to the number of machines and the total processing time. This makes it possible to compare the usage of resources across JSP instances of different size.


The problem of infinite cost

One of the first problems that must be dealt with in the JSP is that many proposed solutions have infinite cost: i.e., there exists x_ \in \mathcal such that C(x_) = + \infty. In fact, it is quite simple to concoct examples of such x_ by ensuring that two machines will
deadlock In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lo ...
, so that each waits for the output of the other's next step.


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 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. The algorithm chooses ...
(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. Taillard instances has an important role in developing job-shop scheduling with makespan objective. In 1976 Garey provided a proof that this problem is
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
for m>2, that is, no optimal solution can be computed in deterministic polynomial time for three or more machines (unless
P=NP The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used abov ...
). In 2011 Xin Chen et al. provided optimal algorithms for online scheduling on two related machines improving previous results.


Offline makespan minimization


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 The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has ma ...
.)
Dorit S. Hochbaum Dorit S. Hochbaum is a professor of industrial engineering and operations research at the University of California, Berkeley.David Shmoys David Bernard Shmoys (born 1959) is a Professor in 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 1 ...
presented a
polynomial-time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an insta ...
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
flow-shop scheduling Flow-shop scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of vary ...
problem. Various algorithms exist, including
genetic algorithm In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to gene ...
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.S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68. 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 = , 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.


Makespan prediction

Machine learning has been recently used to ''predict'' the optimal makespan of a JSP instance without actually producing the optimal schedule. Preliminary results show an accuracy of around 80% when supervised machine learning methods were applied to classify small randomly generated JSP instances based on their optimal scheduling efficiency compared to the average.


Example

Here is an example of a job-shop scheduling problem formulated in
AMPL AMPL (A Mathematical Programming Language) is an algebraic modeling language to describe and solve high-complexity problems for large-scale mathematical computing (i.e., large-scale optimization and scheduling-type problems). It was developed ...
as a mixed-integer programming problem with indicator constraints: param N_JOBS; param N_MACHINES; set JOBS ordered = 1..N_JOBS; set MACHINES ordered = 1..N_MACHINES; param ProcessingTime > 0; param CumulativeTime = sum ProcessingTime ,jj param TimeOffset = max (CumulativeTime 1,j- CumulativeTime 2,j+ ProcessingTime 2,j; var end >= 0; var start >= 0; var precedes binary; minimize makespan: end; subj to makespan_def: end >= start + sum ProcessingTime ,j subj to no12_conflict: precedes 1,i2

> start 2>= start 1+ TimeOffset 1,i2 subj to no21_conflict: !precedes 1,i2

> start 1>= start 2+ TimeOffset 2,i1 data; param N_JOBS := 4; param N_MACHINES := 4; param ProcessingTime: 1 2 3 4 := 1 4 2 1 2 3 6 2 3 7 2 3 4 1 5 8;


Related problems

*
Flow-shop scheduling Flow-shop scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of vary ...
is a similar problem but without the constraint that each operation must be done on a specific machine (only the order constraint is kept). *
Open-shop scheduling Open-shop scheduling or open-shop scheduling problem (OSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given ''n'' jobs ''J''1,  ...
is a similar problem but also without the order constraint.


See also

*
Disjunctive graph In the mathematical modeling of job shop scheduling problems, disjunctive graphs are a way of modeling a system of tasks to be scheduled and timing constraints that must be respected by the schedule. They are mixed graphs, in which vertices (repres ...
*
Dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. I ...
* Genetic algorithm scheduling *
List of NP-complete problems This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in no way comprehensive. Many problems of this type can be found in . ...
*
Optimal control Optimal control theory is a branch of mathematical optimization that deals with finding a control for a dynamical system over a period of time such that an objective function is optimized. It has numerous applications in science, engineering and ...
* Scheduling (production processes)


References


External links


University of Vienna
Directory of methodologies, systems and software for dynamic optimization.
Taillard instances
* ''Brucker P.'
Scheduling Algorithms
Heidelberg, Springer. Fifth ed. {{Scheduling problems Optimal scheduling pt:Escalonamento de Job Shop