用于作业调度的基于瓶颈的多代理方法研究

《用于作业调度的基于瓶颈的多代理方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、用于作业调度的基于瓶颈的多代理方法研究作者姓名武瑞雪学校导师姓名、职称张立勇副教授领域软件工程企业导师姓名、职称藤村茂教授申请学位类别工程硕士提交学位论文日期2014年10月学校代码107011210122617学号分类号TN82TP31公开密级西安电子科技大学硕士学位论文用于作业调度的基于瓶颈的多代理方法研究作者姓名：武瑞雪领域：软件工程学位类别：工程硕士学校导师姓名、职称：张立勇副教授企业导师姓名、职称：藤村茂教授提交日期：2014年10月Multi-agentmethodbasedonbottleneckforsolvingJobShopScheduling

2、AthesissubmittedtoXIDIANUNIVERSITYinpartialfulfillmentoftherequirementsforthedegreeofMasterinSoftwareEngineeringByWuRuixueSupervisor:ZhangLiyongFujimuraShigeruDecember2014西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人

3、已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：日期：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合

4、学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。（保密的论文在解密后遵守此规定）本学位论文属于保密，在年解密后适用本授权书。本人签名：导师签名：日期：日期：摘要摘要随着工业化的快速发展，制造业的生产线变得越来越复杂，对于能及时处理订单的能力也要求越来越高。怎样设计一个好的调度方案成为了制造业成功的关键的因素之一。车间调度是一个经典的调度问题，始于上个世纪50年代。在车间调度问题中，当一个或多个活动的开始时间发生了改变，可能会产生活动操作时间上的冲突，则系统需要一个高效率的方法来调整调度方案。因为多代理方法可以快速得到一个可行解，所以本论文选择多代理方法

5、进行研究。多代理方法是指系统包含了一系列不同的代理，这些代理相互独立，并且每一个代理都有独自解决问题的能力和不同的方法。代理之间通过信息的更新及传达，进行合作和交互从而解决问题，当每一个代理上的个体不存在违反约束的情况，则得出最终结果。正是由于每个代理具有非常强的问题解决能力，所以多代理方法可以快速得到一个可行解。而根据调度理论上的研究，因为瓶颈机器对系统而言，有最紧的约束，所以瓶颈机器很大程度上决定了整个系统的性能。为了使多代理方法得到更好的解，本文在多代理方法的基础上运用了瓶颈策略，即选择出系统的瓶颈机器并对瓶颈机器上活动的处理加以优化。基于瓶颈策略的多代理算

6、法将系统分为了三个代理：生产作业代理，机器代理和瓶颈机器代理。瓶颈机器的优化包含两部分，一是指对瓶颈机器的初始化进行优化，二是指对解决冲突时的做法进行了优化，使优化的算法比原先算法有更进一步的提高。然而根据基于瓶颈策略的多代理系统解决问题的算法框架，虽然这个方法显示了良好的性能，但由于解决过程是一个循环的迭代，所以算法有陷入死锁的可能性。根据大量的能引起死锁产生的实验数据，总结出三种死锁和每种死锁产生的原因。为了使这三种死锁得以解决，在原算法的基础上，本文提出了两种方法：预防死锁和发现并解决死锁，并且努力减少因解决死锁所而带来对系统性能的影响。本文提出的方案可以在

7、较短时间内得到不错的调度方案，同时也解决了自身算法的缺陷-死锁。实验结果表明改进的算法成功地解决了较小规模问题中存在的死锁，对于较大问题，因为机器的分配方案非常多，所以不能一一测试，但在几百次的测试中没有检测到任何遗留的死锁。改进算法与原算法相比，针对相同问题，改进该算法可以得到更好的调度方案。与基于调度规则的算法比较中，虽然用时比基于调度规则的算法用时长，但是可以得到较好的可行解。在本文算法与禁忌搜索算法比较中，在某些问题上可以得到与禁忌搜索算法所的解相近似的解决方案。I西安电子科技大学硕士学位论文关键词：多代理，瓶颈，死锁，车间作业调度论文类型：应用基础技术类

8、IIABS