Apply heuristics and meta-heuristics to large-scale process batch scheduling

Abstract

Large-scale scheduling problems are still challenges to academic researchers and industrial practitioners. With the high complexity and multitudinous constraints existing in the process industry, process scheduling problems are more difficult to solve than the discrete machine scheduling problems. Traditionally, the process scheduling researchers usually formulate the problems into mathematical models in which so many constraints are expressed by equations or inequalities. The mathematical models can theoretically prove the optimality, and obtain optimal or acceptable solutions to small-sized problems. However, for the practical large-scale scheduling problems, it is still hard to achieve acceptable solutions within reasonable computational time by using such mathematical models. That is why scheduling by heuristics and experiences is still popular in real industrial world. In this chapter, heuristics and meta-heuristics have been developed to solve large-scale complex process batch scheduling problems, with the purpose to enhance the feasibility, solution quality and solution speed. In this chapter, an extensive review on the process scheduling is first conducted, which includes the complexity of process scheduling and the available solution methods, and then the strategies to solve large-scale process scheduling problems are analyzed and summarized. In fact, we have dedicated quite some energy to the research on the solution of large-scale problems, focusing on heuristics and meta-heuristics. In this chapter, three types of process scheduling problems are solved using these methods. For the single-stage process scheduling in batch plants with parallel units, which is actually similar to the parallel machine scheduling, a comprehensive set of dispatching rules for a class of scheduling objectives were formed by using the impact factors analysis method. In selecting the suitable heuristic rule(s) for diverse scheduling problems, novel rule-evolutionary approaches were proposed to avoid tedious simulation experiments. These genetic-based approaches not only evolve the solutions of the problems, but also automatically select the effective heuristic knowledge to solve the problems. In solving the very difficult multi-stage process scheduling problems (similar to the hybrid flow shop), we have adopted forward/backward assignment strategies, active scheduling techniques and position selection rules in the proposed genetic algorithms. All these measures effectively enhance the solution quality and solution speed. Besides, based on the concept of evolutionary gradient, a global search framework was proposed to make full use of the search ability of the meta-heuristics for the globally optimal or near-optimal solutions. The scheduling of multi-purpose multi-product batch plants with network structures is more common and representative in the process industry, hence more widely studied by researchers, usually using mathematical models for small-size problems. Large-size problems are still great challenges for further study. In this chapter, a pattern matching method for the large-scale multi-purpose scheduling problems is introduced. Different from the conventional cyclic scheduling and decomposition methods, a significant feature of the pattern matching method is that the growth of problem size may not directly lead to the growth of computational time and complexity as usual. This is indeed practicable in solving large-scale real-world problems. © 2012 by Nova Science Publishers, Inc. All rights reserved.