广义指派问题(GAP)分类与求解算法
表 1 GAP问题元启发式
算法 |
算法要点 |
主要文献 |
遗传算法 |
解的结构为一个n维数组,下标代表物品,数值代表背包 |
[11] |
变邻域搜索 |
随机使用不同邻域;设计容量超出罚函数,容许非可行解 |
[12] |
禁忌搜索 |
将局部最优解写入禁忌表 |
[13]、[14]、[15] |
参考文献
[1] 王周宏. 运筹学基础[M]. 北京交通大学出版社, 2011.
[2] Sahni S, Gonzalez T. P-complete approximation problems[J]. Journal of the ACM (JACM), 1976, 23(3): 555-565.
[3] Dobson G, Nambimadom R S. The batch loading and scheduling problem[J]. Operations research, 2001, 49(1): 52-65.
[4] 余英姿, 张强. 一类广义指派问题的有效解法[C]// 中国运筹学会学术交流会. 2004.
[5] Cheng C H, Goh C H, Lee A. Solving the generalized machine assignment problem in group technology[J].
Journal of the Operational Research Society, 1996, 47(6): 794-802.
[6] Kuhn H W. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly, 1955, 2(1‐2): 83-97.
[7] Ross G T, Zoltners A A. Weighted assignment models and their application[J]. Management Science, 1979, 25(7): 683-696.
[8] Mazzola J B, Neebe A W, Dunn C V R. Production planning of a flexible manufacturing system in a material requirements
planning environment[J]. International Journal of Flexible Manufacturing Systems, 1989, 1(2): 115-142.
[9] Nauss R M. The elastic generalized assignment problem[J]. Journal of the Operational Research Society, 2004, 55(12): 1333-1341.
[10] Mazzola J B, Wilcox S P. Heuristics for the multi‐resource generalized assignment problem[J]. Naval Research Logistics (NRL),
2001, 48(6): 468-483.
[11] Chu P C, Beasley J E. A genetic algorithm for the generalised assignment problem[J]. Computers & Operations Research,
1997, 24(1): 17-23.
[12] Yagiura M, Yamaguchi T, Ibaraki T. A variable depth search algorithm for the generalized assignment problem[M]//Meta-heuristics.
Springer, Boston, MA, 1999: 459-471.
[13]Dıaz J A, Fernández E. A tabu search heuristic for the generalized assignment problem[J]. European Journal of
Operational Research, 2001, 132(1): 22-38.
[14] Yagiura M, Ibaraki T, Glover F. An ejection chain approach for the generalized assignment problem[J].
INFORMS Journal on computing, 2004, 16(2): 133-151.
[15]Yagiura M, Ibaraki T, Glover F. A path relinking approach with ejection chains for the generalized assignment problem[J].
European journal of operational research, 2006, 169(2): 548-569.
[16] Haddadi S, Ouzia H. An effective Lagrangian heuristic for the generalized assignment problem[J].
INFOR: Information Systems and Operational Research, 2001, 39(4): 351-356.
[17] Narciso M G, Lorena L A N. Lagrangean/surrogate relaxation for generalized assignment problems[J].
European Journal of Operational Research, 1999, 114(1): 165-177.
[18]邢文训, 谢金星. 现代优化计算方法[M]. 清华大学出版社, 2006.
[19]Haddadi S, Ouzia H. An effective Lagrangian heuristic for the generalized assignment problem[J].
INFOR: Information Systems and Operational Research, 2001, 39(4): 351-356.
[20] Jeet V, Kutanoglu E. Lagrangian relaxation guided problem space search heuristics for generalized assignment problems[J].
European Journal of Operational Research, 2007, 182(3): 1039-1056.
- 点赞
- 收藏
- 关注作者
评论(0)