非确定型指派问题的求解算法

doi:10.3778/j.issn.1002-8331.2009.15.018

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (15): 61-63.DOI: 10.3778/j.issn.1002-8331.2009.15.018

非确定型指派问题的求解算法

李岩,郭强

西北工业大学理学院应用数学系，西安 710072

收稿日期:2008-04-01 修回日期:2008-06-11 出版日期:2009-05-21 发布日期:2009-05-21
通讯作者: 李岩

Algorithm for uncertainty assignment problem

LI Yan,GUO Qiang

Department of Applied Mathematics，School of Science，Northwestern Polytechnical University，Xi’an 710072，China

Received:2008-04-01 Revised:2008-06-11 Online:2009-05-21 Published:2009-05-21
Contact: LI Yan

摘要/Abstract

摘要： 考虑了一类非确定型指派问题，每人所承担的工作数不确定，按每人至少承担一项工作，每项工作只允许一人承担的指派原则，针对人员无工作数限制和有工作数限制两种情况加以讨论和分析，借鉴Floyd算法的负回路思想，提出了一种迭代算法，并给出了应用此算法求解的具体实例。实验表明：与其他求解算法相比，该算法求解规模小，效率高，应用简便，易于编程实现。

关键词: 指派问题, 最少耗费, Floyd算法

Abstract: The uncertainty assignment problem in which the number of jobs that every person takes is uncertain is considered.One job is to be allocated to exactly one person and each person does at least one job.The cost minimizing problems of person with unlimited capacity and person with limited capacity are discussed and analyzed.The aim is to find the feasible assignment which minimizes the total cost for completing all the jobs.An algorithm based on the Floyd iterative method is proposed for the assignment problem to find an optimal feasible assignment，an example of its application is provided.The algorithm is shown convinient.

Key words: assignment problem, cost minimizing assignment problem, Floyd algorithm

李岩,郭强. 非确定型指派问题的求解算法[J]. 计算机工程与应用, 2009, 45(15): 61-63.

LI Yan,GUO Qiang. Algorithm for uncertainty assignment problem[J]. Computer Engineering and Applications, 2009, 45(15): 61-63.

[1]	刘兵兵1，周伟平1，沈玲2. 灰色线性双层指派问题的智能全局优化方法[J]. 计算机工程与应用, 2016, 52(8): 38-42.
[2]	李超燕1，裴林滔2. 基于宏与全局变量Floyd并行算法的性能对比[J]. 计算机工程与应用, 2014, 50(16): 45-47.
[3]	李巍¹，郭强¹，曹华². 具有成功率约束的最优匹配问题[J]. 计算机工程与应用, 2011, 47(4): 33-35.
[4]	周莉1，张维华2，徐射雕1. 求解指派问题的一次性分配算法[J]. 计算机工程与应用, 2011, 47(18): 135-138.
[5]	杨皎平1，高雷阜2，王俊2. 装卸联盟车辆路径问题及两阶段优化方法[J]. 计算机工程与应用, 2011, 47(14): 217-221.
[6]	范昌胜¹，郭强¹，岳爱峰². 节点间有转向限制的网络最优路径算法[J]. 计算机工程与应用, 2009, 45(23): 59-62.
[7]	李敏郭强刘红丽. 多车场多配送中心的物流配送问题研究[J]. 计算机工程与应用, 2007, 43(8期): 202-204.
[8]	郭强. 人数少于任务数的全指派问题的迭代算法[J]. 计算机工程与应用, 2007, 43(24): 91-93.

非确定型指派问题的求解算法

Algorithm for uncertainty assignment problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics