基于学习效应的单机调度总完工时间最小化问题研究

《基于学习效应的单机调度总完工时间最小化问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、?0_卷在桌大彥硕士学位论文论文题目基于学号故左的单机调度总完工对问最小化问题耐免作者姓名郑‘荟学科专业營理科学与工程导师姓名除料減完成时间二—年工力十豳科嗲敉水大嗲硕士学位论文基于学习效应的单机调度总完工时间最小化问题研究作者姓名：郑春荟学科专业：管理科学与工程导师姓名：陈华平教授完成时间：二—五年五月UniversityofScienceandTechnologyofChinaAdissertationformaster'sdegreeMinimizetotalcompletiontimeonasinglemachineschedulingproblemwithlearningeffect

2、considerationAuthor'sName:ChunhuiZhengSpeciality:ManagementScienceandEngineeringSupervisor:Prof.HuapingChenFinishedtime:May,2015中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成。除已特别力以标注和致谢的地外，论文屮包含：他人粒发及成撰、过的研究成柬。我丨：作的忠对本研究所做的献均论文中作了明确的说明。作者签名签期：中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国利学技术人学拥有

3、学位论文的部分使权，即‘校有权按有关规记卩又部机构送交论文的复印件和电子版允许论义被忾阅和借阅，以将‘位沦文编入《屮国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或丨丨描等复制手段保存、汇编学位论义。小人提夂的电文捫的内界和纸质论义的内转相致。保密的学位论文在解密后也遵守此规定。公斤□保密作者签名签字期签字曰期：么矽六摘要摘要在许多现实生产活动中因为有人的参与，人的学习活动会对生产过程产生重要的影响，因而在某些生产调度问题的研究中考虑其生产环境存在学习效应更具合理性。同时作为工件属性之一的释放时间是制定生产调度计划必须考虑的影响因素之一，直接关系到整个生产过程的效率高低。例如，

4、在芯片生产中的批处理环节，同一批次中的工件数量越多代表该批次效率越高。然而由于工件的释放时间不同，如果某批次中的某个工件需要的等待时间过长，不等待反而有利于整个生产过程效率的提高。因此在某些生产调度环境中同时考虑学习效应和工件不同释放时间具有重要的理论和现实意义。现有的同时考虑学习效应和工件释放时间不同的生产调度问题研宄有限且都是基于位置或者正常加工时间之和的学习效应模型，本文对其进行了扩展，考虑更加符合实际的基于实际加工时间之和的学习效应模型，且优化目标为总完工时间最小化的单机调度问题。针对该问题，本文首先构建了一个非线性整数规划模型，该模型将被用来得到当工件数量规模较小时候的解。接着通过成

5、对交换技术得到加工序列的两个优先规则。在提出的优先规则基础上结合证明的两个下界，提出了分支定界算法来求解小规模工件数量的该问题。因为该问题的难特性，本文又提出了一个馄合了遗传算法相关操作，模拟退火算法思想和优先规则的混合粒子群优化算法来求解工件数量大规模的情况。为了检验提出的相关算法的性能。本文根据工件数量规模的大小设计了两个仿真实验来验证提出的分支定界算法和混合粒子群优化算法的可行性和有效性。仿真实验一的结果表明，求解小规模的该问题，分支定界算法比方法更有效率，同时该实验也一定程度上验证了混合粒子群优化算法的求解精确性。实验二中通过从解的最优，最劣和平均情况三个方面对各个算法进行比较，结果表

6、明混合粒子群优化算法在三个方面都优于其对比的三个经典的基本算法，而且这种优势随着工件规模的增加越来越明显。关键词：调度，学习效应，不同释放时间，粒子群优化算法，优先规则AbstractABSTRACTThelearningactivitieswillhaveasignificantinfluenceonproductionprocessingiftherehasaninvolvementofhumansinschedulingenvironments.Hence,itismorereasonabletotakethelearningefectsintoconsiderationonsomepr

7、oductionschedulingproblem.Ontheotherhand,thereleasetimes，Abstractalgorithmoutperformthebenchmarkalgorithmsintheliteratureandtheadvantagebecomesmoreobviouswiththenumberofjobs.KeyWords:scheduling,learni