Job-shop scheduling

Many variations of the problem exist, including the following:

• Machines can have duplicates (flexible job shop with duplicate machines) or belong to groups of identical machines (flexible job shop).[3]
• Machines can require a certain gap between jobs or no idle-time.
• Machines can have sequence-dependent setups.
• Objective function can be to minimize the makespan, the L_p norm, tardiness, maximum lateness etc. It can also be multi-objective optimization problem.
• Jobs may have constraints, for example a job i needs to finish before job j can be started (see workflow). Also, the objective function can be multi-criteria.[4]
• Set of jobs can relate to different set of machines.
• Deterministic (fixed) processing times or probabilistic processing times.

Since the traveling salesman problem is NP-hard, the job-shop problem with sequence-dependent setup is clearly also NP-hard since the TSP is a special case of the JSP with a single job (the cities are the machines and the salesman is the job).

The disjunctive graph[5] is one of the popular models used for describing the job-shop scheduling problem instances.[6]

A mathematical statement of the problem can be made as follows:

Let ${\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}}$ and ${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\}}$ be two finite sets. On account of the industrial origins of the problem, the ${\displaystyle \displaystyle M_{i}}$ are called machines and the ${\displaystyle \displaystyle J_{j}}$ are called jobs.

Let ${\displaystyle \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 ${\displaystyle x\in {\mathcal {X}}}$ may be written as ${\displaystyle n\times m}$ matrices, in which column ${\displaystyle \displaystyle i}$ lists the jobs that machine ${\displaystyle \displaystyle M_{i}}$ will do, in order. For example, the matrix

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

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

Suppose also that there is some cost function ${\displaystyle 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 ${\displaystyle C_{ij}:M\times J\to [0,+\infty ]}$, the cost/time for machine ${\displaystyle \displaystyle M_{i}}$ to do job ${\displaystyle \displaystyle J_{j}}$.

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

Scheduling efficiency can be defined for a schedule through the ratio of total machine idle time to the total processing time as below:

${\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk}}}$

Here ${\displaystyle l_{i}}$ is the idle time of machine ${\displaystyle i}$, ${\displaystyle C}$ is the makespan and ${\displaystyle m}$ is the number of machines. Notice that with the above definition, scheduling efficiency is simply the makespan normalized to the number of machines and the total processing time. This makes it possible to compare the usage of resources across JSP instances of different size.[7]

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 ${\displaystyle x_{\infty }\in {\mathcal {X}}}$ such that ${\displaystyle C(x_{\infty })=+\infty }$. In fact, it is quite simple to concoct examples of such ${\displaystyle x_{\infty }}$ by ensuring that two machines will deadlock, so that each waits for the output of the other's next step.

Graham had already provided the List scheduling algorithm in 1966, which is (2 − 1/m)-competitive, where m is the number of machines.[1] Also, it was proved that List scheduling is optimum online algorithm for 2 and 3 machines. The Coffman–Graham algorithm (1972) for uniform-length jobs is also optimum for two machines, and is (2 − 2/m)-competitive.[8][9] In 1992, Bartal, Fiat, Karloff and Vohra presented an algorithm that is 1.986 competitive.[10] A 1.945-competitive algorithm was presented by Karger, Philips and Torng in 1994.[11] In 1992, Albers provided a different algorithm that is 1.923-competitive.[12] Currently, the best known result is an algorithm given by Fleischer and Wahl, which achieves a competitive ratio of 1.9201.[13]

A lower bound of 1.852 was presented by Albers.[14] Taillard instances has an important role in developing job-shop scheduling with makespan objective.

In 1976 Garey provided a proof[15] that this problem is NP-complete for m>2, that is, no optimal solution can be computed in deterministic polynomial time for three or more machines (unless P=NP).

In 2011 Xin Chen et al. provided optimal algorithms for online scheduling on two related machines[16] improving previous results.[17]

Machine learning has been recently used to predict the optimal makespan of a JSP instance without actually producing the optimal schedule.[7] Preliminary results show an accuracy of around 80% when supervised machine learning methods were applied to classify small randomly generated JSP instances based on their optimal scheduling efficiency compared to the average.

Here is an example of a job-shop scheduling problem formulated in AMPL as a mixed-integer programming problem with indicator constraints:

param N_JOBS;
param N_MACHINES;

set JOBS ordered = 1..N_JOBS;
set MACHINES ordered = 1..N_MACHINES;

param ProcessingTime{JOBS, MACHINES} > 0;

param CumulativeTime{i in JOBS, j in MACHINES} =
   sum {jj in MACHINES: ord(jj) <= ord(j)} ProcessingTime[i,jj];

param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <> i2} =
   max {j in MACHINES}
     (CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]);

var end >= 0;
var start{JOBS} >= 0;
var precedes{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)} binary;

minimize makespan: end;

subj to makespan_def{i in JOBS}:
   end >= start[i] + sum{j in MACHINES} ProcessingTime[i,j];

subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   precedes[i1,i2] ==> start[i2] >= start[i1] + TimeOffset[i1,i2];

subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   !precedes[i1,i2] ==> start[i1] >= start[i2] + TimeOffset[i2,i1];

data;

param N_JOBS := 4;
param N_MACHINES := 4;

param ProcessingTime:
1 2 3 4 :=
1 4 2 1
2 3 6 2
3 7 2 3
4 1 5 8;

• Flow-shop scheduling is a similar problem but without the constraint that each operation must be done on a specific machine (only the order constraint is kept).
• Open-shop scheduling is a similar problem but also without the order constraint.

• University of Vienna Directory of methodologies, systems and software for dynamic optimization.
• Taillard instances
• Brucker P. Scheduling Algorithms. Heidelberg, Springer. Fifth ed. ISBN 978-3-540-24804-0