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

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

| 来源:网友投稿

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

相关推荐

热门文章

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

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

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

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

共青团成立100周年作文600字(完整)

本页是最新发布的《2022共青团成立100周年作文600字【精选】》的详细范文参考文章,好的范文应该跟大家分享,这里给大家转摘到。共青团员是中国共产党的后备力量,也是党的生命力的源,理论上的成熟是****上成熟的基础,****上的清醒来源于理论上的坚定。下面是小编为大家带来的

2022祖国在我心中演讲稿最新10篇(范文推荐)

最近发表了一篇名为《祖国在我心中演讲稿最新10篇》的范文,感觉很有用处,希望大家能有所收获。演讲是一门艺术。好的演讲自有一种激发听众情绪、赢得好感的鼓动性。要做到这一点,首先要依靠演讲稿思想内容的丰富、深刻,见解精辟,有独到之处,发人深思,语言表达要形象、生动,富有感染力。下面小编给大家带

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

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

2022年度关于端正态度作文初三(精选文档)

《2022关于端正态度的作文初三【精选】》是一篇好的范文,觉得有用就收藏了,看完如果觉得有帮助请记得(CTRL+D)收藏本页。在生活、工作和中,大家都不可避免地要接触到作文吧,作文是通过文字来表达一个主题意义的记叙方法。下面小编为大家整理了2022关于端正的作文初三【精选】的相关内容,以供参

草房子第一章秃鹤心得感悟合集【精选推荐】

《草房子第一章秃鹤的心得感悟》是一篇好的范文,觉得有用就收藏了,这里给大家转摘到。草讲述了发生在20世纪60年代初江南水乡动人动情的童年故事。读完了草房子小说,你有着怎样的草房子读书?你是否在找正准备撰写“草房子第一章秃鹤的心得感悟”,下面小编收集了相关的素材,供大家写文参考!草房子第

2022年大学生档案自我鉴定300字10篇

2022年普通大学生个人社会实践实习报告精选服务社会做好思想准备和业务准备,公司内部电脑系统都是统一英文系统,就要求自己以职场……[详细]2022年党员思想汇报例文两篇【完整版】所以在以后的学习和生活中,经历过苦难的中国,工作以及生活中,特别是通过学习党章党纪……[详细]企业员工服务意识培训心得体会

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

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

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

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

2022百年奋斗谋复兴勇毅前行兴伟业学习心得体会范本合集

《2022百年奋斗谋复兴勇毅前行兴伟业学习心得体会范文》是一篇好的范文,觉得有用就收藏了,希望对网友有用。2022百年奋斗谋复兴勇毅前行兴伟业学习心得体会范文了不起的红色精神,值得永远待播与发扬下去!相信祖国将会更加强大,更加繁荣富强。下面是小编为您推荐2022百年奋斗谋复兴勇毅前

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

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