Atomic jobs 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. (If instead the number of bins is to be minimised, and the bin size is fixed, the problem becomes a different problem, known as the
bin packing problem.)
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.
Jobs consisting of multiple operations The basic form of the problem of scheduling jobs with multiple (M) operations, over M machines, such that all of the first operations must be done on the first machine, all of the second operations on the second, etc., and a single job cannot be performed in parallel, is known as the
flow-shop scheduling problem. Various algorithms exist, including
genetic algorithms.
Johnson's algorithm A heuristic algorithm by S. M. Johnson can be used to solve the case of a 2 machine N job problem when all jobs are to be processed in the same order. 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. •
Step 1. List A = { 1, 2, …, N }, List L1 = {}, List L2 = {}. •
Step 2. From all available operation durations, pick the minimum. If the minimum belongs to Pk1, Remove K from list A; Add K to end of List L1. If minimum belongs to Pk2, Remove K from list A; Add K to beginning of List L2. •
Step 3. Repeat Step 2 until List A is empty. •
Step 4. Join List L1, List L2. This is the optimum 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. We combine the first
m/2 machines into an (imaginary) Machining center, MC1, and the remaining Machines into a Machining Center MC2. Then the total processing time for a Job P on MC1 = sum (operation times on first
m/2 machines), and processing time for Job P on MC2 = sum(operation times on last
m/2 machines). By doing so, we have reduced the m-Machine problem into a Two Machining center scheduling problem. We can solve this using Johnson's method. == Makespan prediction ==