- Job-shop problem
The job-shop problem (JSP) is a problem in discrete or
combinatorial optimization , and is a generalization of the famoustravelling salesman problem . It is a prominent illustration of a class of problems incomputational complexity theory which are hard to solve.tatement of the problem
Let M = { M_{1}, M_{2}, dots, M_{m} } and J = { J_{1}, J_{2}, dots, J_{n} } be two
finite sets. On account of the industrial origins of the problem, the M_{i} are called machines and the J_{j} are called jobs.Let mathcal{X} 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{X} may be written as n imes m matrices, in which column i lists the jobs that machine M_{i} will do, in order. For example, the matrix
:x = egin{pmatrix} 1 & 2 \ 2 & 3 \ 3 & 1 end{pmatrix}
means that machine M_{1} will do the three jobs J_{1}, J_{2}, J_{3} in the order J_{1}, J_{2}, J_{3}, while machine M_{2} will do the jobs in the order J_{2}, J_{3}, J_{1}.
Suppose also that there is some cost function C : mathcal{X} o [0, + infty] . The cost function may be interpreted as a "total processing time", and may have some expression in terms of times C_{ij} : M imes J o [0, + infty] , the cost/time for machine M_{i} to do job J_{j}.
The job-shop problem is to find an assignment of jobs x in mathcal{X} such that C(x) is minimal.
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_{infty} in mathcal{X} such that C(x_{infty}) = + infty. In fact, it is quite simple to concoct examples of such x_{infty} 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 the JSP with m = 1 (the salesman is the machine and the cities are the jobs).
Wikimedia Foundation. 2010.