Assembly Line Balancing Using Probabilistic Combinations of Heuristics

Several recent research efforts have studied the use of probabilistic schemes for generating solutions to particular combinatorial problems. Characteristically, such schemes include both rapid production of many potential solutions, through repeated application of simple choice rules, and dynamic modification of the production process ("learning"). In this study the simple choice rules (heuristics) used are derived from earlier applications of heuristic programming to the assembly line balancing problem. Repeated trials with probabilistic choice of simple rules are here viewed as an alternative method of organizing the appropriate selection and application of these heuristics. The procedure assigns tasks to work stations along the assembly line by randomly selecting a heuristic for choosing the next task to be added to the current work station. While many suitable heuristics for assembly line balancing have been suggested in the literature, our studies have primarily used the following: choose the task with the largest operation time; choose the task with the most immediate followers; choose a task randomly. The results for studies of several problems, and several cycle times of each problem, can be summarized as follows. Random selection of heuristics for choosing the next task does as well as or better than (i.e., results in fewer work stations than) either use of the individual heuristics alone, or random choice of the tasks directly, without intervening choice of heuristics.