文档介绍：博士学位论文中国科学技术大学批处理机调度问题的模型与优化方法研究作者姓名:学科专业:导师姓名:完成时间:杜冰管理科学与工程陈华平教授二。一一年五月五日
,卜
’::.,
/兰觯骸中国科学技术大学学位论文原创性声明中国科学技术大学学位论文授权使用声明口保密!D本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外,论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作作者签名:作为申请学位的条件之一,学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权,即:学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅,可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。日公开签字日期:了明确的说明。导师签名:
摘要批处理机调度是调度问题的一个重要分支。不同于经典调度问题,在批处理机调度问题中,一台机器可以同时加工多个工件。由于这类调度问题不仅需要将工件指派到机器上,还包含将工件分批的决策问题,因此比经典调度问题更为复杂,很多己知的批调度问题均是难解问题。批处理机调度在现实生产环境中有着广泛的应用,包括半导体芯片生产,钢铁制造,货物运输等。合理的调度方案可以大幅提高生产效率,节省生产成本,因此对批处理机调度问题的研究有着重要的现实意义。尽管当前己有不少文献对批处理机调度问题进行研究,但这些研究仍然有着不足之处。一是研究的问题主要侧重于工件具有相同尺寸的较简单情形,较少涉及不同尺寸工件情况。二是求解方法多是设计精确求解算法解决小规模问题或是用简单启发式算法获得近似解,对于复杂的构造式方法较少有入研究。三是研究的目标集中在以为代表的生产效率型目标,而对于调度问题中的能源效率则鲜有关注。针对当前研究中存在的问题,本研究主要做了以下工作:泳劾嗍咏窍卵芯苛瞬煌叽绻ぜ砘鞫任侍狻B壑ち瞬钜旃件单机环境下的批调度问题实质为一种广义聚类问题,为求解该问题提供了一个新的途径。提出了批的空间浪费比的概念,将最小化。。的目标函数变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明。此外,以批的空间浪费比为基础,进一步定义了批间的距离度量,提出了批的约束凝聚聚类算法,并通过实验验证了算法的有效性。ú煌叽绻ぜ呐砘鞫任侍馔乒愕焦ぜ酱锏牟⑿谢境,提出并证明了该问题的两个不同下界。在此基础上设计了两种智能优化算法。一是基于工件序列编码的遗传算法,通过工件序列和—嬖蛏煞批,并设计了一个惴ɡ窗才排诨魃系募庸ぁA硗庖恢质腔诠造式分批的蚁群算法,算法同时考虑工件在尺寸和加工维度的特点作为启发式信息,指导蚂蚁不断寻找适合的工件加入当前批,直到所有分批构造完毕。对两种算法的性能及偏好,通过大量仿真实验进行了比较。茉葱饰侍馊谌氲鞫攘煊虻难芯恐小9菇嗽诜质钡缂厶跫拢以最小化电力成本和为目标的柔性流水车间批调度问题的模型。设计了三种不同的多目标优化算法来求解该问题:⒈冉狭巳炙惴ㄔ诓煌兰壑副晗的性能。
关键词:调度批处理机聚类蚁群优化多目标优化能源效率电力成要本摘
.,——.,.,,,,.:.琣甌
篒瓹簊琤,猳.,甌—琣..,.瓵—甌,—琧琣,