THESIS
2007
xxix, 301 leaves : ill. ; 30 cm. + 1 CD-ROM (4 3/4 in.)
Abstract
Due to the complexity existing in the process industry, traditionally, researchers in the process scheduling area mainly applied mathematical programming methods to small-size problems. This thesis research aims at the study and development of meta-heuristic methods and their hybrids for large-scale complex process scheduling problems, with the purpose to enhance the feasibility, solution quality and solution speed. Specifically, four typical classes of problems have been studied. They are zero-wait, single-stage, multi-stage and multi-purpose scheduling problems,...[
Read more ]
Due to the complexity existing in the process industry, traditionally, researchers in the process scheduling area mainly applied mathematical programming methods to small-size problems. This thesis research aims at the study and development of meta-heuristic methods and their hybrids for large-scale complex process scheduling problems, with the purpose to enhance the feasibility, solution quality and solution speed. Specifically, four typical classes of problems have been studied. They are zero-wait, single-stage, multi-stage and multi-purpose scheduling problems,
To testify the effectiveness of the meta-heuristic methods, the genetic algorithm, tabu search, particle swarm optimization and their hybrid are first implemented for the solution of the well-known traveling salesman problems, and then applied to zero-wait scheduling problems. It is found that a complex hybrid algorithm that consists of several local search techniques is not the practical choice for large-scale industrial applications.
Through the comparative study of mixed-integer linear programming (MILP), the simple rule-used method, random search and genetic algorithm for the single-stage scheduling, and the simulation experiments on the performance of different heuristic rules in a algorithm, it is found that the heuristic rules incorporated in the algorithm can cut the solution space and raise the solution speed greatly, and it is significant to select a suitable rule for the problems with different objectives and conditions. To avoid tedious simulation work to select appropriate case-dependent rules, novel automatic rule-evolutionary approaches are proposed, which work with a comprehensive set of rules from the impact factors analysis. Such approaches not only evolve the solutions as usual, but also automatically select the knowledge to solve the problems.
In solving the challenging multi-stage scheduling problems, proper assignment strategies, the active scheduling technique and position selection rules are found to be effective measures to enhance solution quality and solution speed, which enable the proposed genetic algorithm to gain outstanding performance compared with MILP. Subsequently, a global search framework that allows a local search to be executed iteratively until the evolutionary gradient disappears is designed. This framework is scalable to other large-size combinatorial problems.
A binary coding genetic algorithm has been developed for the scheduling of a typical multi-purpose batch plant. The algorithm utilizes heuristics for maximum production and logical relationships existing in the plant structure. A pattern matching method for the multi-purpose scheduling problems is proposed. Different from the conventional cyclic scheduling and decomposition methods, a significant feature of the pattern matching method is that the increase of problem size may not result in the increase of computational time and complexity as usual. This is practicable in solving large-scale industrial scheduling problems.
Post a Comment