Simultaneous batching and scheduling using dynamic decomposition on a grid

Michael C. Ferris, Christos T. Maravelias, Arul Sundaramoorthy

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

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 batchunit 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.

Original languageEnglish (US)
Pages (from-to)398-410
Number of pages13
JournalINFORMS Journal on Computing
Volume21
Issue number3
DOIs
StatePublished - Jun 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Batching and scheduling
  • Chemical batch processes
  • Decomposition algorithm
  • Grid computing
  • Mixed-integer programming

Fingerprint

Dive into the research topics of 'Simultaneous batching and scheduling using dynamic decomposition on a grid'. Together they form a unique fingerprint.

Cite this