同类双目标排序问题研究

《同类双目标排序问题研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、排序问题是一类非常重要的组合最优化问题，排序是在一定的约束条件下对工件和机器按时间进行分配和安排次序。在经典的排序问题中，大多数情况都是研究仅一个目标函数的单口标排序问题。然而在生产管理实践中有些情况不仅仅只需耍考虑一个方面的性能指标，而是需耍综合考虑多个性能指标，即需耍求解多个目标函数的最优或近似最优或在某口标函数约束范围下求其它一些函数的最优或近似最优解的排序。多口标排序问题被广泛应用于计算机系统、生产管理等其它各个领域，具有广泛的生产实践背景和应用价值。本论文共分为五个章节：第一章简述排序问题的基木理论。第二章介绍本文主要研究的两类多目标排序问题的研究成果和发展现状。第三章研究

2、以工件总误工数为第一目标，以最小加权总提前完工时间为第二目标的双目标函数排序问题。对该排序问题，在文献［1］的基础上提出分支定界算法，并给出几种特殊情况卜•的多项式算法；进一步，将单机排序中的所得结论推广到m台平行机的排序屮，得到该排序问题在平行机屮的相应算法与相关结论。第四章研究以最大延误不超过某个特定值为第一目标，以加权总完工时间为第二目标的约束性双目标函数排序问题。在单机排序中，找到该问题最优解并证明其最优性；在平行机排序中，研究了两台平行机及设定权重恒为一的条件厂找出其相应的算法，最后把该问题推广到m台平行机上，找出其优势条件。第五章是对本论文内容的总结，并捉岀了对未来的工作

3、设想和努力的方向。关键词：多口标排序；分支定界算法；优势条件;启发式算法AbstractSchedulingproblemisonekindofcombinatorialoptimizationproblem.Sortingiscarriesontheassignmentandthearrangementorderundercertainconstraintconditiontotheiobandthemachineaccordingtothetime.ltusuallytakesonlyoneobjectivefunctionintoconsiderationintheclassi

4、cscheduling.Howeverintheactualproductionschedulingitnotonlyneedstoconsideranaspectobject,butneedstotakemanyobjectsintoconsideration,namelyneedstosolvemanyobjectivefunctionmostsuperioreitherapproximatemostsuperiororasksothersomefunctionsundersomeobjectivefunctionrestraintscopemostsuperiororappro

5、ximateoptimalsolutionsorting.Dual-objectivesschdulingiswidelyusedincomputersystem,productionmanagementandsoon.Inthisarticletherearefivechapters:Inthefirstchapter,elementarytheoryofsortingquestionissummarized・Inthesecondchapter,weintroducetheresearchresults,thedevelopmentpresentsituationandmainr

6、esearchofsinglemachainemulti-objectivesandtheparallelmachineschedulingquestion.Inthethirdchapter,thefirstquestionreserchedisthedoubleobjectivefunctionthatbasedonthearticle[1]•Ittakesthenumberofdelaysworkasthefirstgoal,smallestweightingaheadofcompletiontimeassecondgoal.Itgivesanewbranchdelimitat

7、ionalgorithm,andgivesthemultinomialalgorithmsinseveralkindofpeculiarcircumstances;Furthermore,thisarticlepromotesthesinglemachineconclusiontoparallelmachinescheduling,obtainsalgorithmofthisquestionintheparallelmachinesortingandthe