(485c) A Novel Hybrid Algorithm for Scheduling of Multipurpose Batch Process

As the incremental market demands towards low-volume manufacture and various product categories, a growing number of researchers has been devoted to the investigation on batch processes [1,2]. The inherent flexibility of multipurpose batch process on processing route and shared facilities provides it wide application prospect in industry [2]. As one of the key managerial tools, process scheduling can greatly improve profit and save cost while saving makespan reflected on optimized production schedule. Mathematical programming is the most generally used method to address the batch process scheduling, being classified into sequence-based and time-grid-based models [3]. These formulations show good performance on handling scheduling with various processing features, such as variable processing time, storage policies and intermediate deliveries/demands. Continuous-time formulations [4,5] can effectively address multipurpose process scheduling in small-scale problems but often require large computational time or fail to converge to optimality for industrial-scale applications. The discrete-time formulation with tightening methods [6] is more computationally efficient and can handle intractable large-scale scheduling in reasonable time frames. However, in this approach, the optimal number of time points is not known a priori, which is often identified through the iterative procedure. As a result, the computational time is greatly increased.

Metaheuristics such as genetic algorithm (GA), tabu search and particle swarm optimization, have been proven capable to generate good scheduling solutions in a reasonable computational time even for large-scale batch processes. Many studies [7,8] confirmed that the GA shows good exploration of search space for multipurpose process scheduling attributed to its characteristics on inherent parallelism and strong global search ability. Also, GA can significantly reduce the computational time compared with mathematical programming where excessive CPU time is usually required for complicated scheduling problems. However, most existing GA proposed for multipurpose batch processes in literatures are less generalized and easy to prematurely converge to local optimality. Hybrid algorithm [9, 10] combining the advantages of multiple aforementioned methods can eliminate the limitations of single algorithm and show prominence on solving challenging large-scale problems.

In this work, we proposed a novel hybrid algorithm for scheduling of multipurpose batch process, which combines the strengths of GA on fast convergence and sequence-based mixed-integer linear programming (MILP) formulation on ensuring global optimum. The goal is to determine batching, allocation and sequencing of tasks eventually minimizing the Makespan under demand requirement. The hybrid algorithm comprises two stages: firstly, a new-designed GA is used to quickly generate feasible solutions, which do not require the iterative procedure to identify the optimal number of time points and hence significantly reduce the computational time. The obtained batching and sequence decisions are then used to fix some corresponding binary variables in MILP model. Then, the sequence-based formulation is quickly solved to optimality. Different fixing strategies of binary variables will be compared and identify the best one. In GA, a three-part encoding method is designed based on real value encoding way to direct batching and assigning determination and impact the processing sequence of tasks. Constraints concerning unit/storage capacity, material balance and product demand are handled in the decoding procedure to guarantee feasible solutions. We use elitist strategy and roulette wheel method [11] to select good individuals in each population. And a special crossover method was devised for the three-part real-value chromosome. We develop the sequence-based MILP formulation referring the model of Pan [12] and improve its efficiency by reformulating the big-M constraints concerning sequence and using less big-M terms to monitor inventory level of storage.

To evaluate the performance of the proposed method, four benchmark examples from the literature [5, 6] are solved using the proposed hybrid algorithm. Results show that the proposed algorithm can successfully generate global optimal solutions in all instances. It demonstrates general applicability and strong convergent performance. Compared with existing models, the hybrid algorithm can yield good quality solutions within shorter computational time. For example, in P9 and P11 of the Kallrath example, the method of Vooradi and Shaik [5] cannot converge to optimality in 40000s. By contrast, the proposed algorithm solves these two instances to optimality within 200 s, decreasing the CPU time over two orders of magnitude. In the most complicated instance P0, our approach reports a CPU time reduction by 37.5% compared to that of Velez et al. [6]. More importantly, the hybrid algorithm always generates better solutions than the designed GA.

References

1. Rakovitis N, Zhang N, Li J, Zhang LP. A new approach for scheduling of multipurpose batch processes with unlimited intermediate storage policy. Chem. Sci. Eng. 2019; 13(4):784-802.

2. Rakovitis N, Li J, Zhang N. An improved approach to scheduling multipurpose batch processes with conditional sequencing. Aided Chem. Eng. 2019; 46:1387-1392.

3. Harjunkoski I, Maravelias CT, Bongers P, et al. Scope for industrial applications of production scheduling models and solution methods. Comput Chem Eng. 2014; 62:161-193.

4. Vooradi R, Shaik MA, Gupta NM. Three-index model for Westenberger–Kallrath benchmark scheduling problem. AIP Conf. Proc. 2010; 1298:380–385.

5. Vooradi R, Shaik MA. Improved three-index unit-specific event-based model for short-term scheduling of batch plants, Comput Chem Eng. 2012; 43:148-172.

6. Velez S, Merchan AF, Maravelias CT. On the solution of large-scale mixed integer programming scheduling models. Eng. Sci. 2015; 136(2):139-157.

7. He Y, Hui CW. A binary coding genetic algorithm for multi-purpose process scheduling: A case study. Chem. Eng. Sci. 2010; 65(16):4816-4828.

8. Woolway M, Majozi T. A novel metaheuristic framework for the scheduling of multipurpose batch plants. Chem. Eng. Sci. 2018; 192:678-687.

9. Rakovitis N, Li D, Zhang N, et al. Novel Approaches for Energy-Efficient Flexible Job-Shop Scheduling Problems, Eng. Trans. 2020; 20: 823-828.

10. Lee H, Maravelias CT. Combining the advantages of discrete- and continuous-time scheduling models: Part 1. Framework and mathematical formulations, Comput Chem Eng. 2018; 116:176-190.

11. Beheshti Z, Shamsudding S. A review of population-based meta-heuristic algorithms, Int J Adv Soft Comput Appl. 2013; 5:1–35.

12. Pan M, Qian Y, Li XX. A novel precedence-based and heuristic approach for short-term scheduling of multipurpose batch plants. Eng. Sci. 2008; 63:4313-4332.