当前位置: 简表范文网 > 专题范文 > 公文范文 >

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

| 来源:网友投稿

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

相关推荐

热门文章

2022年争先创优演讲稿最新10篇(完整文档)

《争先创优演讲稿最新10篇》是一篇好的范文,觉得有用就收藏了,这里给大家转摘到。演讲稿具有宣传、鼓动、教育和欣赏等作用,它可以把演讲者的观点、主张与思想感情传达给听众以及读者,使他们信服并在思想感情上产生共鸣。下面小编给大家带来关于争先创优演讲稿,希望会对大家的与有所帮助。争先创优演讲稿1

共青团员自我总结400字

《2022共青团员自我总结400字》是一篇好的范文,好的范文应该跟大家分享,希望对网友有用。作为一个新时期的共青团员,思想****理论是不可或缺的,共青团员是中国共产党的后备力量,也是党的生命力的源泉,理论上的成熟是****上成熟的基础,****上的清醒来源于理论上的坚定。以下是小编整理的2022共

2022年爱细节作文600字初中范本

《2022爱的细节作文600字初中范文【】》是一篇好的范文,觉得应该跟大家分享,希望对网友有用。爱是冬日的一缕阳光,使饥寒交迫的人感到人间的温暖;爱是一场洒落在久旱的土地上的甘霖,使濒临绝境的人重新看到生活的希望;爱是一首飘落在夜空里的歌谣,使孤苦无依的人获得心灵的慰藉。下面小编为大家整理了20

共青团员个人总结参考五篇(范文推荐)

《共青团员个人总结参考五篇》是一篇好的范文,觉得应该跟大家分享,希望大家能有所收获。一年来,在团组织和各位老师的热心支持和帮助下,认真做好本职,积极完成学校布置的各项任务。以下是小编整理的共青团员个人总结参考范文五篇,欢迎阅读分享。共青团员个人总结参考1一个学年以来,在团组织的正确领导和帮助下,我在

2022年猪场学习心得体会合集

《猪场学习心得体会》是一篇好的范文,好的范文应该跟大家分享,希望大家能有所收获。当受到启发,对生活有了新的感悟时,将其记录在心得体会里,让自己铭记于心,这样可以记录自己的思想活动。那么心得体会到底应该怎么写呢?下面小编给大家带来学习心得体会,希望大家喜欢!猪场学习心得体会111月25日至12月1

2022年教师年度考核个人总结例文

最近发表了一篇名为《教师年度考核个人总结例文》的范文,觉得有用就收藏了,重新编辑了一下发到。在日常生活或是工作中,我们经常会写总结,面对年末的时候,你们知道教师是怎么写的工作总结?来了解下吧!以下是小编为大家带来的2022教师年度考核个人总结例文,希望您能喜欢!教师年度考核个人总

2022年新员工培训心得怎么写合集通用(全文)

最近发表了一篇名为《新员工培训心得怎么写通用》的范文,感觉很有用处,重新整理了一下发到这里。培训能够拓展员工的视野,提升员工的能力,让员工在培训之中成长。员工培训心得对经历过员工培训的人具有许多的影响,你知道它的写法?你是否在找正准备撰写“新

关于珍爱生命作文800字高中【精选推荐】

范文参**网最近发表了一篇名为《2022关于珍爱生命的作文800字高中【】》的范文,感觉写的不错,希望对您有帮助,重新整理了一下发到这里。在平日的学习、工作和生活里,大家都不可避免地要接触到作文吧。下面小编为大家整理了2022关于的作文800字高中【5

2022清明网上祭英烈活动心得感悟经典范本10篇600字

本页是最新发布的《清明网上祭英烈活动心得感悟经典范文10篇600字》的详细范文参考文章,觉得有用就收藏了,希望大家能有所收获。清明祭心得感悟经典范文10篇600字说到清明节这个大家熟悉的节日,大家一定都是去祭拜祖先!但是可曾想过在清明节这天来祭奠我们的英烈们呢?下面是小编为您推荐

2022年度《公民节约用水行为规范》倡议书范本

最近发表了一篇名为《2022《公民节约用水行为规范》倡议书范文【五篇】》的范文,感觉很有用处,看完如果觉得有帮助请记得(CTRL+D)收藏本页。虽然人类已浪费了许多,但是人类们已经感觉到水的可贵而开始保护起来。在此大家一起杜绝浪费水之源,保护水资源吧。下面小编在这里为大家精心整理了几篇20

愚人节祝福语简短一句话大全(完整文档)

本页是最新发布的《2022愚人节祝福语简短一句话大全》的详细范文参考文章,好的范文应该跟大家分享,希望大家能有所收获。节的历史起源于法国,最初是法国的一些主张变革的人为嘲笑那些因循守旧的人而在4月1日使出一些骗人的招数。后逐渐成为西方及美国的民间传统节日,现在也成为东方很多国家人们喜爱的节

2022全国中小学生安全教育日心得体会三篇

最近发表了一篇名为《2022全国中小学生安全教育日心得体会三篇》的范文,感觉写的不错,希望对您有帮助,重新编辑了一下发到。2022全国中小学生日心得体会三篇为贯彻落实珍爱,安全第一为主题的中小学安全日教育活动,我校领导高度重视,紧紧围绕安全日安全教育这一主线,在师生中开展了丰富多