一种任务分配问题的快速剪枝优化算法

• 作者: 井哲 周德云 马云红
• 来源期刊: 西北工业大学学报
• 学科: 数学
• 关键词: 算法 任务分配 运筹学 剪枝优化算法 无人机
• 年，卷（期）: 2013,（1）
• 页码范围: 40-43
• 页数: 4页
• 分类号: O22
• 字数: 2935字
• 语种: 中文

摘要

任务分配问题是运筹学中的一类规划问题,求解这类问题的比较经典的算法是匈牙利算法,但匈牙利算法在求解大规模任务分配时运算效率不高.文章提出了一种新的求解任务分配问题的方法——剪枝优化算法.算法通过逐步剔除已确定的部分分配方案对应代价矩阵元素,逐次降低分配问题的规模,从而实现快速求解全局任务分配问题.对于n个主体执行n个任务的分配问题,进行(n-1)次操作就可以获得最优解.论文进行了相应的仿真,将文章提出的算法和匈牙利算法做了比较.仿真结果表明,该算法与传统匈牙利算法计算结果一致,但计算耗时远远小于匈牙利算法,即该算法大大提高了任务分配问题的求解速度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周德云	西北工业大学电子信息学院	198	1485	19.0	29.0
2	马云红	西北工业大学电子信息学院	16	231	8.0	15.0
3	井哲	西北工业大学电子信息学院	1	15	1.0	1.0