带有学习与恶化效应的机器受限的排序问题

《带有学习与恶化效应的机器受限的排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、编号：全日制研究生√类教育硕士别同等学力硕士学位论文题目：带有学习与恶化效应的机器受限的排序问题培养单位：数学与系统科学学院专业名称：管理科学与工程指导教师：赵玉芳副教授研究生：崔苗苗完成时间：2012年5月22日沈阳师范大学研究生处制全日制研究生√类教育硕士别同等学力硕士学位论文题目：带有学习与恶化效应的机器受限的排序问题论文编号：专业名称：管理科学与工程培养单位：数学与系统科学学院沈阳师范大学研究生处制带有学习与恶化效应的机器受限的排序问题摘要在某些实际生产过程中，工件加工时间的变化既受生产设备长时间使用，导致恶化现象的影响，也受生产设备或工人加工效率提高的影响。因此，在这种模型中，工件的

2、实际加工时间不仅与它的所排位置有关，而且还与工件的开始加工时间有关。此外，由于机器发生故障或进行维护与保养等原因，导致其在某一时间段内无法加工工件。我们把受生产因素等影响，排在后面加工的工件，其加工时间缩短的现象称之为学习效应；把机器设备等由于长时间使用导致生产能力下降，排在后面加工的工件，其加工时间增加的现象称之为恶化效应；把机器在工作过程中出现定期维修或保养等情况，从而导致机器在某段时间内不能加工工件的现象称之为机器具有可用性限制。本文将这三方面结合在一起进行了研究，具体内容概括如下：1、对于单机问题，即考虑一台机器在任意时间段不可用的情况，本文主要讨论了以下两个问题：(1)当工件的加工时

3、间受学习与恶化效应影响时，极小化总完工时间的排序问题；(2)当工件的加工时间受学习与恶化效应影响、且工件的基本加工时间与权值逆序时，极小化加权总完工时间的排序问题。对上面的NP-难问题，分别分析了最优解性质，给出了此问题的拟多项式时间的动态规划算法及相应算法的计算复杂性，并用数值例子说明了算法的有效性。2、对于平行机问题，即考虑其中一台（如第一台）机器在任意时间段不可用时的情况，本文针对以上两个问题分别进行了讨论，分析了问题的最优解性质，给出了拟多项式时间的动态规划算法及算法的计算复杂性。3、对于带有指数学习效应和机器可用性限制的单机和两台机器的平行机排序问题。当目标函数是总完工时间时，对于机

4、器在任意时间段维修的情况，分别给出了动态规划算法，分析了算法复杂性，并给出相应数值例子表明算法的有效性。对于机器在零时刻进行维修的特殊情况，通过将其转化为指派问题，给出了多项式最优算法。关键词：学习效应，恶化效应，机器可用性限制，算法复杂性，动态规划SchedulingproblemswithlearninganddeteriorationeffectandavailabilityconstrainAbstractInsomerealproductionsituations,theprocessingtimeofajobchangesduetoeitherjobdeteriorationove

5、rtimeormachine/worker`slearningthroughexperiences.Inthismodel,theprocessingtimesofjobsarerelatedwiththeirpositionsandstartingtimesinasequence;Moreover,themachinecouldbeunavailableforaspecifiedperiodbyperiodicmachinebreakdownormaintenanceactivity.Asaresult,theprocessingtimeofagivenjobisshorterifitiss

6、cheduledlaterintheproductionsequence,thephenomenonisknownaslearningeffectintheliterature.Theprocessingtimeofagivenjobislongerifitisscheduledlaterintheproductionsequence,thephenomenonisknownasdeterioratingeffectintheliterature.Machinemaybecomeunavailableduetoamachinebreakdownorpreventivemaintenancedu

7、ringtheschedulingperiod,thephenomenonisknownasavailabilityconstraintintheliterature.Inthispaper,weconsiderthreeaspectsofabove,thespecificcontentasfollows:1、Forthemachineunavailabilityinthecommoncaseat