Identification approach for bottleneck clusters in a job shop based on theory of constraints and sensitivity analysis

Abstract

Manufacturing systems are constrained by one or more bottlenecks. Reducing bottlenecks improves the entire system. Finding bottlenecks, however, is a difficult task. In this study, a new bottleneck detection method based on theory of constrains and sensitivity analysis is presented to overcome the disadvantages of existing bottleneck identification methods for a job shop. First, a bottleneck index matrix is obtained by examining the sensitivity of system production performance to the capacity of each machine. Technique for order preference by similarity to ideal solution is then employed to calculate the comprehensive bottleneck index of each machine. Based on the calculation result, bottleneck machine clusters under different hierarchies are obtained through hierarchical cluster analysis. The designed identification approach, as a prior-to-run method, can identify bottleneck machine clusters under different hierarchies before the overall system circulation, thereby providing good guidance for subsequent production optimization. Finally, a set of job-shop scheduling problem benchmarks with different scales is selected for comparison between the proposed approach and existing approaches, such as, the shifting bottleneck detection method, the bottleneck detection method based on orthogonal experiment, and the bottleneck cluster identification method. By comparison, the proposed approach is proven to be credible and superior.

Keywords

Job shop bottleneck identification theory of constraints sensitivity analysis hierarchical cluster

Introduction

The production volatility and processing dependency of production systems, as well as limited manufacturing resources, inevitably lead to bottlenecks that restrict the maximization of system throughput.¹ Each manufacturing system has bottlenecks that constrain its performance. According to theory of constraints (TOC), bottlenecks control the circulation of the entire system; the output rate of bottlenecks determines that of the system.² In many studies,^3–5 bottlenecks have been regarded as important characteristic information that may be utilized to accelerate the appearance of the optimal scheduling solution. In most situations, the final throughput of manufacturing systems can be improved within a relatively short time if bottleneck machines are well scheduled and controlled. Therefore, identifying system bottlenecks rapidly and accurately is a key to bottleneck management and a prerequisite to production management and process control. However, how to define the bottleneck and how to design an easily implemented bottleneck detection method are still problematic at present.

Finding bottlenecks is a difficult task. Cox and Spencer,⁶ for example, simply recommend that “the best approach is often to go to the production floor and ask knowledgeable employees.” Several traditional approaches define and identify bottlenecks through production features, such as equipment load and queue lengths of unprocessed jobs in front of each machine. The entity with the highest load^5,7 or the longest queue length^8,9 is considered to be the system bottleneck. This method is simple and can be implemented easily. However, in cases wherein the utilizations of different machines are the same or very similar or the buffers of several machines overflow simultaneously, identifying which machine is the bottleneck is difficult. In addition, in some systems, machines with the highest load are not the real bottlenecks.^10,11 Machine load can mostly be regarded as a priori information in bottleneck identification.

Some system-theoretical approaches have been proposed for bottleneck detection. Li et al.¹² proposed a data driven bottleneck detection method which utilized the blockage and starvation probabilities and buffer content records in production line to detect bottleneck. Sengupta et al.¹³ analyzed the inter-departure time from different machines to identify and rank the bottlenecks. The machine with the minimum total time spent in blocked-up and blocked-down states is the number one bottleneck machine. Ching et al.¹⁴ presented a bottleneck detection method using the frequencies of machine blockages and starvations in assembly systems. These system-theoretical approaches usually need to accumulate and process a lot of production data to detect bottlenecks, such as the blockage possibilities/time/frequencies or the starvation possibilities/time/frequencies of each machine, and the inter-departure time of each machine. They can detect bottlenecks only if manufacturing systems have run for a long time. The bottleneck detection process of system-theoretical approaches is very complicated. Usually they are used in production lines that consist of machines arranged in consecutive order and buffers separating each of the two adjacent machines. It is not easy for the system-theoretical bottleneck detection approaches to be implemented in the more complex job-shop environment.

Roser et al.^15,16 divided all possible states of machines into two groups, being either active states or inactive states and proposed the shifting bottleneck detection method (SB-DM). The machine with the longest average active period is considered to be the bottleneck. This method can be easily implemented and is reliable in detecting bottlenecks in a job shop. However, it requires a long time to obtain the information describing the change in the status of the different machines.

Chiang et al.^17,18 and Kuo et al.^19,20 employed sensitivity analysis to identify bottlenecks in production lines. The bottleneck in a production line is understood as a machine that impedes system performance in the strongest manner. The difficulty of sensitivity analysis rapidly increases with system complexity, thereby limiting its application in complex systems, such as a job shop; this method is only used in a flow shop currently. Kasemset et al.⁷ also mentioned a sensitivity index. After identifying the system bottleneck candidates by measuring a set of indicators of each machine, including utilization rate, production bottleneck rate, and processing and utilization factors, the judgment whether multiple bottlenecks exist was performed by adding bottleneck candidates and measuring the corresponding effect on system output. The sensitivity index was used in this study only to determine the existence of multiple bottlenecks.

Most existing bottleneck detection methods are posterior-to-run approaches which detect bottlenecks after a production system has run or the scheduling scheme to be used has already been generated. Consequently, the guidance of the obtained bottleneck knowledge to production optimization is greatly weakened. Zhai et al.^10,21 proposed a prior-to-run identification method based on orthogonal experiment Bottleneck Detection Method based on Orthogonal Experiment (BDM-OE); this method can locate system bottlenecks before production task execution by performing typical orthogonal experiments constructed by orthogonal layouts and dispatching rules. However, the reliability of the results greatly depends on whether the orthogonal layouts used are appropriate. Constructing suitable orthogonal layouts for cases that consist of numbers of machines is a complex and difficult task. In addition, different orthogonal layouts must be created for different cases. These disadvantages greatly weaken the adaptability and flexibility of this method. Zhang and Wu^22,23 also designed a prior-to-run bottleneck identification method, which is based on constraint transformation for job-shop scheduling. A new optimization model which relaxed the capacity constraints for the machines of the original scheduling problem was initially proposed. A simulated annealing algorithm was then applied to solve the newly defined model. Based on the optimization result, the bottleneck characteristic value of each machine was calculated to identify system bottlenecks before manufacturing systems run. However, the newly defined optimization model, like the original scheduling problem, is also a combinatorial optimization problem. Thus, obtaining its optimal solution, which is the foundation of bottleneck detection, is a difficult task. This greatly reduces the efficiency of the method.

In this study, a new prior-to-run bottleneck detection method for a job shop is proposed according to the basic principle that bottlenecks control the operation of the entire system. The method is implemented by performing sensitivity analysis on the relationship between the capacity of each machine and the corresponding outcome objective values by analyzing the simulation data of scheduling problems. For different production systems, this approach can rapidly and simply identify bottleneck machine clusters under different hierarchies by performing a unified measurement on the sensitivity of system production performance to machine capacity before task execution, and thus it provides good guidance for subsequent production optimization.

Bottleneck machine identification

Definition of bottleneck machines

In a job shop, factors that affect system performance can be divided into internal factors (e.g. machine capacities and process routings), external factors (e.g. raw material supply, production tasks change, and order delivery time), and random factors (e.g. equipment failure and personnel changes). Without considering the effects of external and random factors because of their high unpredictability, internal factors, particularly machine capacities, have significant and direct effect on system performance. In practical scheduling problems, there often exist machines with such properties: compared with other machines, these machines can produce a more significant impact on the final scheduling performance. In other words, in the event that the capacities of other machines are all fixed, moderate changes of the capacity of this machine will lead to comparatively larger variations of the final scheduling objective value, which indicates that the room for optimization and improvement is also relatively large for such machines. Machines with such characteristics are referred to as “bottleneck machines” in this study and defined as follows.

Definition 1

Consider m is the number of machines in a certain production system. Let c_i (i = 1, 2, …, m) denote the production capacity of machine i under certain production tasks, and f denote the value of one of the scheduling objectives that measure system performance. The sensitivity of f to c_i can be calculated by equation (1)

e_{i} = | \frac{Δ f}{Δ c_{i}} |, i = 1, 2, \dots, m

(1)

According to TOC, e_i quantifiably describes the likelihood that machine i is the bottleneck and is referred to as bottleneck index.

Definition 2

If $e_{i} > e_{j}$ , $\forall j \neq i$ , machine i is defined as a bottleneck machine.

Calculation of bottleneck index matrix

Based on the preceding explanation, a bottleneck machine identification method is developed by analyzing the simulation data of scheduling problems. The algorithm performs sensitivity analysis on the relationship between the capacity of each machine and the corresponding outcome objective values.

To calculate the bottleneck index of each machine, capacity variation $Δ c_{i}$ in Definition 1 needs to be quantitatively measured. In practice, one machine frequently undertakes different processing tasks. Thus, directly and uniformly measuring its capacity variation is difficult. While the changes in machine capacity will lead to the alteration of the processing times of the processes on this machine, the time alteration can reflect capacity change. A longer processing time indicates the capacity is reduced, whereas a shorter processing time indicates the capacity is improved. Therefore, machine capacity is indirectly changed in the study by altering the processing times of all the processes on this machine. The corresponding changes in production objective values can then be measured, and the bottleneck index can be obtained.

In a determined scheduling case (i.e. the number of jobs, number of machines, processing route of each job, and processing time of each process are all determined), assume that a set of n jobs are to be processed on a set of m machines under the following basic assumptions: (1) the raw materials required are adequate in the production system, (2) no change will occur in the production tasks, (3) all machines will not break down within the production cycle, (4) all machines are available and all jobs can be processed at t = 0, (5) each job has a fixed processing route and each process has a fixed processing time, (6) all machines are independent from each other. i∈M = {1,2, …, m} is the machine mark number and A = {A₁, A₂, …, A_i, …, A_m} is the machine set. P_i is the process set on machine A_i.

Let us suppose that the current simulation data set Ω_j contains N_j solutions to the discussed scheduling problem, and these solutions are rapidly generated through the combination of dispatching rules, which is one of the most easily implemented and efficient scheduling methods. Element $S_{j}^{k}$ in Ω_j denotes the kth generated feasible solution, k∈{1,2, …, N_j}, and its corresponding scheduling objective value that measures production performance is $f_{j}^{k}$ . Thus, the average objective value of all solutions in set Ω_j can be expressed as equation (2)

{\bar{f}}_{Ω_{j}}^{0} = \frac{1}{N_{j}} \sum_{k = 1}^{N_{j}} f_{j}^{k}

(2)

The variation of machine capacity in the jth simulation $Δ c_{j} (0 < | Δ c_{j} | < 1)$ is then set. $Δ c_{j} < 0$ denotes that machine capacity decreases by $| 100 Δ c_{j} | %$ and $Δ c_{j} > 0$ denotes that machine capacity increases by $| 100 Δ c_{j} | %$ . Therefore, the processing time of all the processes on the machine changes to $1 / (1 + Δ c_{j})$ of the original times.

For machine A_i, change the processing time of all the processes in set P_i by $Δ c_{j}$ while ensuring that the processing time of the processes on all the other machines remains unchanged. The new average objective value ${\bar{f}}_{Ω_{j}}^{i}$ can be obtained by decoding each scheduling solution in set Ω_j again after the time alteration and averaging the obtained objective values. The change in average objective value caused by the capacity change of machine A_i is described as equation (3)

Δ f_{ij} = {\bar{f}}_{Ω_{j}}^{i} - {\bar{f}}_{Ω_{j}}^{0}

(3)

According to the definition of bottleneck machines, the bottleneck index of machine A_i when capacity changes by $Δ c_{j}$ can be expressed as equation (4)

e_{ij} = | \frac{Δ f_{ij}}{Δ c_{j}} | = | \frac{{\bar{f}}_{Ω_{j}}^{i} - {\bar{f}}_{Ω_{j}}^{0}}{Δ c_{j}} |

(4)

The bottleneck index matrix of m machines in the jth simulation can be obtained by conducting the same operation separately to other machines with the same $Δ c_{j}$

{BNI}_{j} = {[e_{1 j}, e_{2 j}, \dots, e_{mj}]}^{T}

(5)

To avoid accidental factors that may occur in a single simulation and to investigate the bottleneck characteristics of each machine comprehensively, a total of μ simulations are conducted and different $Δ c_{j}$ are used in different simulations. Finally, a m × μ matrix BNI can be obtained, where each element in the jth column separately depicts the bottleneck index of each machine gained in the jth simulation and each element in the ith row separately depicts the bottleneck index of machine A_i gained in each simulation, as shown in Figure 1.

Figure 1.

Interpretation of BNI.

Calculation of comprehensive bottleneck index based on technique for order preference by similarity to ideal solution

Technique for order preference by similarity to ideal solution (TOPSIS) is a method for multiple attribute decision that involves the following basic procedures: (1) specifying the decision problem by giving the candidates, attributes, performances of each candidate under each attribute, and construct the decision matrix; (2) finding out the ideal solution and the anti-ideal solution of the discussed decision issue; (3) calculating the similarity of each candidate to the ideal solution by considering its distances to the ideal solution and to the anti-ideal solution, and (4) sorting all the candidates according to their similarities to the ideal solution and obtaining the preferred solution that is closest to the ideal solution and farthest from the anti-ideal solution. In this study, each machine is considered as a candidate of the bottleneck identification issue, and the bottleneck index values of the machine under different capacity variations are regarded as the attribute values of the candidate under different attributes. In this manner, the similarities of each candidate (each machine) to the ideal solution (an ideal machine with the highest bottleneck indexes under different capacity variations) can be calculated using TOPSIS. This similarity is referred to as the comprehensive bottleneck index of the machine. The corresponding relations between the elements of TOPSIS and the elements of bottleneck detection are shown in Table 1, and taking BNI as the decision matrix, the procedures to obtain the comprehensive bottleneck index are as follows:

Step 1. Normalizing bottleneck index matrix BNI.

Let

{MAX}_{j} = max {e_{ij} | i \in M}, j = 1, 2, \dots, μ

(6)

{MIN}_{j} = min {e_{ij} | i \in M}, j = 1, 2, \dots, μ

(7)

e_{ij}^{'} = \frac{e_{ij} - {MIN}_{j}}{{MAX}_{j} - {MIN}_{j}}

i \in M, j = 1, 2, \dots, μ

(8)

The bottleneck index matrix BNI will be transformed into the standardized BNI′ through transforming $e_{ij}$ into $e_{ij}^{'}$ by equation (8).

Step 2. Finding out the ideal solution and the anti-ideal solution

{MAX}_{j}^{'} = max {e_{ij}^{'} | i \in M}, j = 1, 2, \dots, μ

(9)

{MIN}_{j}^{'} = min {e_{ij}^{'} | i \in M}, j = 1, 2, \dots, μ

(10)

The ideal solution ${BNI}^{+}$ is selected as

{BNI}^{+} = {MAX'_{j} | j = 1, 2, \dots, μ}

(11)

The anti-ideal solution ${BNI}^{-}$ is selected as

{BNI}^{-} = {MIN'_{j} | j = 1, 2, \dots, μ}

(12)

Step 3. Calculating the Euclidean distance from machine A_i to the ideal solution ${BNI}^{+}$ as equation (13) and that to the anti-ideal solution ${BNI}^{-}$ as equation (14)

L_{i}^{+} = D_{Eu} (A_{i}, {BNI}^{+}) = \sqrt{\sum_{j = 1}^{μ} {(e_{ij}^{'} - MAX'_{j})}^{2}}, i \in M

(13)

L_{i}^{-} = D_{Eu} (A_{i}, {BNI}^{-}) = \sqrt{\sum_{j = 1}^{μ} {(e_{ij}^{'} - MIN'_{j})}^{2}}, i \in M

(14)

Step 4. Calculating the similarity of machine A_i to the ideal solution as equation (15) and referring the results E_i as the comprehensive bottleneck index of machine A_i

E_{i} = \frac{L_{i}^{-}}{L_{i}^{+} + L_{i}^{-}}, i \in M

(15)

Thus, the comprehensive bottleneck index matrix of m machines CBNI is obtained

CBNI = {[E_{1}, E_{2}, \dots, E_{m}]}^{T}

(16)

Table 1.

Corresponding relations between TOPSIS and bottleneck detection.

Elements of TOPSIS	Elements of bottleneck detection
Candidate	Machines of the manufacturing system
Attribute	Bottleneck index of a machine under a certain capacity variation
Attribute value	Bottleneck index value of a machine under a certain capacity variation
Multiple attributes	Bottleneck indexes of a machine under different capacity variations
Decision matrix	Bottleneck index matrix BNI
Ideal solution	Machine with the highest bottleneck indexes under different capacity variations
Anti-ideal solution	Machine with the lowest bottleneck indexes under different capacity variations
Similarity of a candidate to the ideal solution	Comprehensive bottleneck index of a machine

TOPSIS: technique for order preference by similarity to ideal solution.

Comprehensive bottleneck index is calculated by integrating the bottleneck characteristic knowledge gained from μ simulations. It can eliminate accidental factors that may occur in a single simulation. Hence, bottleneck characteristics can be fully reflected. The identification results based on this index are satisfactory and convincing.

Identification of bottleneck machine clusters based on hierarchical clustering analysis

Considering the fact that there exist primary and secondary relationships among bottleneck machines, Wang et al.^11,24 proposed a set of innovative concepts, including machine cluster, bottleneck cluster (BC), primary bottleneck cluster (PBC), and PBC order, and established a job-shop bottleneck cluster detection method (BC-DM) that uses clustering analysis to output bottleneck machine clusters under different hierarchies. Different from determining the bottleneck sets by a subjectively given size, the cluster method makes the size more reasonable and objective.

After obtaining the comprehensive bottleneck index matrix CBNI, hierarchical clustering analysis is employed in this study to identify bottleneck machine clusters under different hierarchies. The workflow is shown in Figure 2.

Figure 2.

Bottleneck machine cluster identification through machine’s hierarchical clustering.

It can be seen from Figure 2 that m machines in A are first hierarchically clustered according to their comprehensive bottleneck indexes in CBNI. During the process, the distance between two machine clusters C_p and C_q is defined as the distance between the two machines that are separate from the two clusters and are closest to each other in the comprehensive bottleneck index. That is

\begin{matrix} D_{sl} (C_{p}, C_{q}) & = min {d (A_{x}, A_{y}) | A_{x} \in C_{p}, A_{y} \in C_{q}} \\ = min {| E_{x} - E_{y} |, A_{x} \in C_{p}, A_{y} \in C_{q}} \end{matrix}

(17)

Bottleneck machine cluster identification is then conducted based on the final result of machine hierarchical clustering C_m+t and the corresponding dendrogram. In this process, the cluster center of a machine cluster is defined as the machine with the highest comprehensive bottleneck index in this cluster. The cluster centers of two machine clusters are compared, and the machine cluster with the cluster center that has a higher comprehensive bottleneck index is selected as the bottleneck machine cluster under a certain hierarchy.

The entire workflow of the proposed detection method is shown in Figure 3. The basic procedures are described as follows:

Step 1. Make the discussed bottleneck identification case specific by giving the job number n, machine number m, processing route of each job, and processing time of each process. Set the total number of simulations μ. j denotes the simulation mark number, j = 1.

Step 2. If $j ⩽ μ$ , randomly generate a feasible solution set Ω_j, decode each of its element $S_{j}^{k}$ and obtain the corresponding scheduling objective value $f_{j}^{k}$ . Then, the results are used to calculate the average objective value ${\bar{f}}_{Ω_{j}}^{0}$ . Create $Δ c_{j}$ in the jth simulation. Let the machine mark number i = 1 and proceed to Step 3. Else, output the bottleneck characteristic index matrix $BNI$ and proceed to Step 5.

Step 3. For machine A_i, change the processing time of all the processes in P_i into $1 / (1 + Δ c_{j})$ of the original and calculate its bottleneck index in the jth simulation $e_{ij}$ ; then, change the processing time of all the processes in P_i back to the original. i = i+1 and proceed to Step 4.

Step 4. If $i ⩽ m$ , proceed to Step 3. Else, output bottleneck matrix in the jth simulation ${BNI}_{j}$ , j = j+1, and proceed to Step 2.

Step 5. Calculate the comprehensive bottleneck index matrix CBNI based on BNI with TOPSIS.

Step 6. Conduct hierarchical cluster analysis to identify the bottleneck machine clusters under different hierarchies based on CBNI.

Step 7. Terminate and output the final results.

Figure 3.

Bottleneck identification workflow based on TOC and sensitivity analysis.

Computational example studies and discussions

Computational examples

To illustrate the effectiveness and performance of the designed method in this study, we adopt job-shop scheduling benchmark instances for simulation, including different scales of 50, 75, 100, 200, and 300 operations. Each scale contains 4 instances, that is, 20 instances in all. The simulation details of each instance (such as the number of machines, number of jobs, number of operations, processing time for each operation, and processing routine) are available at http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt. Minimizing the makespan that is frequently used is selected as the scheduling objective. The number of feasible solutions randomly generated in each simulation is set as N_j = 200 for benchmarks with processes less than or equal to 100 and N_j = 400 for benchmarks with processes more than 100. Bottleneck identification will be conducted from two aspects, $Δ c_{j} > 0$ and $Δ c_{j} < 0$ . The common identification results obtained in both aspects will be considered as the final results. In each aspect, a total of 10 simulations will be conducted. When $Δ c_{j} > 0$ , $Δ c_{j}$ is increased from 0.05 to 0.5 with an increment of 0.05; when $Δ c_{j} < 0$ , $Δ c_{j}$ is decreased from −0.05 to −0.5 with a reduction of 0.05. The bottleneck machine clusters obtained under different hierarchies are shown in Table 2. LA08 is selected to demonstrate the detailed identification process (only aspect $Δ c_{j} > 0$ is presented; when $Δ c_{j} < 0$ , the process is the same), as shown in Figure 4.

Table 2.

Identification results of the proposed method.

Benchmark	Scale (n × m)	Δc > 0		Δc < 0		Final results
Benchmark	Scale (n × m)	PBC	Hierarchy	PBC	Hierarchy	PBC	Hierarchy
LA01	10 × 5	5	1	5	1	5	1
LA02	10 × 5	1, 4	1	1, 4	1	1, 4	1
LA02	10 × 5	4	2	4	2	4	2
LA03	10 × 5	1, 2, 5	1	1, 2	1	1, 2	1
		1, 2	2	2	2	2	2
		2	3
LA04	10 × 5	1, 3, 5	1	1, 3, 5	1	1, 3, 5	1
LA04	10 × 5	5	2	5	2	5	2
LA06	15 × 5	1	1	1	1	1	1
LA07	15 × 5	1, 4	1	1, 4	1	1, 4	1
LA07	15 × 5	1	2	1	2	1	2
LA08	15 × 5	4, 5	1	4, 5	1	4, 5	1
LA08	15 × 5	5	2	5	2	5	2
LA09	15 × 5	2, 4	1	2, 4	1	2, 4	1
LA09	15 × 5	2	2	2	2	2	2
LA16	10 × 10	1, 7, 10, 3, 5, 6	1	1, 7, 10, 3, 5, 6	1	1, 7, 10, 3, 5, 6	1
		1, 7, 10, 3	2	1, 7, 10, 3	2	1, 7, 10, 3	2
		3	3	3	3	3	3
LA17	10 × 10	4, 7	1	4, 7	1	4, 7	1
LA17	10 × 10	4	2	4	2	4	2
LA18	10 × 10	1, 4, 7, 8, 6	1	1, 4, 7, 8	1	1, 4, 7, 8	1
		1, 4, 7, 8	2	1	2	1	2
		1	3
LA19	10 × 10	1, 10, 8, 3, 4, 2, 7	1	2, 7	1	2, 7	1
		2, 7	2	7	2	7	2
		7	3
LA26	20 × 10	1, 5, 7	1	1, 5, 7	1	1, 5, 7	1
		1	2	1, 5	2	1	2
				1	3
LA27	20 × 10	9, 10, 4, 6, 7, 1, 3, 8	1	4, 6, 7	1	4, 6, 7	1
		6, 7, 4, 9, 10	2	4	2	4	2
		6, 7, 4	3
		4, 6	4
		4	5
LA28	20 × 10	2, 10	1	2, 10	1	2, 10	1
LA28	20 × 10	2	2	2	2	2	2
LA29	20 × 10	3, 4, 10	1	3, 4	1	3, 4	1
		3, 4	2	3	2	3	2
		3	3
LA31	30 × 10	1, 7, 8	1	1, 7, 4, 5, 8	1	1, 7	1
		1, 7	2	1, 7	2	1	2
		1	3	1	3
LA32	30 × 10	7, 9	1	7, 9	1	7, 9	1
LA32	30 × 10	7	2	7	2	7	2
LA33	30 × 10	4, 7	1	4, 7	1	4, 7	1
LA33	30 × 10	4	2	4	2	4	2
LA34	30 × 10	2, 4, 3, 8, 9, 5, 7, 6, 10	1	2, 4, 3, 8, 9, 5, 7, 6, 10	1	2, 4, 3, 8, 9, 5, 7, 6, 10	1
		2, 4, 3, 5, 7, 6	2	2, 4, 3, 5, 7, 6	2	2, 4, 3, 5, 7, 6	2
		4, 7, 6	3	4, 7, 6	3	4, 7, 6	3
		4, 6	4	4, 6	4	4, 6	4
		4	5	4	5	4	5

PBC: primary bottleneck cluster.

Figure 4.

Detailed bottleneck identification process of LA08: (a) bottleneck index of each machine in LA08, (b) comprehensive bottleneck index of each machine in LA08, (c) hierarchical clustering dendrogram of LA08, (d) bottleneck cluster (BC), (e) primary bottleneck cluster (PBC₂), and (f) final results.

The identification results of the proposed methods are compared with those of several existing approaches in literature: (1) BDM-OE,¹⁰ (2) SB-DM,¹⁵ and (3) BC-DM.¹¹ The results are presented in Table 3.

Table 3.

Comparison of the results of four methods.

Benchmark	Scale (n × m)	Results of SB-DM	Results of BDM-OE	Results of BC-DM		Results of the proposed method
Benchmark	Scale (n × m)	Results of SB-DM	Results of BDM-OE	PBC	Hierarchy	PBC	Hierarchy
LA01	10 × 5	5	5	5	1	5	1
LA02	10 × 5	4	1	4	1	1, 4	1
LA02	10 × 5	4	1	4	1	4	2
LA03	10 × 5	2	2	1, 2, 5	1	1, 2	1
				1, 2	2	2	2
				2	3
LA04	10 × 5	3	5	1	1	1, 3, 5	1
LA04	10 × 5	3	5	1	1	5	2
LA06	15 × 5	1	1	1	1	1	1
LA07	15 × 5	1	1	1	1	1, 4	1
LA07	15 × 5	1	1	1	1	1	2
LA08	15 × 5	5	3	4, 5	1	4, 5	1
LA08	15 × 5	5	3	5	2	5	2
LA09	15 × 5	2	2	2, 4	1	2, 4	1
LA09	15 × 5	2	2	2	2	2	2
LA16	10 × 10	3	1	3	1	1, 7, 10, 3, 5, 6	1
						1, 7, 10, 3	2
						3	3
LA17	10 × 10	4	4	4	1	4, 7	1
LA17	10 × 10	4	4	4	1	4	2
LA18	10 × 10	1	1	1, 4	1	1, 4, 7, 8	1
LA18	10 × 10	1	1	1	2	1	2
LA19	10 × 10	7	2	7	1	2, 7	1
LA19	10 × 10	7	2	7	1	7	2
LA26	20 × 10	1	5	1, 9	1	1, 5, 7	1
LA26	20 × 10	1	5	1	2	1	2
LA27	20 × 10	4	4	4	1	4, 6, 7	1
LA27	20 × 10	4	4	4	1	4	2
LA28	20 × 10	2	2	2	1	2, 10	1
LA28	20 × 10	2	2	2	1	2	2
LA29	20 × 10	4	4	4	1	3, 4	1
LA29	20 × 10	4	4	4	1	3	2
LA31	30 × 10	1	1	1	1	1, 7	1
LA31	30 × 10	1	1	1	1	1	2
LA32	30 × 10	7	9	7	1	7, 9	1
LA32	30 × 10	7	9	7	1	7	2
LA33	30 × 10	4	4	4	1	4, 7	1
LA33	30 × 10	4	4	4	1	4	2
LA34	30 × 10	7	7	7	1	2, 4, 3, 8, 9, 5, 7, 6, 10	1
						2, 4, 3, 5, 7, 6	2
						4, 7, 6	3
						4, 6	4
						4	5

SB-DM: shifting bottleneck detection method; BC-DM: bottleneck cluster detection method; PBC: primary bottleneck cluster.

Results discussion

Table 3 shows that the results of the proposed method are consistent with those of SB-DM for most scheduling benchmarks, with a consistency rate of 87.5%. In identifying BC under the highest hierarchy, which is the most important bottleneck knowledge, the coincidence rate between the results of the proposed method and those of BC-DM is 90%. Thus, the proposed method is feasible and effective.

The slight difference in detection results from those of the other methods is attributed to the difference in data foundations and production indicators used (Table 4). The proposed method can be conducted without the optimal scheduling scheme. Its data foundation is a set of feasible scheduling schemes that are randomly generated, whereas SB-DM and BC-DM work based on the obtained optimal or suboptimal scheduling scheme obtained by optimization algorithms. The proposed method locates bottlenecks based on the sensitivity of production performance to the capacities of each machine, whereas SB-DM determines the bottleneck based on the duration a machine is active without interruption in the optimal scheduling scheme and BC-DM bases identification on production data of each machine, including workload, utilization rate, and average active time. Differences in data foundation and identification indicators determine that the slight variances in the recognition result cannot be avoided.

Table 4.

Comparison of data foundation and production indicators used in the three methods.

	SB-DM	BC-DM	Proposed method
Data foundation	Optimal or suboptimal solution	Optimal or suboptimal solution	Feasible solutions
Production indicators	Duration a machine is active without interruption	Workload, utilization rate, and average active time	Sensitivity of system performance to machine capacity

SB-DM: shifting bottleneck detection method; BC-DM: bottleneck cluster detection method.

Notably, the proposed method is superior to the other two methods on computational complexity and efficiency. As posterior-to-run identification methods, SB-DM and BC-DM, can only be applied after the production system has run or the optimal scheduling scheme to be used has already been generated. However, the gain of the optimal scheduling scheme largely depends on the selected optimization algorithm and related parameters, and most job-shop scheduling problems have been shown to be non-deterministic polynomial-time (NP)-hard in the strong sense and still considered to be very difficult combinatorial optimization problems. Thus, the relatively high requirement of the two methods on data foundations considerably reduces their recognition efficiency.

The proposed method is a prior-to-run identification method and only requires feasible scheduling schemes as data foundations. The main procedures, including the random generation of feasible scheduling schemes, changing processing time of processes, encoding, and decoding, are very simple. Hence, identifying bottlenecks takes less time and the longest running time does not exceed 10 s. Therefore, the proposed method has great advantages on efficiency.

Compared with BDM-OE, which is also a prior-to-run identification method, the proposed method has unique advantages. BDM-OE conducts identification by performing several typical orthogonal experiments without knowing the optimal scheduling scheme. However, the reliability of the results highly depends on whether the orthogonal layouts used are appropriate. In addition, different orthogonal layouts need to be created for different cases, and the construction of orthogonal layouts is very complex, especially for cases consisting of numbers of machines. As the number of machines increases, constructing the appropriate orthogonal layouts becomes increasingly difficult, which greatly restricts the application of the method in large-scale scheduling cases and weakens its adaptability and flexibility.

Based on the basic principles of TOC, the proposed method conducts bottleneck identification by examining the sensitivity of system performance to machine capacities. For identification cases of all sizes, bottlenecks can be located through unified procedures and operations without individualized processes. Thus, the method has greater adaptability and flexibility.

Conclusion and outlook

This study initially defines bottleneck machines in a job shop based on the basic principle of TOC that bottlenecks control operations of the whole system. With an eye to internal factors that have impact on system performance, this definition is in favor of identifying system bottlenecks from the global point of view by conducting an overall performance-oriented measurement in each machine. Consequently, this method provides good guidance for subsequent production optimization.

To overcome the disadvantages of existing bottleneck detection methods for a job shop, including complex recognition algorithms and poor guidance caused by posterior-to-run recognition, a prior-to-run method based on TOC and sensitivity analysis is designed based on the foundation of bottleneck identification. A bottleneck index matrix is first obtained by measuring the sensitivity of system performance to the capacity of each machine. TOPSIS is then employed to calculate the comprehensive bottleneck index. Based on the calculation results, BCs under different hierarchies are obtained through hierarchical cluster analysis. Finally, 20 benchmarks of job-shop scheduling problems are selected to compare the proposed approach with several existing approaches, that is, SB-DM, BDM-OE, and BC-DM, to illustrate the effectiveness and performance of the designed method. The comparison shows that the proposed approach is largely consistent with other popular methods in the recognition results, but could be conducted with less complexity because of its simple and unified procedures. Moreover, its data foundations are easier to obtain. Therefore, the proposed method is feasible and superior. BCs under different hierarchies can be quickly identified before the overall system circulation by using the proposed method, thereby providing considerable valuable information for managers of production systems to improve the overall system performance.

After achieving bottleneck machine identification under a steady production state, future research will consider the influence of dynamic random events on bottleneck identification and the multi-objective and multi-resource characteristics of bottlenecks, as well as focus on bottleneck identification and prediction oriented toward multiple objectives and multiple resources under the background of bottleneck shifting.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The research is supported by the National Natural Science Foundation of China (NSFC) under grant no. 51205429 and the National Science and Technology Pillar Program during the 12th Five-year Plan Period of China under grant no. 2012BAF01B01.

References

Wang

Sun

Wang

. Management & control of manufacturing cells based on theory of constrains. Comput Integr Manuf 2006; 12(7): 1108–1116.

Watson

Blackstone

Gardiner

. The evolution of a management philosophy: the theory of constraints. J Oper Manag 2007; 25(2): 387–402.

Cheng

. Research of production scheduling algorithm based on bottleneck analysis. In: Proceedings of 2008 ISECS international colloquium on computing, communication, control, and management, Guangzhou, China, 3–4 August 2008, pp.52–56. New York: IEEE.

Zhang

. Bottleneck identification procedures for the job shop scheduling problem with application to genetic algorithm. Int J Adv Manuf Tech 2009; 42(11–12): 1153–1164.

Zuo

. Modified bottleneck-based heuristic for large-scale job shop scheduling problem with a single bottleneck. J Syst Eng Electron 2007; 18(3): 556–565.

Cox

Spencer

. The constraints management handbook. Boca Raton, FL: St. Lucie Press, 1997.

Kasemset

Kachitvichyanukul

. Simulation-based procedure for bottleneck identification. In: Asia simulation conference2007, Seoul, Korea, 10–12 October 2007, pp.46–55. Berlin Heidelberg: Springer.

Lawrence

Buss

. Shifting production bottlenecks: causes, cures, and conundrums. Prod Oper Manag 1994; 3(1): 21–37.

Zhuang

Wong

Fuh

JYH

. On the role of a queueing network model in the design of a complex assembly system. Robot Cim Int Manuf 1998; 14(2): 153–161.

10.

Zhai

Sun

Wang

. Job shop bottleneck detection based on orthogonal experiment. Comput Ind Eng 2011; 61: 872–880.

11.

Wang

Kang

Chen

. Identification approach for bottleneck cluster in a Job Shop. Comput Integr Manuf 2013; 19(3): 540–551.

12.

Chang

. Data driven bottleneck detection of manufacturing systems. Int J Prod Res 2009; 47(18): 5019–5036.

13.

Sengupta

Das

VanTil

. A new method for bottleneck detection. In: Proceedings of the 40th conference on winter simulation, Miami, FL, 7–10 December 2008, pp.1741–1745. New York: IEEE.

14.

Ching

Meerkov

Zhang

. Assembly systems with non-exponential machines: throughput and bottlenecks. Nonlinear Anal Theor 2008; 69(3): 911–917.

15.

Roser

Nakano

Tanaka

. A practical bottleneck detection method. In: Proceedings of the 2001 winter simulation conference, Washington, DC, December 2001, pp.949–953. December 9–12. New York: IEEE.

16.

Roser

Nakano

Tanaka

. Shifting bottleneck detection. In: Proceedings of the 2002 winter simulation conference, San Diego, CA, 8–11 December 2002, pp.1079–1086. New York: IEEE.

17.

Chiang

Kuo

Lim

. Improvability of assembly systems I: problem formulation and performance evaluation. Math Probl Eng 2000; 6(4): 321–357.

18.

Chiang

Kuo

Lim

. Improvability of assembly systems II: improvability indicators and case study. Math Probl Eng 2000; 6(4): 359–393.

19.

Kuo

Lim

Meerkov

. Bottlenecks in serial production lines: a system-theoretic approach. Math Probl Eng 1996; 2(3): 233–276.

20.

Kuo

Lim

Meerkov

. Bottlenecks in serial production lines: a systems approach. In: Proceedings of the 35th conference on decision and control, Kobe, Japan, 11–13 December 1996, pp.2751–2756. New York: IEEE.

21.

Zhai

Sun

Yang

. Multi-bottleneck scheduling algorithm for large-scale job shop. Comput Integr Manuf 2011; 17(7): 1486–1494.

22.

Zhang

. Bottleneck machine identification based on optimization for the job shop scheduling problem. ICIC Expr Lett 2008; 2(2): 175–180.

23.

Zhang

. Bottleneck machine identification method based on constraint transformation for job shop scheduling with genetic algorithm. Inform Sciences 2012; 188: 236–252.

24.

Wang

Chen

. New entropy weight-based TOPSIS for evaluation of multi-objective job-shop scheduling solutions. In: Proceedings of the 2012 IEEE international conference on industrial engineering and engineering management, Hong Kong, 10–13 December 2012, pp.464–468. New York: IEEE.