基于PSO-MAs算法的产品组合问题研究

运筹与管理 ›› 2014, Vol. 23 ›› Issue (1): 116-122.

基于PSO-MAs算法的产品组合问题研究

胡忠义, 鲍玉昆, 熊涛

华中科技大学管理学院,湖北武汉 430074

收稿日期:2012-01-03 出版日期:2014-01-25
作者简介:胡忠义(1987-),男,博士研究生,研究方向:智能优化建模与运作管理;鲍玉昆(1974-),男,教授,通讯作者,研究方向:智能预测与决策、运作管理;熊涛(1985-),男,博士研究生,研究方向:智能预测与决策、运作管理。
基金资助:
国家自然科学基金资助项目(70771042);中央高校基本科研业务费资助(HUST-2012QN208);湖北省人文社会科学重点研究基地现代信息管理研究中心资助项目

PSO based Memetic Algorithms for Product Mix Problems

HU Zhong-yi, BAO Yu-kun, XIONG Tao

School of Management, Huazhong University of Science and Technology, Wuhan 430074, China

Received:2012-01-03 Online:2014-01-25

摘要/Abstract

摘要： 针对多约束的产品组合问题,提出一种基于PSO的Memetic算法。该算法首先运用约束理论识别并剔除非瓶颈约束,然后基于伪效用比率设计了一个局部搜索算法,并将其加入到PSO算法的种群进化中,以增强PSO算法的局部学习能力。通过对算法在小规模和大规模算例中测试,表明该算法在小规模问题中优于许多已有算法,同时能在相对较短地时间内更有效地求解较大规模产品组合问题。因此本文提出的基于PSO的Memetic算法可以用来有效地求解实际中的产品组合问题。

关键词: 运筹学, 产品组合, 模因算法, 约束理论, 粒子群算法

Abstract: To solve the product mix problem with multiple constraints, a memetic algorithms is proposed based on particle swarm optimization(PSO). Firstly, the problem is simplified by recognizing and removing the non-bottlenecks based on the Theory of Constraints(TOC). Secondly, a pseudo utility ratio based local search is proposed to improve the exploitation ability of PSO. Both small-scale benchmark datasets and a group of randomly generated large-scale examples are used to test the proposed approach on solving the product mix problems. The computational results show that the proposed approach outperform some existing approaches, such as TOC, revised TOC, Tabu Search(TS), Simulated Annealing(SA)and Genetic Algorithms(GA), and can solve the large-scale problems more effectively. Hence, the proposed approach can be accepted as a practical approach to solve the product mix problem.

Key words: operation research, product mix problem, memetic algorithms, theory of constraints, particle swarm optimization

中图分类号:

O22
TP301.6

胡忠义, 鲍玉昆, 熊涛. 基于PSO-MAs算法的产品组合问题研究[J]. 运筹与管理, 2014, 23(1): 116-122.

HU Zhong-yi, BAO Yu-kun, XIONG Tao. PSO based Memetic Algorithms for Product Mix Problems[J]. Operations Research and Management Science, 2014, 23(1): 116-122.

参考文献

[1] Goldratt E M, The Haystack syndrome[M]. Croton-on-Hudson, NY: North River press, 1990.
[2] Fredendall L D, Lea B R. Improving the product mix heuristic in the theory of constraints[J]. International Journal of Production Research, 1997, 35(6): 1535-1544.
[3] Hsu T C, Chung S H. The TOC-based algorithm for solving product mix problems[J]. Production Planning & Control, 1998, 9(1): 36-46.
[4] Aryanezhad M B, Komijan A R. An improved algorithm for optimizing product mix under the theory of constraints[J]. International Journal of Production Research, 2004, 42(20): 4221-4233.
[5] Onwubolu G C. Tabu search-based algorithm for the TOC product mix decision[J]. International Journal of Production Research, 2001, 39(10): 2065-2076.
[6] Onwubolu G C, Mutingi M. Optimizing the multiple constrained resources product mix problem using genetic algorithms[J]. International Journal of Production Research, 2001, 39(9): 1897-1910.
[7] Onwubolu G C, Mutingi M. A genetic algorithm approach to the theory of constraints product mix problems[J]. Production Planning & Control, 2001, 12(1): 21-27.
[8] Chaharsooghi S K, Jafari N. A simulated annealing approach for product mix decisions[J]. Scientia Iranica, 2007, 14(3): 230-235.
[9] Wang J Q, Sun S D, Si S B, Yang H A. Theory of constraints product mix optimisation based on immune algorithm[J]. International Journal of Production Research, 2009, 47(16): 4521-4543.
[10] 王军强,孙树栋,余建军,司书宾.基于约束理论和免疫算法的产品组合优化研究[J].计算机集成制造系统,2006,12(12):2017-2043.
[11] Moscato P, Norman M G. A ‘memetic'approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems[J]. Parallel Computing and Transputer Applications, 1992. 177-186.
[12] Karapetyan D, Gutin G. A new approach to population sizing for memetic algorithms: a case study for the multidimensional assignment problem[J]. Evolutionary Computation, 2011, 19(3): 345-371.
[13] Kim S S, Smith A E, Lee J H. A memetic algorithm for channel assignment in wireless FDMA systems[J]. Computers & Operations Research, 2007, 34(6): 1842-1856.
[14] Li B B, Wang L, Liu B. An effective PSO-based hybrid algorithm for multiobjective permutation flow shop scheduling[J]. IEEE Transactions on Systems Man and Cybernetics Part A-Systems and Humans, 2008, 38(4): 818-831.
[15] Linhares A. Theory of constraints and the combinatorial complexity of the product-mix decision[J]. International Journal of Production Economics, 2009, 121(1): 121-129.
[16] Ray A, Sarkar B, Sanyal S. The TOC-based algorithm for solving multiple constraint resources[J]. IEEE Transactions on Engineering Management, 2010, 57(2): 301-309.
[17] Pirkul H. A Heuristic solution procedure for the multiconstraint zero-one knapsack problem[J]. Naval Research Logistics, 1987, 34: 161-172.
[18] Poli R, Kennedy J, Blackwell T. Particle swarm optimization: an overview[J]. Swarm Intelligence, 2007, 1: 33-57.
[19] Luebbe R, Finch B. Theory of constraints and linear programming: a comparison[J]. International Journal of Production Research, 1992, 30: 1471-1478.
[20] Lee T N, Plenert G. Optimising theory of constraints when new product alternatives exist[J]. Production and Inventory Management Journal, 1993, 34(3): 51-57.
[21] Plenert G. Optimizing theory of constraints when multiple constrained resources exist[J]. European Journal of Operational Research, 1993, 70: 126-133.
[22] Posnack A J. Theory of constraints: improper applications yield improper conclusions[J]. Production and Inventory Management, 1994, 35(1): 85-86.