Planning production on a single processor with sequence-dependent setups. Part 2: Campaign sequencing and scheduling

Abstract

In the preceding paper (Oh, H., Karimi, I., 2001. Planning production on a single processor with sequence-dependent setups - 1. Determination of campaigns, Comput. Chem. Eng., the preceding paper in this issue), we presented a methodology for determining the optimal campaign numbers for producing multiple products on a single processor with sequence-dependent setups and a fixed planning horizon. In this paper, we address the sequencing of these given product campaigns to obtain a detailed schedule of operation. Decomposing the problem into a sequencing subproblem and a scheduling subproblem, we develop efficient heuristic algorithms for both subproblems. For the former combinatorial subproblem, we propose an efficient tabu search based on a simple dummy search objective, while for the latter continuous subproblem, we present a novel linear programming approximation. Extensive computational evaluation on randomly generated problems shows that the combined algorithm is quite efficient and well suited for large-scale industrial problems. Moreover, it gives solutions consistently within 7% (on an average) of a lower bound and its performance does not deteriorate with high sequence-dependency or high machine utilization. Thus, the methodology of this two-part paper represents a significant improvement over existing methods for this problem. © 2001 Elsevier Science Ltd. All rights reserved.