双目标瓶颈指派问题的遗传算法

黄沙日娜　赵国亮　朱捷

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

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

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

1 引 言

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

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

指派问题在生产和服务系统中有着广泛的应用. 例如在咨询服务行业，决策者或者管理人员根据咨询师以往的工作表现和顾客反馈，可以给出不同咨询师完成某项工作的合适性，即费用. 经典指派问题的目标是要使这项费用最大化. 本文将在此基础上，同时考虑咨询师（工人）对工作的排名偏好，建立双目标瓶颈指派问题的模型，进而将此问题转化为单目标规划问题，并设计遗传算法来求解.

同样，模型（4）的最优解也是问题（2）的Pareto最优解. 问题（2）到模型（4）的转化方式也是处理多目标优化的常用方法.模型（3）与模型（4）相比其优势在于约束条件相较于问题（2）没有增加，问题的规模没有增大，利用我们给出的编码、交叉和变异算子可以保证个体的可行性.

参考文献

[1] DF VOTAW， A ORDEN. The personnel assignment problem[C]//Symposium on Linear Inequalities and Programming. Scoop 10， US Air Force， 1952： 155-163.

[2] H W KUHN. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly， 1955， 2（1/2）： 83-97.

[3] J GORSKI， K KLAMROTH， S RUZIKA. Generalized multiple objective bottleneck problems[J]. Operations Research Letters， 2012， 40（4）： 276-281.

[4] L LIU， H MU， Y SONG， et al. The equilibrium generalized assignment problem and genetic algorithm[J]. Applied Mathematics and Computation， 2012， 218（11）： 6526–6535.

[5] A A PESSOA， PM HAHN， M GUIGNARD， et al. Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization technique[J]. European Journal of Operational Research， 2010， 206（1）： 54-63.

[6] PA KROKHMAL， PM PARDALOS. Random assignment problems[J]. European Journal of Operational Research， 2009， 194（1）： 1-17.

[7] F LI， LD XU， C JIN， et al. Random assignment method based on genetic algorithms and its application in resource allocation[J]. Expert Systems with Applications， 2012， 39（15）： 12213-12219.

[8] PN TAPKAN， LZBAKIR， A BAYKASOGLU. Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking[J]. Expert Systems with Applications， 2013， 40（3）： 892-898.

[9] 林浩，林澜. 有负荷约束的指派问题[J]. 经济数学，2013，30（1）： 17-21.

[10]D W PENTICO. Assignment problem： A golden anniversary survey[J]. European Journal of Operational Research， 2007， 176（2）： 774-793.

[11]葛悦. 模糊环境下若干网络优化问题的模型及其算法研究[D]. 哈尔滨：哈尔滨工业大学理学院数学系， 2012.

[12]D Z DU， P M PARDALOS. Minmax and Applications[M]. Netherland： Kluwer Academic Publishers， 1995.

[13]I H TOROSLU， Y ARSLANOGLU. Genetic algorithm for the personnel assignment problem with multiple objectives[J]. Information Sciences， 2007， 177（3）： 787–803.

[14]S Y LIN， S J HORNG， T W KAO， et al. Solving the bi-objective personnel assignment problem using particle swarm optimization[J]. Applied Soft Computing， 2012， 12（9）： 2840-2845.

[15]A ZINFLOU， C GAGNE， M GRAVEL. GISMOO： A new hybrid genetic/immune strategy for multiple-objective optimization[J]. Computers & Operations Research， 2012，39（9）： 1951-1968.endprint

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

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

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

1 引 言

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

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

指派问题在生产和服务系统中有着广泛的应用. 例如在咨询服务行业，决策者或者管理人员根据咨询师以往的工作表现和顾客反馈，可以给出不同咨询师完成某项工作的合适性，即费用. 经典指派问题的目标是要使这项费用最大化. 本文将在此基础上，同时考虑咨询师（工人）对工作的排名偏好，建立双目标瓶颈指派问题的模型，进而将此问题转化为单目标规划问题，并设计遗传算法来求解.

同样，模型（4）的最优解也是问题（2）的Pareto最优解. 问题（2）到模型（4）的转化方式也是处理多目标优化的常用方法.模型（3）与模型（4）相比其优势在于约束条件相较于问题（2）没有增加，问题的规模没有增大，利用我们给出的编码、交叉和变异算子可以保证个体的可行性.

参考文献

[1] DF VOTAW， A ORDEN. The personnel assignment problem[C]//Symposium on Linear Inequalities and Programming. Scoop 10， US Air Force， 1952： 155-163.

[2] H W KUHN. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly， 1955， 2（1/2）： 83-97.

[3] J GORSKI， K KLAMROTH， S RUZIKA. Generalized multiple objective bottleneck problems[J]. Operations Research Letters， 2012， 40（4）： 276-281.

[4] L LIU， H MU， Y SONG， et al. The equilibrium generalized assignment problem and genetic algorithm[J]. Applied Mathematics and Computation， 2012， 218（11）： 6526–6535.

[5] A A PESSOA， PM HAHN， M GUIGNARD， et al. Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization technique[J]. European Journal of Operational Research， 2010， 206（1）： 54-63.

[6] PA KROKHMAL， PM PARDALOS. Random assignment problems[J]. European Journal of Operational Research， 2009， 194（1）： 1-17.

[7] F LI， LD XU， C JIN， et al. Random assignment method based on genetic algorithms and its application in resource allocation[J]. Expert Systems with Applications， 2012， 39（15）： 12213-12219.

[8] PN TAPKAN， LZBAKIR， A BAYKASOGLU. Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking[J]. Expert Systems with Applications， 2013， 40（3）： 892-898.

[9] 林浩，林澜. 有负荷约束的指派问题[J]. 经济数学，2013，30（1）： 17-21.

[10]D W PENTICO. Assignment problem： A golden anniversary survey[J]. European Journal of Operational Research， 2007， 176（2）： 774-793.

[11]葛悦. 模糊环境下若干网络优化问题的模型及其算法研究[D]. 哈尔滨：哈尔滨工业大学理学院数学系， 2012.

[12]D Z DU， P M PARDALOS. Minmax and Applications[M]. Netherland： Kluwer Academic Publishers， 1995.

[13]I H TOROSLU， Y ARSLANOGLU. Genetic algorithm for the personnel assignment problem with multiple objectives[J]. Information Sciences， 2007， 177（3）： 787–803.

[14]S Y LIN， S J HORNG， T W KAO， et al. Solving the bi-objective personnel assignment problem using particle swarm optimization[J]. Applied Soft Computing， 2012， 12（9）： 2840-2845.

[15]A ZINFLOU， C GAGNE， M GRAVEL. GISMOO： A new hybrid genetic/immune strategy for multiple-objective optimization[J]. Computers & Operations Research， 2012，39（9）： 1951-1968.endprint

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

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

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

1 引 言

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

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

指派问题在生产和服务系统中有着广泛的应用. 例如在咨询服务行业，决策者或者管理人员根据咨询师以往的工作表现和顾客反馈，可以给出不同咨询师完成某项工作的合适性，即费用. 经典指派问题的目标是要使这项费用最大化. 本文将在此基础上，同时考虑咨询师（工人）对工作的排名偏好，建立双目标瓶颈指派问题的模型，进而将此问题转化为单目标规划问题，并设计遗传算法来求解.

同样，模型（4）的最优解也是问题（2）的Pareto最优解. 问题（2）到模型（4）的转化方式也是处理多目标优化的常用方法.模型（3）与模型（4）相比其优势在于约束条件相较于问题（2）没有增加，问题的规模没有增大，利用我们给出的编码、交叉和变异算子可以保证个体的可行性.

参考文献

[1] DF VOTAW， A ORDEN. The personnel assignment problem[C]//Symposium on Linear Inequalities and Programming. Scoop 10， US Air Force， 1952： 155-163.

[2] H W KUHN. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly， 1955， 2（1/2）： 83-97.

[3] J GORSKI， K KLAMROTH， S RUZIKA. Generalized multiple objective bottleneck problems[J]. Operations Research Letters， 2012， 40（4）： 276-281.

[4] L LIU， H MU， Y SONG， et al. The equilibrium generalized assignment problem and genetic algorithm[J]. Applied Mathematics and Computation， 2012， 218（11）： 6526–6535.

[5] A A PESSOA， PM HAHN， M GUIGNARD， et al. Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization technique[J]. European Journal of Operational Research， 2010， 206（1）： 54-63.

[6] PA KROKHMAL， PM PARDALOS. Random assignment problems[J]. European Journal of Operational Research， 2009， 194（1）： 1-17.

[7] F LI， LD XU， C JIN， et al. Random assignment method based on genetic algorithms and its application in resource allocation[J]. Expert Systems with Applications， 2012， 39（15）： 12213-12219.

[8] PN TAPKAN， LZBAKIR， A BAYKASOGLU. Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking[J]. Expert Systems with Applications， 2013， 40（3）： 892-898.

[9] 林浩，林澜. 有负荷约束的指派问题[J]. 经济数学，2013，30（1）： 17-21.

[10]D W PENTICO. Assignment problem： A golden anniversary survey[J]. European Journal of Operational Research， 2007， 176（2）： 774-793.

[11]葛悦. 模糊环境下若干网络优化问题的模型及其算法研究[D]. 哈尔滨：哈尔滨工业大学理学院数学系， 2012.

[12]D Z DU， P M PARDALOS. Minmax and Applications[M]. Netherland： Kluwer Academic Publishers， 1995.

[13]I H TOROSLU， Y ARSLANOGLU. Genetic algorithm for the personnel assignment problem with multiple objectives[J]. Information Sciences， 2007， 177（3）： 787–803.

[14]S Y LIN， S J HORNG， T W KAO， et al. Solving the bi-objective personnel assignment problem using particle swarm optimization[J]. Applied Soft Computing， 2012， 12（9）： 2840-2845.

[15]A ZINFLOU， C GAGNE， M GRAVEL. GISMOO： A new hybrid genetic/immune strategy for multiple-objective optimization[J]. Computers & Operations Research， 2012，39（9）： 1951-1968.endprint