Efficient heuristics for buffer allocation in closed serial production lines

Graduation date: 2005The optimal allocation of buffers in serial production systems is one of the\ud oldest and most researched problems in Industrial Engineering. In general, there\ud are three main approaches to the buffer allocation problem when the objective is to\ud maximize throughput. The first is basically a systematic trial and error procedure\ud supported either by discrete event simulation or analytical models. A second\ud approach is to allocate buffers based on general design rules that have been\ud established in the research literature through experimentation. And the third\ud approach is to apply a buffer allocation optimization algorithm to a specific\ud production line. All these approaches have limitations and could be time and\ud resource consuming. Additionally, most of the existing research on buffer\ud allocation only considers production systems modeled with an infinite supply of\ud raw materials before the first workstation and an unlimited capacity for finished\ud goods after the last workstation. In reality many production systems are designed\ud as closed systems where an interaction between the last and the first workstations in\ud the line is present. In a closed production system, there is a finite buffer after the\ud last workstation and the number of "carriers" holding jobs that move through the\ud line is fixed.\ud The objective of this thesis was to develop efficient heuristic algorithms for\ud the buffer allocation problem in closed production systems. Two heuristics for\ud buffer allocation were implemented. Heuristic H 1 uses the idea that highly utilized\ud workstation stages require any available buffer more than sub-utilized stages.\ud Heuristic H2 uses information stored in the longest path of a network representation\ud of job flow to determine where additional buffers are most beneficial.\ud An experiment was designed to determine if there are any statistically\ud significant differences between throughput values with buffer allocations obtained\ud with a genetic algorithm, also developed in this research, and through puts with\ud buffer allocations generated by Hi and H2. Several types of closed production\ud systems were examined in eight different test cases. No significant differences in\ud performance were observed. The efficiency of the heuristics was also analyzed. A\ud significant difference between the speeds of Hi and H2 is found.\ud The analysis performed in this research indicates that heuristic H2 is\ud sufficiently effective and accurate for determining near optimal buffer allocations in\ud closed production systems