Title: An evolutionary linear programming algorithm for solving the stock reduction problem

Authors: Gang Shen; Yan-Qing Zhang

Addresses: Computer Science Department, Georgia State University, P.O. Box 3994, Atlanta, GA 30302-3994, USA. ' Computer Science Department, Georgia State University, P.O. Box 3994, Atlanta, GA 30302-3994, USA

Abstract: It is very difficult to solve complex nested optimisation problems (optimising both parent and child problems at the same time). In this paper, we propose an evolutionary linear programming algorithm that combines Linear Programming (LP) and Genetic Algorithm (GA) to solve them. GA is used to optimise the parent problem, and the LP/GA hybrid algorithm is used to solve the sub-problem. The stock reduction problem (SRP) is a typical nested optimisation problem. The parent is a minimising stock mix problem (MSMP), and the child is a cutting stock problem (CSP). Simulation results have shown that our new hybrid algorithm can solve complex SRPs with high efficiency and accuracy. This new hybrid algorithm can be used in many other applications where integer and non-integer optimisation problems interact with each other, such as airline scheduling, shipping scheduling, etc.

Keywords: genetic algorithms; linear programming; complex nested optimisation; cutting stock problem; stock reduction problem; scheduling; simulation.

DOI: 10.1504/IJCAT.2012.049080

International Journal of Computer Applications in Technology, 2012 Vol.44 No.3, pp.171 - 179

Published online: 12 Sep 2012 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article