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, ..., ''J
n'' 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, ..., ''O
n'' 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,
,
" 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
and
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
are called machines and the
are called jobs.
Let
denote the set of all sequential assignments of jobs to machines, such that every job is done by every machine exactly once; elements
may be written as
matrices, in which column
lists the jobs that machine
will do, in order. For example, the matrix
:
means that machine
will do the three jobs
in the order
, while machine
will do the jobs in the order
.
Suppose also that there is some cost function