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.

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 $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 $\displaystyle M_{i}$ are called machines and the $\displaystyle J_{j}$ are called jobs.

Let $\displaystyle \ \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 $\displaystyle i$ lists the jobs that machine $\displaystyle M_{i}$ will do, in order. For example, the matrix

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

means that machine $\displaystyle M_{1}$ will do the three jobs $\displaystyle J_{1}, J_{2}, J_{3}$ in the order $\displaystyle J_{1}, J_{2}, J_{3}$, while machine $\displaystyle M_{2}$ will do the jobs in the order $\displaystyle J_{2}, J_{3}, J_{1}$.

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 $\displaystyle M_{i}$ to do job $\displaystyle J_{j}$.

The job-shop problem is to find an assignment of jobs $x \in \mathcal{X}$ such that $\displaystyle C(x)$ is a minimum, that is, there is no $y \in \mathcal{X}$ such that $\displaystyle C(x) > C(y)$.

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 special case of the JSP with $m = 1$ (the salesman is the machine and the cities are the jobs).

See also

• Job shop scheduling
• List of NP-complete problems