science

Shifting bottleneck heuristic

Shifting bottleneck heuristic is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Shifting bottleneck heuristic rather than just read about it. In short: 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.

Key takeaways

Shifting bottleneck heuristic belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Shifting bottleneck heuristic to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Shifting bottleneck heuristic from memory before moving on to harder problems.

Reference excerpt

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

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

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

The next step is to determine which resource/machine is currently the bottleneck. This is done by considering the production time, denoted pij, 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 rij, 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 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 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

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

… excerpt ends here. Continue reading the full article.

Illustrations

Worked examples

Example 1 — a first encounter with Shifting bottleneck heuristic

Start with the simplest possible case. Write down what Shifting bottleneck heuristic claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Shifting bottleneck heuristic before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Shifting bottleneck heuristic ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Shifting bottleneck heuristic

In research: Shifting bottleneck heuristic appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Shifting bottleneck heuristic in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Shifting bottleneck heuristic is common in secondary-school and first-year university syllabi. It links to neighbouring topics Production planning, Queue management, so understanding it makes those chapters shorter.
In everyday life: Look for Shifting bottleneck heuristic outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Shifting bottleneck heuristic” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Shifting bottleneck heuristic in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Shifting bottleneck heuristic means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Shifting bottleneck heuristic out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Shifting bottleneck heuristic in simple terms?

Why does Shifting bottleneck heuristic matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Shifting bottleneck heuristic?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Shifting bottleneck heuristic.