| 基于资源受限广义指派问题的分解启发式算法 |
| |
| 引用本文： | 杨子兰,李睿,张瑜.基于资源受限广义指派问题的分解启发式算法[J].数学的实践与认识,2017(2):148-154. |
| |
| 作者姓名： | 杨子兰 李睿 张瑜 |
| |
| 作者单位： | 云南大学旅游文化学院 信息科学与技术系,云南 丽江,674199 |
| |
| 基金项目： | 云南省教育厅科学研究基金项目(2016ZDX152)，云南大学旅游文化学院一般项目(2015XY08) |
| |
| 摘 要： | 资源受限广义指派问题(RGAP)是NP-难的,对RGAP问题给出一个分解启发式算法.通过分解目标函数及约束条件,把原问题分解成子问题的集合,并设计分解启发式算法找到该问题的满意解.最后,通过算例说明算法的有效性.
|
| 关 键 词： | 广义指派问题 分枝定界法 贪婪算法 启发式算法 |
A Decomposition Heuristic Algorithm Based on Resource Constrained Generalized Assignment Problem |
| |
| YANG Zi-lan,LI Rui,ZHANG Yu.A Decomposition Heuristic Algorithm Based on Resource Constrained Generalized Assignment Problem[J].Mathematics in Practice and Theory,2017(2):148-154. |
| |
| Authors: | YANG Zi-lan LI Rui ZHANG Yu |
| |
| Abstract: | The resource constrained generalized assignment problem(RGAP) is NP-Hard.In this paper,By decomposiug the objective function and the constraints,the RGAP model is decomposed into a set of sub-problems and the heuristic decomposition algorithm is presented to solve the RGAP problem.Also,we give some examples to illustrate how the heuristic decomposition algorithm works. |
| |
| Keywords: | generalized assignment problem branch and boud algorithm greedy algorithm heuristic decomposition algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
