Job-shop problem

From formulasearchengine
Jump to navigation Jump to search

{{ safesubst:#invoke:Unsubst||$N=Unreferenced |date=__DATE__ |$B= {{#invoke:Message box|ambox}} }} {{#invoke:Hatnote|hatnote}} The job-shop problem (JSP) 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.

Description of the problem

A number of jobs have to be done and every job consists 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.

The job shop process differs from flow shop process in that the flow of work is not unidirectional in job shop, hence it is one of the complex scheduling problems.

References

1) principles of sequencing and scheduling by Kenneth R Baker et al.

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 deadlock, so that each waits for the output of the other's next step.

NP-hardness

If one already knows that the travelling salesman problem is NP-hard (as it is), then the job-shop problem is clearly also NP-hard, since the TSP is special case of the JSP with (the salesman is the machine and the cities are the jobs).

See also

de:Scheduling#Scheduling-Probleme