Job-shop problem

El directorio enciclopédico desde la Wikipedia.

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 $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 \times m$ matrices, in which column $i$ lists the jobs that machine $M i$ will do, in order. For example, the matrix

$x = \begin{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} \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 $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.

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

Página espejo de la Wikipedia

Directorio de Enlaces Directorio dmoz Directorio espejo dmoz Pedro Bernardo