Scheduling in multi-stage multi-product batch plants has received significant attention from researchers and practitioners for its promising role in the economic performance of chemical processes. Existing methods for the above problem assume that given the customer orders, the number and size of batches for each order are known a priori. In other words, batching and scheduling decisions are made independently in a two-step approach: orders are first split into several smaller suborders and then supplied to the scheduling model where each suborder is assumed to be satisfied by a single batch. However, when the parallel units in each stage have non-uniform capacity, then a given order of a certain size (quantity) cannot necessarily be split optimally into different batch sizes outside the scheduling model. Thus, the number and sizing of batches towards an order becomes part of the optimization. Recently, Prasad and Maravelias (2006) proposed a holistic method that accounts for batching, assignment and sequencing decisions simultaneously. However, the addition of another level (batching) in the hierarchy of decisions easily increases the size and complexity of the model. In this work, we propose an algorithm that exploits the structure of the above model and decomposes the full-space problem into several tractable subproblems. We apply a grid computing scheme based on “Condor” (Thain et al., 2003), a specialized workload management system that solves these subproblems in parallel by liaising between a master computer and several worker computers.

The problem of simultaneous batching and scheduling in multi-stage batch processes involves three major decisions. Firstly, divide the given orders into a number of batches. Secondly, assign these batches on suitable units. Thirdly, sequence the batches on each unit. Thus, there exists a natural flow of information from batching through assignment to sequencing. Hence, we use three sets of binary variables to model the above three major decisions: selection, assignment and sequencing binaries. When the selection binaries are fixed at the first level of decision hierarchy, the problem reduces to a multi-stage batch scheduling problem with known number of batches. If assignments are also made at the second level of the hierarchy, then the problem becomes a job-shop scheduling problem. Such a sequential structure in the decision hierarchy motivated us to split the full-space problem into smaller subproblems.

The proposed algorithm exploits this structure to generate a small number of promising subproblems that are relatively easy to solve. Subproblems are generated by fixing the first two levels, batch selection and assignment, of the decision hierarchy. To reduce the number of subproblems, we fix assignment decisions in the “bottleneck” stage only. Our computational studies show that this is usually sufficient to most practical problems. However, for hard problems it is possible to fix assignment binaries in more than one stage. For a given full-space problem, we may generate innumerable subproblems by simply fixing the first two levels. Many of these subproblems can be infeasible or duplications. Thus, we equip the algorithm with some preprocessing steps that can screen infeasible or “symmetric” subproblems. We also use our insight to develop rules for the generation of “balanced” subproblems. For example, if a set of decisions leads to many good solutions (and thus is difficult to explore), then we subdivide it into more subproblems.

The subproblems thus generated are solved using the grid computing scheme. Grid computing manages a pool of computers as a common resource in an opportunistic manner. It only utilizes the idle times of computers that participate in the grid. We use a specialized work management system, called Condor, which places the subproblems into a queue, chooses idle computers, assigns the subproblems based on a policy, monitors the progress of subproblems, and finally informs the user upon completion. In addition, we use various solver enhancements (routines for bound checking, etc.) to harness the computational resources of Condor.

We illustrate the efficiency of the algorithm and the gird computing scheme using two instances that cannot be solved to optimality in 24 hours of wall time if conventional branch-and-bound techniques are used on the grid. This is because some of the subproblems in the branch-and-bound tree remain very hard, thus leading to long processing times that slow the entire process down. Even if strong branching is used to generate a “balanced” tree, these instances cannot be solved to optimality. However, using the proposed algorithm both instances are solved to optimality in less that three hours of wall time. From the above study, we conclude that grid computing coupled with decomposition approaches can be used for the solution of large-scale multi-stage scheduling problems.

Reference:

1. Prasad, P., Maravelias, C.T. Batch Selection, Assignment and Sequencing in Multi-stage Multi-product Processes. To appear in Comput. Chem. Eng., 2007.

2. Condor – High Throughput Computing. http://www.cs.wisc.edu/condor/

3. Thain, D., Tannenbaum, T., Livny, M. Condor and the Grid, John Wiley & Sons, Ltd., 2003.