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 HighWire Google Scholar Articles by Ferris, M. C. Articles by Sundaramoorthy, A.

Simultaneous Batching and Scheduling Using Dynamic Decomposition on a Grid

Computer Sciences Department, University of Wisconsin–Madison, Madison, Wisconsin 53706
Department of Chemical and Biological Engineering, University of Wisconsin–Madison, Madison, Wisconsin 53706
Department of Chemical and Biological Engineering, University of Wisconsin–Madison, Madison, Wisconsin 53706
ferris{at}cs.wisc.edu
maravelias{at}wisc.edu
sundaramoort{at}wisc.edu

Scheduling problems arise in many applications in process industries. However, despite various efforts to develop efficient scheduling methods, current approaches cannot be used to solve instances of industrial importance in reasonable time frames. The goal of this paper is the development of a dynamic decomposition framework that exploits the structure of the problem and is well suited for grid computing. The problem we study is the simultaneous batching and scheduling of multistage batch processes for which the binary decision variables are batch selection, batch-unit assignment, and batch sequencing on units. We present methods to decompose the original problem into a number of subproblems in a dynamic fashion. First, we discuss the generation of subproblems based on fixing the batch-selection variables. Second, we generate subproblems by fixing the batch-unit assignment variables in a bottlenecking stage. Third, we generate subproblems by fixing the last batch in the sequence on each unit of the bottlenecking stage. Furthermore, the second and third methods can be carried out in various combinations. Alternatively, a problem can be decomposed into a number of promising subproblems using an automatic strong branching scheme. Our results show that the proposed method can be used on a grid computer to solve large problems to optimality in a reasonable computational time.

Key words: chemical batch processes; batching and scheduling; mixed-integer programming; grid computing; decomposition algorithm
History: received October 2007; revised March 2009; accepted April 2009.

This article has been cited by other articles:

				M. R. Bussieck, M. C. Ferris, and A. Meeraus Grid-Enabled Optimization with GAMS INFORMS Journal on Computing, July 1, 2009; 21(3): 349 - 362. [Abstract] [PDF]