HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Chemical and Biomolecular Engineering >
CBME Journal/Magazine Articles >

Please use this identifier to cite or link to this item:
Title: Genetic algorithm based on heuristic rules for high-constrained large-size single-stage multi-product scheduling with parallel units
Authors: He, Yaohua
Hui, David Chi Wai
Keywords: Parallel unit scheduling
Mixed-integer linear programming
Random search
Heuristic rule
Genetic algorithm
Issue Date: 2007
Citation: To be published on Chemical engineering and processing
Abstract: This paper presents a heuristic rule-based genetic algorithm (GA) for large-size high-constrained single-stage multi-product scheduling problem (SMSP) with parallel units. SMSP can be classified into two types: type one is the problem with changeover and process constrains (CP constraints); type two is that without CP constraints. This paper is mainly concerned with type one. SMSP has been widely studied by the researchers. Most of them used mixed-integer linear programming (MILP) formulation to solve the problem. When the problem size increases linearly, the computation time of MILP will increase exponentially. It is very difficulty for MILP to solve large-size problem. Therefore, the researchers often use small instances to illustrate their MILP model. To solve large-size classical scheduling problems, meta-heuristic methods, like GA, are widely used. However, due to the CP constraints in SMSP, it is not easy to obtain feasible solutions in heuristic search. Hence, some authors concluded that GA is not suitable for this type problem, especially large-size problem. Indeed, if quite a few CP constraints exist, it will take GA plenty of time to generate feasible solutions. Nevertheless, by replacing the forbidden changeovers and processes with a large penalty numerical value, the problem is changed to be type two. By this penalty method, the search time of GA to large-size SMSP under CP constraints is reduced greatly. In our proposed method, GA is combined with heuristic rule that greatly reduces the solution space and the search time. Through comparison of computation results of MILP, random search and GA, GA demonstrates promising performance in solving large-size high-constrained SMSP.
Rights: Chemical engineering and processing © 2007 Elsevier. The Journal's web site is located at
Appears in Collections:CBME Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
Paper1HeuristicrulebasegeneticalgorithmforlargesizehighconstrainedsinglesatemultiproductschedulingwithParallelUnits.pdf398KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.