This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Gaglioppa, F. Articles by Benjaafar, S. Search for Related Content

Multitask and Multistage Production Planning and Scheduling for Process Industries

Graduate Program in Industrial and Systems Engineering, Department of Mechanical Engineering, University of Minnesota, Minneapolis, Minnesota 55455
Graduate Program in Industrial and Systems Engineering, Department of Mechanical Engineering, University of Minnesota, Minneapolis, Minnesota 55455
Graduate Program in Industrial and Systems Engineering, Department of Mechanical Engineering, University of Minnesota, Minneapolis, Minnesota 55455
fgagliop{at}me.umn.edu
lmiller{at}me.umn.edu
saif{at}umn.edu

We consider the planning and scheduling of production in a multitask/multistage batch manufacturing process typical of industries such as chemical manufacturing, food processing, and oil refining. We allow instances in which multiple sequences of tasks may be used to produce end products. We formulate the problem as a mixed-integer linear program and show that the linear programming relaxation has a large integrality gap and requires significant computational effort to solve to optimality for large instances. Using echelon inventory, we construct a new family of valid inequalities for this problem. The formulation with the additional constraints leads to a significantly tighter linear programming relaxation and to greatly reduced solution times for the mixed-integer linear program.

Subject classifications: production planning/scheduling; echelon inventory; integer programming.
History: Received July 2004; revision received May 2007; accepted May 2007.