In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan – the total length of the schedule (that is, when all the jobs have finished processing).
In the specific variant known as job-shop scheduling, each job consists of a set of operations O1, O2, ..., On which need to be processed in a specific order (known as precedence constraints).
A common relaxation is the flexible job shop, where each operation can be processed on any machine of a given set (the machines in each set are identical).
[1] The best problem instances for a basic model with a makespan objective are due to Taillard.
[2] In the standard three-field notation for optimal job scheduling problems, the job-shop variant is denoted by J in the first field.
Many variations of the problem exist, including the following: 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).
[citation needed] The disjunctive graph[5] is one of the popular models used for describing the job-shop scheduling problem instances.
The job-shop problem is to find an assignment of jobs
Scheduling efficiency can be defined for a schedule through the ratio of total machine idle time to the total processing time as below:
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
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.
[12] Currently, the best known result is an algorithm given by Fleischer and Wahl, which achieves a competitive ratio of 1.9201.
[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] The simplest form of the offline makespan minimisation problem deals with atomic jobs, that is, jobs that are not subdivided into multiple operations.
It is equivalent to packing a number of items of various different sizes into a fixed number of bins, such that the maximum bin size needed is as small as possible.
Dorit S. Hochbaum and David Shmoys presented a polynomial-time approximation scheme in 1987 that finds an approximate solution to the offline makespan minimisation problem with atomic jobs to any desired degree of accuracy.
[20] The steps of algorithm are as follows: Job Pi has two operations, of duration Pi1, Pi2, to be done on Machine M1, M2 in that sequence.
Johnson's method only works optimally for two machines.
However, since it is optimal, and easy to compute, some researchers have tried to adopt it for M machines, (M > 2.)
The idea is as follows: Imagine that each job requires m operations in sequence, on M1, M2 … Mm.
[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.