Models and algorithms for a two-stage production process

Abstract This paper considers the problem of scheduling and sequencing jobs on machines in a two-stage production process. The problem is motivated by a real-world application concerning a major paper products plant which produces business forms. Here, the printing and the collating operations constitute the two production stages. We develop a model for this problem and propose a solution approach based on the decoupling of the problem into two single stage problems. Each single stage problem, which is the main focus of this paper, is further decomposed into an allocation subproblem and a sequencing subproblem of jobs on machines. Both exact and heuristic algorithms are developed for these subproblems. An overall scheme is proposed for linking together the information and solutions provided by these decomposed system components. Different versions of the algorithm are tested on industrial data, and recommendations are made for implementation.