The G-group heuristic for single machine lot scheduling

Abstract

This paper develops a heuristic procedure for generating feasible solutions for the single-machine, multi-product, infinite-horizon, lot scheduling problem. This problem occurs in several practical situations, for example, in metal stamping factories, on appliance assembly lines, in the beverage blending and bottling industries, in paint production and on motor car assembly lines. The proposed heuristic divides the N products into G groups and the products belonging to the same group are produced in the same cyclical pattern. Thus the problem of scheduling N independent products is reduced to that of scheduling G groups of products. Since G is much less than N, the problem is made simpler. The proposed heuristics has two main advantages: implementation facility and effectiveness. Computer codes are available for several mini and micro computers. The effectiveness is demonstrated by two tests. First, we solved the six problems originally solved by Elmaghraby (1978 a). Obviously, the results based on only six problems, cannot be generalized. Second, the G-group heuristic, as well as five other heuristics, was applied to 270 random computer-generated problems. The results show that it performed better.