Keywords

1 Introduction

Let, there are ‘n’ tasks that comprise a job that needs to be completed in an assembly line and the corresponding time of completion be tj (j = 0 to n). The order of processing is partially controlled by certain constraints called as the ‘precedence’ that are not to be violated. This defines the tasks that need to be completed before starting a particular task. The tasks are carried out in different work stations that are to be balanced to the possible extent. The maximum time to be spent in a work station defines the ‘cycle time, c.’ The cycle time being constant, the objective is to minimize the number of work stations, m*.

The solution procedures include exact methods and heuristic methods. The exact methods are not suitable for larger problems as the computation time grows exponentially with the problem size. SALBP-1 are NP hard [1] and hence, efficient heuristics are required to solve within a reasonable time period. As a result, researchers have developed many efficient heuristic methods over the years.

Positional weight method [2], procedure based on number of predecessors [3], heuristic using trade and transfer [4], heuristic of Hackman et al. [5], precedence matrix method proposed by Hoffmann [6] are a few efficient heuristic methods proposed during earlier periods of research. Many heuristics are available in the literature based on simple as well as combined priority rules. It is generally accepted that Hoffmann’s algorithm is still one of the best simple algorithms in this domain, at the cost of execution time.

In the next level, branch and bound method, dynamic programming and evolutionary algorithms are used by many to refine the accuracy of heuristics. Most of the evolutionary algorithms take the results from the simple heuristics as their seed solutions and proceed.

Sivasankaran and Shahabudeen [7] classified assembly-line balancing problems into eight types and conducted a comprehensive review on the available methods.

2 Data Set and Heuristics Considered

A precedence diagram is a graphical representation of a project that shows the number of tasks, their respective task times, and the sequence of tasks that need to be completed before a particular task. Figure 41.1 shows the precedence diagram of a SALBP-1 analyzed by Rosenberg and Ziegler [8].

Fig. 41.1
figure 1

A precedence diagram—Rosenberg and Ziegler

Full size image

This particular project has 25 tasks with a total time of 125 units. For analyzing the heuristics considered, this particular problem is considered as it is a reasonably large sized tested data set. To have more number of problems, the cycle time is considered for different values, from 14 units to 32 units as listed in Table 41.1.

Table 41.1 Cycle time and optimum number of work stations
Full size table
$$\begin{aligned} {\text{Strength}}\,{\text{of}}\,{\text{the}}\,{\text{precedence}},\,D & = 2d/(N(N - 1)) \\ & = \left( {2\, \times \,32} \right)/(25(25 - 1)) \\ & = 0.11 \\ \end{aligned}$$

Since the same data set is tested for six cycle times, we get a total of six SALBP-1.

‘c’ represents the cycle time and ‘m*’ represents the optimum number of work stations for a particular cycle time. The optimum number of work stations for different cycle times is available in the data sets provided by Scholl [9] and is reproduced in Table 41.1. The parameters considered are listed in Table 41.2.

Table 41.2 Parameters considered
Full size table

The precedence diagram is transformed into a precedence matrix as shown in the left half of Table 41.3 which can be directly used in a computer program. The matrix is appended with other required parameters (obtained from the precedence diagram) as described and presented in the right half of the same table.

Table 41.3 Precedence matrix and other parameters
Full size table

Based on a presumption that simultaneously considering the same parameter before and after a task being considered can result in better algorithms; slope indices (ratios) are being computed for a particular task. They are the ratios of a particular parameter before and after a task.

The weights w1 to w5 are the slope indices as computed below. Weight ‘w’ is the rule proposed by Dar-El; weight, w = a = total number of tasks having ‘j’ as its head (including self). Weight w6 is computed in a different way but, using tj, k and i that are used for w5 in a slope format. For any task ‘j,’ the slope is the ratio between the right and left parameter values.

$$\begin{aligned} {\text{Weight}},\,w = a;\,{\text{Weight}},w1 = tj\frac{a}{b};{\text{Weight}},w2 = tj\frac{c}{d} \hfill \\ {\text{Weight}},\,w3 = tj\frac{f}{e};\,{\text{Weight}},w4\, = \,tj\frac{h}{g};\,{\text{Weight}},\,w5\, = \,tj\frac{k}{i} \hfill \\ {\text{Weight}},\,w6 = tj(k - i). \hfill \\ \end{aligned}$$

Table 41.4 shows the parameters converted as weights for different heuristics. For solving the problems, the weights are arranged in descending order of their weights.

Table 41.4 Weights considered for the analysis
Full size table

The two popular time-tested algorithms proposed by Dar-El [10] and Hoffmann [6] are taken as the benchmarks.

3 Performance Measures

Perfect balancing of work stations is important to reduce the idle time of individual work stations. If they are not balanced properly, bottlenecks will be a problem in any assembly line. There are three basic measures for the effectiveness of the heuristics viz. (i) Line efficiency (ii) Smoothness index, and (iii) Computation time.

Only the former two measures are considered in this analysis as all the heuristics except the Hoffmann’s have the same time complexity. The performance measures are defined as:

$${\text{Line}}\,{\text{efficiency}}\,\left( {\text{LE}} \right) = \frac{{\sum\limits_{i = 1}^{k} {{\text{ST}}_{i} } }}{c \cdot k} \times 100$$
$${\text{Smoothness}}\,{\text{index}}\,\left( {\text{SI}} \right)\, = \,\sqrt {\mathop \sum \limits_{i = 1}^{k} [({\text{ST}}_{ \hbox{max} } - {\text{ST}}_{i} )]^{2} }$$

  • STi—Total station time of ith station

  • c—Cycle time

  • k—Number of work stations.

4 Computational Results

The line efficiency and smoothness indices are computed separately for each heuristic algorithm using the benchmark problems in addition to the reference algorithms. Higher values of efficiency and lower value of smoothing index are the indications of perfect line balancing. In all the cases, the ties are broken according to the task number, smaller first. The summary of results is presented in Table 41.5.

Table 41.5 Summary of performance measures for different heuristics
Full size table

It is observed that the heuristic numbers three and seven perform better than others, including the benchmark algorithms in terms of the tested performance measures. When one-way AVOVA was carried out, it was observed that:

$${\text{Line}}\,{\text{efficiency}}:{\text{Experimental}}\,F = 0.86 < {\text{Critical}}\,F = 2.372.$$
$${\text{Smoothness}}\,{\text{index}}:{\text{Experimental}}\,F = 0.85 < {\text{Critical}}\,F = 2.372.$$

Hence, it is concluded that there is no significant difference among the heuristics. However, to confirm their relative performance, pairwise comparisons will be carried out in the extended work. The box plots for line efficiency and smoothing index obtained show that the variation in line efficiencies and smooth indices are relatively less for the weights a, t(f/e) and t(k − i).

After the computation, three more cases were analyzed as described below:

  1. (i)

    Taking the weight as t(a/b) + t(k/i) (combination of better performing heuristics):

The results show that the mean line efficiency and smoothing index are exactly the same as that of t(k/i) for each cycle time and slightly differ from that of t(a/b).

$${\text{New}},\,{\text{mean}}\,{\text{efficiency}} = 85.1931\% \,{\text{and}}\,{\text{smoothing}}\,{\text{index}} = 11.1094.$$
  1. (ii)

    The order of one better performing heuristic is reversed to ascending and the measures are again computed.

In such a case, the performance decreases to 82.0986% and 15.8208 from 85.1931% and 11.1094 earlier.

  1. (iii)

    The order of one average performing heuristic is reversed to ascending and the measures are again computed.

In this case, the performance increases to 81.9379% and 15.8160 from 80.9713 and 16.2697 earlier.

In the latter two cases, another observation is that the maximum number of jobs available for allotment is four as against five earlier.

5 Conclusion and Future Work

This paper discusses a newly proposed set of six simple heuristics based on the slope indices for the simple type—I assembly-line problems. They are tested against the benchmark data set for different cycle times. The results are compared with the popular time-tested algorithms proposed by Dar-El and Hoffmann. Two of the six heuristics perform better than these two for the tested performance measures, line efficiency, and smoothing index.

To validate the results further, more number of data sets are to be used. Also, further improvements in simple heuristics including tie-breaking rules, different precedence strengths are to be applied for these heuristics also and the effects are to be analyzed. Only forward enumeration is considered here. Backward and bidirectional enumerations are to be implemented for further improvement in the performance.