(372f) On the Determination of Multiple Solutions for Batch Scheduling Using Constraint Programming

On the determination of multiple solutions for batch scheduling using constraint programming

This work discusses the determination of multiple solutions for the batch scheduling problems with the help of constraint programming. Due to the complexity of batch scheduling, multiple solutions can exist for a variety of reasons. Some of them include (i) varying number of tasks performed (ii) different start times of tasks (iii) different batch size.

There has been a substantial development for efficiently solving the batch scheduling problem for longer horizons or for complex flowsheets by means of novel formulations [1-4] and hybrid algorithms [5-7]. However, there has not been any substantial development for the determination of multiple solutions for such problems. The determination of multiple solutions is important as it provides the manufacturer with additional flexibility of selecting a solution to satisfy a criterion that was not included in the optimization formulation. This can be viewed as the satisfaction of soft constraints.

The traditional way [8] of determining multiple solutions is to add an integer cut designed to avoid visiting the previous solutions and thus help in determining additional solutions while maintaining the optimality. The constructions of such cuts are straight forward for binary variables but involve complexities in the presence of integer variables. Another method involves the modification of the fathoming rule in the conventional branch and bound algorithm which allows for the determination of multiple solutions differing in the space on integer variable space. However, the determination of multiple solutions is straight forward in Constraint programming because of its intelligent enumerative nature and is thus more suitable for generating multiple solutions.

The proposed work considers the STN based MILP/CP hybrid model proposed in [5]. This model is selected as it has shown to be more efficient than the continuous time MILP model of [1]. Another benefit of this algorithm is that it inherently brings the flexibility to prioritize the nature of the multiple solutions that are needed. The hybrid algorithm of [5] composes of two parts a MILP master problem that decides on the type and number of tasks to be performed along with the assignments of the unit to tasks whereas the CP subproblem checks the feasibility of the assignments and generates cuts for the master problem. Thus, it gives the user a flexibility to determine multiple solutions based on either the number of copies and or on the batch sizes and time of tasks. Another benefit of using the hybrid algorithm of [5] is that it provides an easier modeling environment. For example, constrains stating that a task cannot start in a particular time instant can be very easily modeled in the CP framework.

As this method is based on the hybrid algorithm of [5], it can handle objective functions such as the minimization of assignment cost, the minimization of makespan for fixed demand and the maximization of profit for a fixed time horizon. Also it can accomodate variable batch-sizes and different storage policies, and resource constraints.

Algorithm:

Scenario 1: Having obtained the optimal solution, determination of multiple solutions which have the same number copies but different schedules (start and end time) or batch sizes

Step 1: Convert the CP problem to be a feasibility problem by removing the objective function and add a constraint stating that the objective should be equal to the optimal value.

Step 2:  Determine all feasible solutions.

Scenario 2: Having obtained the optimal solution, determination of multiple solutions which have different number of copies.

Step 1: Note the current solution. Convert the CP subproblem to a feasibility problem by removing the objective function and adding a constraint stating that the objective is equal to the optimal value.

Step 2:  Add Type I constraint of [5] to the master problem so that the current solution is not revisited.

Step 3: Solve the Master Problem. If infeasible, all the possible solutions have been obtained. If feasible, the solution is a part of the multiple solutions

Step 4:  Go to Step 2

Scenario 3: Having obtained the optimal solution, determination of all possible multiple solutions. This is a combination of scenario1 followed by scenario 2

It should be noted that some problems may have a huge number of multiple solutions and it may be time consuming to determine and analyze all these solutions. In such circumstances, a subsequent optimization problem (without affecting the optimality of the previous optimization problem) can be solved to determine better solutions. For example, the profit maximization problem can be solved followed by a makespan minimization problem. However, the second problem should include an additional constraint that forces the profit to be equal to the maximum profit. This will lead to a solution which will have a maximum profit and also has a minimum makespan. Another example would be the maximization of profit followed by maximizing (or minimization) the amount of a particular product or even the early completion of a product. This procedure is referred to as Lexicographic optimization. However, the solution of a series of optimization problems can be avoided by using a single step lexicographic optimization approach.

Case Study: The proposed algorithm has been implemented on an example taken form literature [5]. This case study produces 3 products and has a total of 3 units to perform 9 tasks. The details of the case study can be obtained from [5]. The results presented here are only for the maximization of profit over a horizon of 20 hours. The optimal profit for this case study has been reported [5] to be 16 units.

Preliminary Results: The results of the first two scenarios are presented here as the third scenario is an extension of the first two scenarios. The results were obtained using the ILOG OPL Scheduler.

Scenario 1: Figures 1 and 2 represent two solutions obtained with the same number of copies. As can be seen from the figure, the optimal profit in both cases is 16 units. However, the solution in Figure 1 takes 20 hours while the solution in Figure 2 takes only 19 hours to obtain the same profit. This is inspite of the fact that both the solutions produce exactly the same amount of products. Thus, the manufacturer can select any of these two solutions as per the need. These two solutions are part of the multiple solutions and not the whole set of multiple solutions. These other solutions can be explored to determine solutions satisfying an additional constraint.

Scenario 1: Multiple Solutions with different schedules

Figure 1: An optimal solution with a makespan of 20hours

Figure 2: An optimal solution with a makepan of 19hours

Scenario 2: Figures 3 and 4 represent two solutions having the same amount of profit but with different number of tasks being performed in each of them. The solution in Figure 1 is the same as that of Figure 3. However, these turn out to be two different solutions for Scenario 2. The solution in Figure 3 produces all the three types of products whereas the solution in Figure 4 produces only two types of products. Thus it provides the manufacturer with additional flexibility to select any of these solutions depending on the requirement.

Scenario 2: Multiple Solutions with different Tasks

Figure 3: An optimal solution producing all three products

Figure 4: An optimal solution producing only two products

In this article, we have presented an algorithm for the determination of multiple global solutions in batch scheduling industries. The algorithm is straight forward and can be very useful to industries as it offers a variety of equivalent solutions that can be implemented. Future extensions of this work can include the determination of pareto solutions with respect to different objectives and possibly enriching the underlying hybrid algorithm.

References:

1. Maravelias, C. T., & Grossmann,
   I. E. (2003) Industrial and Engineering Chemistry Research, 42(13), 3056?3074.
2. Ierapetritou, M. G., & Floudas, C. A. (1998) Industrial and Engineering Chemistry Research, 37, 4341?4359.
3. Lee, K.-H., Park, H. I., & Lee, I.-B. (2001). Industrial and Engineering Chemistry Research, 40, 4902? 4911.
4. Castro, P., Barbosa-Povoa, A. P. F. D., & Matos, H. (2001). Industrial and Engineering Chemistry Research, 40, 2059?2068.
5. Maravelias, C. T., & Grossmann,
   I. E. (2004) Computers and Chemical Engineering 28 (2004) 1921?1949
6. Harjunkoski, I., & Grossmann,
   I. E. (2002) Computers and Chemical Engineering, 26, 1533?1552.
7. Jain, V., & Grossmann,
   I. E. (2001) INFORMS Journal in Computing, 13, 258?276.
8. Tawarmalani, M.; Sahanidhis N.V. (2002). Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Kluwer Academic Publishers,
   BostonMA.