Job-shop problem
Encyclopedia
The job-shop problem is a problem in discrete
or combinatorial optimization
, and is a generalization of the famous travelling salesman problem
. It is a prominent illustration of a class of problems in computational complexity theory
which are hard to solve.
Although a job can have any number of operations, the most common formulation of the job shop problem specifies that each job has exactly 'n' operations, one on each machine.
Job shop process differs from flow shop process that the flow of work is not unidirectional in job shop , hence it is one of the complex scheduling problems.
and 
be two finite 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
. The cost function may be interpreted as a "total processing time", and may have some expression in terms of times 
, the cost/time for machine 
to do job 
.
The job-shop problem is to find an assignment of jobs
such that 
is a minimum, that is, there is no 
such that 
.
such that 
. In fact, it is quite simple to concoct examples of such 
by ensuring that two machines will deadlock
, so that each waits for the output of the other's next step.
is NP-hard (as it is), then the job-shop problem is clearly also NP-hard, since the TSP is the JSP with
(the salesman is the machine and the cities are the jobs).
Discrete optimization
Discrete optimization is a branch of optimization in applied mathematics and computer science.As opposed to continuous optimization, the variables used in the mathematical program are restricted to assume only discrete values, such as the integers.Two notable branches of discrete optimization...
or combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
, and is a generalization of the famous travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
. It is a prominent illustration of a class of problems in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
which are hard to solve.
Description of the problem
A number of jobs have to be done and every job consist of using a number of machines for a certain amount of time. The problem is to find the best planning to do all the jobs on all the different machines in the shortest period of time.Although a job can have any number of operations, the most common formulation of the job shop problem specifies that each job has exactly 'n' operations, one on each machine.
Job shop process differs from flow shop process that the flow of work is not unidirectional in job shop , hence it is one of the complex scheduling problems.
Statement of the problem
Let and be two finite 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
. The cost function may be interpreted as a "total processing time", and may have some expression in terms of times , the cost/time for machine to do job .The job-shop problem is to find an assignment of jobs
such that is a minimum, that is, there is no such that .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 such that . In fact, it is quite simple to concoct examples of such by ensuring that two machines will deadlockDeadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
, so that each waits for the output of the other's next step.
NP-hardness
If one already knows that the travelling salesman problemTravelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
is NP-hard (as it is), then the job-shop problem is clearly also NP-hard, since the TSP is the JSP with
(the salesman is the machine and the cities are the jobs).See also
- Job shop schedulingJob Shop SchedulingJob 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:...
- List of NP-complete problems