Shifting bottleneck heuristic

The Shifting Bottleneck Heuristic is a procedure intended to minimize the time it takes to do work, or specifically, the makespan in a job shop. The makespan is defined as the amount of time, from start to finish, to complete a set of multi-machine jobs where machine order is pre-set for each job. Assuming that the jobs are actually competing for the same resources (machines) then there will always be one or more resources that act as a 'bottleneck' in the processing. This heuristic, or 'rule of thumb' procedure minimises the effect of the bottleneck. The Shifting Bottleneck Heuristic is intended for job shops with a finite number of jobs and a finite number of machines.

Uses

Machine Sequence and Processing Times Example

The Shifting Bottleneck Heuristic is used in manufacturing and service industries that include job shops with constraints on the order that the machines must be used for each job. A good example of a service industry that may use this technique is a hospital. The different areas within a hospital, such as physical examination, x-ray booth, cat scan, or surgery, could all be considered machines for this particular application. A precedence constraint in this context is when one machine must be used before another machine on any given job (or patient). These types of problems with multiple machines are known to be computationally very difficult. The processing time of each job on each machine is given (see chart on right for an example). Job j being performed on machine i is denoted ij. It is assumed that each machine can only work on one job at a time. The objective is to determine the schedule that will produce the shortest makespan.

Procedure

Make graph
- Determine starting makespan
Determine optimal sequence for bottleneck machine (considering precedence constraints)
- Perform an iteration
  - Solve lowest maximum lateness problem
  - Include optimal sequence in graph
Determine optimal sequences for remaining machines (considering precedence and machine constraints)
- Perform further iterations
  - Conduct iterations until all machines have been accounted for
  - Draw out final graph
  - Determine final makespan

First graph

Original drawing

The first step is to draw out the precedence constraints in a graphical form called a graph (See Original Drawing picture). Each job originates at the "source", which we will label U on the graph. Each job will finish in a "sink" of jobs, which we will label V on the graph. Each row of nodes in the graph represents a job. Each node on the graph represents a task that is part of the job, the second number confirms the job being performed and the first number indicates what machine is being used for this task. At this point, the initial throughput time of each job should be calculated by adding up the processing times that the job takes on each of the machines (or rows). After the throughput time for each job has been calculated, the makespan for the system is determined by the longest throughput time of any individual job. This assumes no resource conflicts and gives a makespan of 22.

First iteration

Machine 1

Iteration 1

The next step is to determine which resource/machine is currently the bottleneck. This is done by considering the production time, denoted p_ij, that each job takes on each machine, the release time of each job on each respective machine, and the due date of each job for each respective machine. The release time, denoted r_ij, is determined by adding up the processing times of job j on the machines that precede machine i in the job order of job j. The due date, denoted d_ij, is determined by subtracting the processing times of job j on the machines succeeding the machine i in the job order from the makespan. Once all of this is determined, the minimum lateness for each machine needs to be determined. This is accomplished by finding the path for each machine that reduces the maximum lateness seen for all jobs on the respective machine. This can be done using a branch and bound technique for example. It can also be approximated using an other heuristic such as the earliest due date heuristic. Once the maximum lateness is determined for each of the respective machines, the machine with the largest maximum lateness is the bottleneck. If there is no maximum lateness on any of the machines, one can draw all of the machines’ optimal sequences in the job diagram. If there are two machines with the same maximum lateness, either one can be chosen for the bottleneck. All of this work is considered the first iteration.

Once the bottleneck has been determined, the path for the machine needs to be included in the graph of jobs (See Iteration 1 Drawing, where the colored arrows represent disjunctive constraints). These new paths can be considered the disjunctive constraints and they need to be taken into consideration when determining the new makespan. The disjunctive constraints are the machine constraints in our job shop. The new makespan will be the old makespan plus the maximum lateness of the machine determined to be the bottleneck.

Second iteration

Iteration 2

The next step is to perform a new analysis for each of the remaining machines. The differences now are there is a new makespan, and the precedence constraints need to be considered as well as the disjunctive constraints when determining the release date of each job on the machine. The longest path to get from the "source" U to the respective job, coming from comparing the release times of the preceding jobs for disjunctive constraints and precedence constraints, will be the new release date. The due dates will be the time that the given job needs be finished on the respective machine to still have enough time to finish the job on the proceeding machines within the makespan. This is the length of the longest path from the job to the "sink" V. The proceeding jobs are known from the precedence constraints.

Again, determine which machine is the new bottleneck. Add the new disjunctive constraints to the graph (see Iteration 2). This is considered the second iteration. The new makespan is the old makespan plus the maximum lateness from the new bottleneck. Again, if the maximum lateness on all machines is zero then use all the paths for the disjunctive constraints on the drawing and the makespan is still the same as it was before.

Further iterations

Iteration 3

This process is repeated until all machines have been accounted for or the maximum lateness is zero on all respective remaining machines. Each time the process is repeated, it is considered an iteration and all of the disjunctive constraints may be drawn on the job and machine diagram. For our example, the next iteration provided us with zero for the maximum lateness on machines 3 and 4, so their optimal sequences can be included in the drawing (see Iteration 3).

At this point the Shifting Bottleneck Heuristic is complete. The drawing should now include all precedence constraints and all disjunctive constraints. The final makespan is the original makespan plus all of the maximum latenesses from each of the respective bottlenecks. It is the lowest amount of time needed complete all of the jobs given these machine and precedence constraints.

External links

The shifting bottleneck procedure for job-shops with parallel machines

References

Pinedo, Michael. Planning and Scheduling in Manufacturing and Services. Springer Science+Business Media, LLC. 2005. Pages 87–93. ISBN 978-0-387-22198-4.