资源描述：
《两类加工时间可变的现代排序问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、两类加工时间可变的现代排序问题摘要排序论是当前发展非常快速，研究十分活跃，成果相当丰硕的学科之一。经典排序问题中工件的加工时间是一个固定不变的常数。但是在某些实际生产生活中，工件的实际加工时间可能是某些因素的具体函数。本文讨论两类工件加工时间可变的现代排序问题。首先在第一章介绍了有关排序问题的发展和得到的主要结果。本文第二章对具有学习效应的平行机排序问题，讨论了目标函数分别是极小化提前和延误的加权和以及极小化提前和误工工件数的加权和两类问题，并且分别给出了两类问题的多项式算法。第三章考虑在单机环境下，具有老化效应、维修活动和共同工期窗
2、口安排的排序问题。由于出现老化效应，所以可以通过维修活动使机器的加工效率得到恢复，目标函数是极小化流时间、提前、延误和工期窗口大小的加权和。对工期窗口的开始时间是已给定的常量这一问题，给出了一个多项式算法，并且讨论了问题的特殊情况。第四章探讨工件加工时间与其开工时间有关的排序问题，首先研究了退化条件下具有维修活动的单机排序问题，对目标函数是确定安排维修活动的次数和位置，使排序的最大完工时间最小这一问题，给出了一个多项式时间最优算法，推广了已有文献中的结论；其次研究了具有退化工件和和共同工期窗口安排的单机和两台机器流水作业排序问题，目标
3、是极小化所有工件最大费用的最小值，给出了两类问题的多项式算法且详细讨论了单机问题中的几种情况。最后，对全文内容进行了总结，并提出将来工作努力的方向。关键词：排序，学习效应，老化效应，线性加工时间TwomodernschedulingproblemswithvaryingprocessingtimesAbstractSchedulingisanimportantproblemincombinatorialoptimization.Theprocessingtimeofajobisafixedconstantintheclassicals
4、cheduling.However,intherealword,theprocessingtimeofthejobmaybedependentonitspositioninaschedule,itsstartingtimeorcharacteristics.Modernschedulingproblemwithvaryingprocessingtimesistheexpansionoftheclassicalschedulingproblemandmoreandmorecausetheresearcher'sinterest.Inth
5、epaper,westudytwomodernschedulingproblemswithvaryingprocessingtimes,thestructureisfollowing:Firstly,weintroducethebackgroundknowledgeofschedulingproblemandworksinthispaper.Inthesecondchapter,fortheparallelmachinesschedulingmodelwithlearningeffect,wediscusstwoproblemswhi
6、chobjectivefunctionsareminimizingthesumofearlinessandtardinesspenaltiesandminimizingtheweightedsumofearlinessandnumberoftardyjobs.Forthetwoproblems,wepresentapolynomialtimealgorithm,respectively.Inthethirdchapter,weconsidertheproblemofdue-windowassignmentandschedulingmo
7、delofajob-dependentagingeffectandamaintenanceactivityonasinglemachine.Inthismodel,themaintenanceactivityrestorestheprocessingefficiencyofthemachine.Theobjectiveistominimizethetotalflow-time,earliness,tardinessanddue-windowcosts.Forthedue-windowstartingtimeisagivenparame
8、ter,weprovideapolynomial-timealgorithm.Intheforthchapter,westudytheproblemoftheprocessingtimeofajobisdependent
