Job-shop problem

From Wikipedia, the free encyclopedia

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.

[edit] Statement 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 Mi are called machines and the Jj 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 \times m matrices, in which column i lists the jobs that machine Mi will do, in order. For example, the matrix

x = \begin{pmatrix} 1 & 2 \\ 2 & 3 \\ 3 & 1 \end{pmatrix}

means that machine M1 will do the three jobs J1,J2,J3 in the order J1,J2,J3, while machine M2 will do the jobs in the order J2,J3,J1.

Suppose also that there is some cost function C : \mathcal{X} \to [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 \times J \to [0, + \infty], the cost/time for machine Mi to do job Jj.

The job-shop problem is to find an assignment of jobs x \in \mathcal{X} such that C(x) is minimal.

[edit] 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.

[edit] 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).

Languages