WikiMili The Free Encyclopedia

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.

**Job shops** are typically small manufacturing systems that handle job production, that is, custom/bespoke or semi-custom/bespoke manufacturing processes such as small to medium-size customer orders or batch jobs. Job shops typically move on to different jobs when each job is completed. Job shops machines are aggregated in shops by the nature of skills and technological processes involved, each shop therefore may contain different machines, which gives this production system processing flexibility, since jobs are not necessarily constrained to a single machine. In computer science the problem of job shop scheduling is considered strongly NP-hard.

A **heuristic technique**, often called simply a **heuristic**, is any approach to problem solving or self-discovery that employs a practical method, not guaranteed to be optimal, perfect, logical, or rational, but instead sufficient for reaching an immediate goal. Where finding an optimal solution is impossible or impractical, heuristic methods can be used to speed up the process of finding a satisfactory solution. Heuristics can be mental shortcuts that ease the cognitive load of making a decision. Examples that employ heuristics include using a rule of thumb, an educated guess, an intuitive judgment, a guesstimate, profiling, or common sense.

In engineering, a **bottleneck** is a phenomenon by which the performance or capacity of an entire system is severely limited by a single component. The component is sometimes called a **bottleneck point**. The term is metaphorically derived from the neck of a bottle, where the flow speed of the liquid is limited by its neck.

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.

- Make Graph
- Determine starting makespan

- Determine optimal sequence for bottleneck machine (Considering precedence constraints)
- Perform an iteration
- Lowest maximum lateness
- Branch and bound technique
- Include optimal sequence in graph

- Perform an iteration
- 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

- Perform further iterations

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.

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

**Branch and bound** is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores *branches* of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated *bounds* on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

Once the bottleneck has been determined, the path for the machine needs to be included in the drawing 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.

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 to the respective job, coming from comparing the processing 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 can be finished on the respective machine and still have enough time to finish the job on the proceeding machines within the makespan. The proceeding jobs are known from the precedence constraints. Draw out the new disjunctive constraints on your drawing (see Iteration 2). This is considered the second iteration.

Again, determine which machine is the new bottleneck. 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.

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.

In computer science, a **search algorithm** is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values. Specific applications of search algorithms include:

In telecommunication, a **convolutional code** is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to a data stream. The sliding application represents the 'convolution' of the encoder over the data, which gives rise to the term 'convolutional coding'. The sliding nature of the convolutional codes facilitates trellis decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity.

**Dijkstra's algorithm** is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

A **greedy algorithm** is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

In computer science, **A*** is a computer algorithm that is widely used in pathfinding and graph traversal, which is the process of finding a path between multiple points, called "nodes". It enjoys widespread use due to its performance and accuracy. However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, although other work has found A* to be superior to other approaches.

In numerical analysis, **hill climbing** is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.

The **Bottleneck traveling salesman problem** is a problem in discrete or combinatorial optimization. The problem is to find the Hamiltonian cycle in a weighted graph which minimizes the weight of the most weighty edge of the cycle. It was first formulated by Gilmore & Gomory (1964) with some additional constraints, and in its full generality by Garfinkel & Gilbert (1978).

In computer science, **instruction scheduling** is a compiler optimization used to improve instruction-level parallelism, which improves performance on machines with instruction pipelines. Put more simply, it tries to do the following without changing the meaning of the code:

**Iterative deepening A*** (**IDA***) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of iterative deepening depth-first search that borrows the idea to use a heuristic function to evaluate the remaining cost to get to the goal from the A* search algorithm. Since it is a depth-first search algorithm, its memory usage is lower than in A*, but unlike ordinary iterative deepening search, it concentrates on exploring the most promising nodes and thus does not go to the same depth everywhere in the search tree. Unlike A*, IDA* does not utilize dynamic programming and therefore often ends up exploring the same nodes many times.

**Pathfinding** or **pathing** is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding a shortest path on a weighted graph.

In computational phylogenetics, **tree alignment** is a computational problem concerned with producing multiple sequence alignments, or alignments of three or more sequences of DNA, RNA, or protein. Sequences are arranged into a phylogenetic tree, modeling the evolutionary relationships between species or taxa. The edit distances between sequences are calculated for each of the tree's internal vertices, such that the sum of all edit distances within the tree is minimized. Tree alignment can be accomplished using one of several algorithms with various trade-offs between manageable tree size and computational effort.

In operations research, **Johnson's rule** is a method of scheduling jobs in two work centers. Its primary objective is to find an optimal sequence of jobs to reduce makespan. It also reduces the amount of idle time between the two work centers. The method minimizes the makespan in the case of two work centers. Furthermore, the method finds the shortest makespan in the case of three work centers if additional constraints are met.

The genetic algorithm is an operational research method that may be used to solve scheduling problems in production planning.

**Job shop scheduling** or **the job-shop problem** (**JSP**) is an optimization problem in computer science and operations research in which jobs are assigned to resources at particular times. The most basic version is as follows: We are given *n* jobs *J*_{1}, *J*_{2}, ..., *J _{n}* of varying processing times, which need to be scheduled on

In graph theory and combinatorial optimization, a **closure** of a directed graph is a set of vertices with no outgoing edges. That is, the graph should have no edges that start within the closure and end outside the closure. The **closure problem** is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem. It may be used to model various application problems of choosing an optimal subset of tasks to perform, with dependencies between pairs of tasks, one example being in open pit mining.

**Flow shop scheduling** problems, are a class of scheduling problems with a workshop or group shop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines or with other resources *1,2,...,m* in compliance with given processing orders. Especially the maintaining of a continuous flow of processing tasks is desired with a minimum of *idle time* and a minimum of *waiting time*. Flow shop scheduling is a special case of job shop scheduling where there is strict order of all operations to be performed on all jobs. Flow shop scheduling may apply as well to production facilities as to computing designs.

In job shop scheduling and graph drawing, the **Coffman–Graham algorithm** is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When *W* = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/*W* times as many levels as necessary.

In graph algorithms, the **widest path problem** is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the **bottleneck shortest path problem** or the **maximum capacity path problem**. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible.

In the mathematical modeling of job shop scheduling problems, **disjunctive graphs** are a way of modeling a system of tasks to be scheduled and timing constraints that must be respected by the schedule. They are mixed graphs, in which vertices may be connected by both directed and undirected edges. The two types of edges represent constraints of two different types:

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

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.