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.

This heuristic, or 'rule of thumb' procedure minimises the effect of the bottleneck.

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.

The objective is to determine the schedule that will produce the shortest makespan.

The due date, denoted dij, 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 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 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.

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.

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.

It is the lowest amount of time needed complete all of the jobs given these machine and precedence constraints.