黄沙日娜　赵国亮　朱捷

摘 要 给出一种双目标瓶颈指派问题的新模型，本模型结合了决策者和工人两方面的因素，特别之处在于考虑到了工人对工作的排名偏好. 进而，将双目标瓶颈指派问题转化为单目标规划，并设计了解此问题的遗传算法，算法的解均为双目标瓶颈指派问题的Pareto最优解.

关键词 双目标； 瓶颈指派问题； 遗传算法； Pareto最优解

中图分类号 O221.6 文献标识码 A

1 引 言

经典指派问题是一类特殊的组合优化问题，是指将n项工作分配给n个工人去完成，且每个工人只能完成一项工作，每项工作只能由一个人来完成，不同的工人完成每一项工作的费用是不同的，从而求出最优指派. 所谓的最优是指使总体费用最大或者总体用时最小.

指派问题最早由Votaw和Orden提出^[1]， 1955年，Kuhn给出了解指派问题的匈牙利算法^[2]， 从此指派问题得到了真正的发展. 此后的几十年，指派问题的解法日趋成熟，出现了隐枚举法、分支定界法和割平面法等，但是用到最多的还是匈牙利法. 与此同时，还出现许多经典指派问题的变形，如瓶颈指派问题^[3]、平衡指派问题^[4]、半指派问题、多准则指派问题、分数指派问题、二次指派问题^[5]、随机指派问题^[6，7]、模糊指派问题^[8]以及带负荷约束的指派问题^[9]等，有关这些问题的介绍可参阅综述文章^[10]及其参考文献.

指派问题在生产和服务系统中有着广泛的应用. 例如在咨询服务行业，决策者或者管理人员根据咨询师以往的工作表现和顾客反……