非方阵指派问题的求解

作者：杨丽英; 韩建达; 聂义勇

来源：信息与控制, 2009, (06): 641-645+652.

• 极大极小指派问题
• 总体极小指派问题
• 混合整数线性规划
• 矩阵作业法
• 行优先选取算法 minimax assignment problem
• global-minimum assignment problem
• mixed integer linear programming(MILP)
• operations on matrix
• selection algorithm of precedence rows

本文将2类方阵指派问题——极大极小和总体极小指派问题——的矩阵作业解法推广到非方阵情形,即求解任务与人员数目不等的指派问题,且维持矩阵作业法的效率.假定m>n,则按本文行优先选取算法求解m×n非方阵指派问题的最大逻辑运算量为O(mn2),其效率通常与执行一轮覆盖的矩阵作业法相当.

• 单位
  中国科学院沈阳自动化研究所; 中国科学院大学; 机器人学国家重点实验室