摘要
考虑了一类非确定型指派问题,每人所承担的工作数不确定,按每人至少承担一项工作,每项工作只允许一人承担的指派原则,针对人员无工作数限制和有工作数限制两种情况加以讨论和分析,借鉴Floyd算法的负回路思想,提出了一种迭代算法,并给出了应用此算法求解的具体实例。实验表明:与其他求解算法相比,该算法求解规模小,效率高,应用简便,易于编程实现。
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.
出处
《计算机工程与应用》
CSCD
北大核心
2009年第15期61-63,66,共4页
Computer Engineering and Applications
关键词
指派问题
最少耗费
FLOYD算法
assignment problem
cost minimizing assignment problem
Floyd algorithm
