Heuristic Techniques for Simultaneous Scheduling of Production and Distribution in Multi-Echelon Structures: Theory and Empirical Comparisons

Seven heuristic algorithms are discussed. Each can be used for production scheduling in an assembly network (a network where each work station has at most one immediate successor work station, but may have any number of immediate predecessor work stations), distribution scheduling in an arborescence network (a network where each warehouse or stocking point is supplied by at most one immediate predecessor stocking point, but may itself supply any number of immediate successor stocking points), and joint production-distribution scheduling in a conjoined assembly-arborescence network. The objective of each algorithm is to determine a production and/or product distribution schedule which satisfies final product demand and minimizes the sum of the average inventory holding costs and average fixed charges for processing (ordering, delivery, or setup costs), per period, over an infinite planning horizon. Exogenous demand for product is assumed to be deterministic, at a constant rate, and to occur only at “retail” facilities of the networks. On the basis of their performance in 11,000 computer generated problems, the seven heuristic methods are compared with each other and with a dynamic programming algorithm. The results indicate that for most of the network structures considered, the best heuristic is the method of steepest descent; the second best is a simple extension of a method originally developed by Crowston, Wagner, and Henshaw. The improved myopic procedure of Graves and Schwarz performs very well for some particular types of structures. Surprisingly, two particularly naive heuristics also perform quite well in certain situations. In addition to the computer simulation experiments, we also discuss a simple computer-compatible algebraic notation scheme for identifying structure (facility interrelationships) within networks of the three types considered.