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. 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. 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.