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

Algorithm for uncertainty assignment problem

作　　者：李岩[1] 郭强[1] 

机构地区：[1]西北工业大学理学院应用数学系,西安710072

出　　处：《计算机工程与应用》2009年第15期61-63,66,共4页Computer Engineering and Applications

摘　　要：考虑了一类非确定型指派问题,每人所承担的工作数不确定,按每人至少承担一项工作,每项工作只允许一人承担的指派原则,针对人员无工作数限制和有工作数限制两种情况加以讨论和分析,借鉴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.

关 键 词：指派问题 最少耗费 FLOYD算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]