考虑加工成本的双目标平行机批调度问题的启发式算法研究

【摘要】生产调度问题作为一个在生产制造领域中有着很强应用背景的组合优化问题,它是指在一定时间内对生产任务进行规划和分配以达到某项或某几项指标的过程。合理并且有针对性的调度方案在提高企业的生产效益,促进有限资源的合理利用等方面起到了巨大的推动作用。然而由于实际的生产调度问题往往具有约束条件多、目标问题种类多以及随机不确定性等特点,导致了不少调度问题都未能得到妥善合理地解决。其中很多问题已被证明属于NP难问题,因此如何针对复杂的生产调度环境设计简单高效的求解算法始终是批调度问题研究的侧重点。本文从调度问题的基础概念出发,介绍了关于描述一个具体的调度问题时所通用的表示方法、调度问题按不同研究角度形成的分类及其主要研究方法。其次,介绍了构成构成经典调度问题的四个必要条件。经典调度问题的假设之一,即任何机器无论在任何时刻至多只能加工一个工件。但在实际的工业生产环境中,为了缩短加工时间,提高生产效率,有的机器可以同时加工多个工件,这种类型的现代调度问题即为批调度问题。最后介绍了本文所要研究的批调度问题的一个分支：差异工件批调度,即待加工的工件集中各工件在尺寸上存在差异,而且需要满足属于同一批中的工件,其尺寸之和不能超过机器容量的条件。差异工件批调度问题相较于经典调度和工件尺寸均一致的传统批调度来说,其问题复杂程度要高出很多,更能适应现代复杂多变的生产环境需求。本文探讨了考虑工件自身加工成本的双目标平行机批调度问题,当前关于平行机环境下的研究主要集中于如何提高生产效率,即优化的目标函数主要是关于时间的函数(例如最大完工时间Cmax、总完工时间∑Cj),然而随着绿色制造理念的提出,生产中的能源效率问题也日益突出。在现有涉及到成本目标的批调度问题的研究中,主要考虑的是批的交货成本(即客户对每个批所要求的交货时间),而忽视了工件作为独立对象被分配加工时所产生的成本。针对考虑工件加工成本的双目标平行机批调度问题,本文提出了一个启发式优化算法。对于双目标的优化本文基于分级法思想,以最小化总完工时间为第一目标,以最小化机器总加工成本MOC为第二目标。对批调度过程中的两个阶段：分批以及批排序,分别利用启发式算法BFLPS和rank-s予以解决。通过仿真实验将本文设计的启发式算法与遗传算法及文献中现有的启发式算法进行性能比较并给出了性能分析,实验结果验证了本文算法对于优化双目标平行机批调度问题的有效性。
【作者】孙笑芸；
【导师】贾兆红；
【作者基本信息】安徽大学，计算机技术，2014，硕士
【关键词】平行机；双目标；差异工件批调度；分级法思想；启发式算法；

【参考文献】
[1]牛津.“花园”里的社会教育：H市S幼儿园小五班的文化描述研究[D].安徽大学,人类学,2014,硕士.
[2]黄宝平.员工培养流程与企业执行力关系研究[D].大连海事大学,企业管理,2013,硕士.
[3]杨成云.齿轮传动系统耦合振动响应及抗冲击性能研究[D].重庆大学,2006.
[4]芮虎.比价购物平台中网络爬虫的设计与实现[D].华东理工大学,软件工程,2013,硕士.
[5]降刚.金砖国家银行业竞争与效率比较研究[D].山西财经大学,金融学,2014,硕士.
[6]谢娟.黄斑水肿的光学相干断层扫描分析[D].山西医科大学,眼科学,2002,硕士.
[7]杨冬妮.淮安废黄河旅游开发初步研究[D].扬州大学,旅游管理,2011,硕士.
[8]张美琴.中国银行内蒙古分行中小企业信贷金融服务研究[D].内蒙古大学,工商管理,2012,硕士.
[9]马悦.先秦诸子散文的文学传播研究[D].西北师范大学,中国古代文学,2013,硕士.
[10]王楠.宋代绘画艺术市场研究[D].河北大学,艺术学,2014,硕士.
[11]章骁程.用反向有限元法从小冲杆试验中获得材料的断裂韧性参数[D].华东理工大学,化工过程机械,2014,硕士.
[12]童云华.用于扫描刻蚀加工的特种悬臂梁探针关键技术研究[D].安徽工程大学,机械制造及其自动化,2012,硕士.
[13]臧文静.极端气候条件下的建筑形态研究[D].北京建筑大学,建筑设计及其理论,2013,硕士.
[14]范雪峰.基于跨媒体特征向量的分类及多模态数据分析[D].吉林大学,网络与信息安全,2013,硕士.
[15]佟影,李凤兰,曹丽华.三元能量对落叶松、樟子松的作用[J].人天科学研究.1997(06)
[16]刘新.胞嘧啶脱氨酶APOBEC3F抗病毒调控机制的研究[D].吉林大学,生物化学与分子生物学,2014,硕士.
[17]何於家.《死亡简史》（第一章）翻译报告[D].四川外国语大学,翻译（专业学位）,2014,硕士.
[18]李武全,吴昭景,王会.一类上三角随机非线性系统的输出反馈控制[J].控制与决策,2012,10:1494-1498+1504.
[19]李瑞.活性污泥法除磷过程中胞内储存物质的红外光谱解析与应用[D].安徽建筑工业学院,市政工程,2012,硕士.
[20]张旭红.面向移动平台的新闻资讯系统设计与实现[D].北京交通大学,2012.
[21]李龙飞.高速铁路接触网跨距的确定[D].西南交通大学,电气工程,2014,硕士.
[22]江鸿宾.基于MM5-CALPUFF耦合体系研究关中城市群对西安市SO_2浓度贡献特征[D].长安大学,环境工程,2013,硕士.
[23]严校平.基于染料电聚合修饰的青霉素酶生物传感器的研究[D].安徽工程大学,发酵工程,2012,硕士.
[24]姜泽毅,张欣欣,董补全,陈晓丹,于百勤,夏建良,刘华飞.环形加热炉在线优化控制的研究与应用[J].冶金自动化,1999,05:28-31.
[25]刘晶星.基于临床路径的天津总医院单病种费用控制的系统研究[D].天津大学,公共管理,2013,硕士.
[26]朱琳.不同催化剂催化制备的GaN材料[D].太原理工大学,2013.
[27]邓峥宇.湖南省外商直接投资的环境效应[D].云南财经大学,国际贸易学,2014,硕士.
[28]鲁爱军.我国小额诉讼程序研究[D].山东大学,法律（专业学位）,2013,硕士.
[29]严彩萍.色调保持的自适应图像视频细节增强算法[D].浙江工商大学,计算机应用技术,2013,硕士.
[30]李应博.我国农业信息服务体系研究[D].中国农业大学,2005.
[31]秦静.神州数码服务器分销渠道发展战略研究[D].北京交通大学,2014.
[32]顾斌.Epstein-Barr病毒特异性细胞毒性T淋巴细胞在异基因造血干细胞移植中的作用[D].苏州大学,血液病学,2013,硕士.
[33]徐蓝.煤炭矿区可持续发展研究[D].湖南师范大学,人口、资源环境经济学,2013,硕士.
[34]韩冠军.食品供应链的政府监管体制研究[D].山东师范大学,工商管理（专业学位）,2012,硕士.
[35]倪士浩.西安地铁2号线穿越地裂缝段的限界设计[J].城市轨道交通研究.2008(04)
[36]何军.大数据对企业管理决策影响分析[J].科技进步与对策,2014,04:65-68.
[37]朱通.基于供应链金融的中小企业信用风险评价[D].浙江工业大学,2013.
[38]公维友.我国民主行政的社会建构研究[D].山东大学,政治学理论,2014,博士.
[39]苏奋振,周成虎,杜云艳,邵全琴,刘宝银.3S空间信息技术在海洋渔业研究与管理中的应用[J].上海水产大学学报,2002,03:277-282.
[40]唐华伦.重庆市主城区土地征收补偿工作中存在的问题与对策研究[D].西南大学,土地资源管理,2012,硕士.
[41]徐杰.浙江沿海富营养化与赤潮历史的沉积记录研究[D].浙江大学,环境科学,2004,硕士.
[42]乔钰淇.回收热电厂冷源损失用于区域供热的规划技术研究[D].哈尔滨工业大学,供热、供燃气、通风及空调工程,2013,硕士.
[43]傅锡洪.朱子鬼神观研究[D].复旦大学,中国哲学,2012,硕士.
[44]徐士帅.基于体裁的买卖合同语篇分析[D].黑龙江大学,外国语言学及应用语言学,2012,硕士.
[45]闫明月.时间序列相似性与预测算法研究及其应用[D].北京交通大学,2014.
[46]李光远.高职院校学生社团政治参与研究[D].河北师范大学,政治学理论,2012,硕士.
[47]潘莹.泛素C末端水解酶UCH-L1在SAMP8小鼠海马CA1区的增龄变化及意义[D].河北医科大学,人体解剖与组织胚胎学,2013,硕士.
[48]张永耀.新课改下高中课堂管理现状的教育现象学研究[D].西北师范大学,教育学原理,2013,硕士.
[49]宋明秀.山东省环境规制对FDI区位分布的影响[D].山东财经大学,国际贸易学,2013,硕士.
[50]张霖.地方政府执行力特征与考核指标的研究[J].河南科学,2014,11:2395-2398.