Job-shop problem

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.

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

:

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).