A Heuristic Approach to Alternate Routing in a Job Shop

Abstract

The research reported here investigates the use of heuristics for selecting from several alternate routes resulting from partially ordered tasks in a job shop order file. The experimental vehicle employed was digital simulation. The concept of the "Alternate string" has been developed to generalize the existence of partially ordered operations. That term is defined as a concatenation of operations that can be performed in any order, with the additional specification that all within the string can be attempted. The presence of alternate strings with two or more member gives rise to the alternate routing problem, whose solution is approached by heuristic methods. Choosing from among several alternate routes constitutes a three level decision problem. At the lowest level, routes can be chosen when the order enters the shop. This is equivalent to fixed routing. At a higher level, alternates can be selected at the time of transition from one work station to another. The third decision level occurs at operation time, when one of the alternate operations is placed on a machine. Heuristics were tested at the latter two levels. There were two prior assertions that this thesis set out to prove. The first was that alternate routing at the highest decision level would produce significant reductions in the mean tardiness of orders completed past their designated due dates, the improvement being both relative to fixed routing and to alternate routing heuristics implemented at lower decision levels. Secondly, the contention was made that the improvement would be as such a magnitude that on-line, real-time systems become economically justifiable as a means of mitigating the attendant control problems caused by non-deterministic paths through the queuing network. The methodology employed here was to conduct two passes of simulated shop runs. The first, with two artificially high levels of alternate incidence, tested the efficiency of five different alternate routing heuristics in reducing mean tardiness. The second pass consisted of runs with the best heuristic developed during the first experimental phase applied to a realistic length and frequency of alternate strings. The results of the experiments strongly support the assertions made at the outset of the thesis. The performance characteristics of the different heuristics are discussed at length. In addition, some implications are drawn of the computational nature of alternate routing and the difficulties encountered in implementing alternate routing heuristics at operation time.