Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2929

Genetic algorithm based on heuristic rules for high-constrained large-size single-stage multi-product scheduling with parallel units

Authors He, Yaohua
Hui, Chi-Wai
Issue Date 2007
Source Chemical engineering and processing, v. 46, (11), 2007, NOV, p. 1175-1191
Summary This paper presents a genetic algorithm (GA) based on heuristic rules for high-constrained large-size single-stage multi-product scheduling problem (SMSP) with parallel units. SMSP has been widely studied, very often solved by using mixed-integer linear programming (MILP methods). When the problem size increases linearly, the computational time of MILP will increase exponentially. Therefore, it is very difficult for MILP to obtain acceptable solutions to the large-size problems within reasonable time. To solve the large-size scheduling problems, the preferred method in industry is the use of scheduling rules. However, due to the constraints in SMSP, the simple rule-based method may not guarantee the feasibility and quality of the solutions. In this study, random search based on heuristic rules is proposed first. Through exploring a set of random solutions, better feasible solutions are obtained. To improve the quality of solutions, GA based on heuristic rules is then proposed to evolve the random solutions. The heuristic rules play a very important role in the algorithm. However, the computational time of the GA increases dramatically due to some constraints that may create infeasibility. To overcome this, a penalty method is adopted. Through comparison of computational results of MILP, random search and GA, GA has demonstrated its effectiveness and reliability in solving the highly constrained large-size scheduling problems. (c) 2007 Elsevier B.V. All rights reserved.
Subjects
ISSN 0255-2701
Rights Chemical engineering and processing © 2007 Elsevier. The Journal's web site is located at http://www.sciencedirect.com.
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST