具有学习效应和安装时间的单机排序问题

《具有学习效应和安装时间的单机排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、具有学习效应和安装时间的单机排序问题摘要排序问题是一类重要的组合优化问题，现在已经成为运筹学研究的一个非常活跃的分支。在经典的排序问题中工件的加工时间是固定不变的，然而在某些实际问题中工件的加工时间不仅与已完成工件的加工时间有关，而且还与工件的加工位置有关。此外，工件有时候具有安装时间，由此产生的工件具有安装时间的问题。本文主要讨论了工件具有学习效应和安装时间的单机排序问题。首先介绍了排序问题的定义、分类及表示方法，并且分别对具有学习效应和安装时间的排序问题进行了介绍。在第二章主要讨论了具有学习效应和线性安装

2、时间的单机排序问题。工件的加工时间不仅与已完成工件的加工时间有关，还与工件的加工位置有关。安装时间是依赖于已加工完的工件的实际加工时间的简单函数，即p-s-d形式。证明了极小化最大完工时间，极小化完工时间总和，极小化完工时间k次幂的和是多项式可解的，另外还证明了满足一定条件下的极小化加权完工时间和，极小化最大延误和极小化延迟时间和问题是多项式可解的。在第三章中讨论了工件具有学习效应和非线性安装时间的单机排序问题。工件具有学习效应并且安装时间为非线性的函数。同样的证明了极小化最大完工时间，极小化完工时间总和，极

3、小化完工时间k次幂的和是多项式可解的，另外还证明了满足一定条件下的极小化加权完工时间和，极小化最大延误和极小化延迟时间和问题是多项式可解的。本文最后对论文的内容作了总结，并提出了未来工作的努力方向。关键词：排序；单机；学习效应；线性安装时间；非线性安装时间ISingle-machineschedulingproblemswithlearningeffectsandsetuptimesAbstractSchedulingproblemisanimportantcombinationoptimizationpro

4、blem.IthasalreadybecameaveryactivebranchoftheOperationresearch.Theclassicalschedulingproblemisusuallysupposedthatthejobprocessingtimeisaconstant.Butinsomeactualproduction,theprocessingtimeofajobdependsnotonlyontheprocessingtimesofthejobalreadyprocessedbutal

5、soonitsschedulingposition.Inaddition,theprocessedjobsalsohavesetuptimes.Thustheschedulingproblemwithsetuptimesisproduced.Thispapermainlyconsidersthesingle-machineschedulingproblemswithtime-dependentlearningeffectandsetuptimesconsiderations.Inthispaper,weint

6、roducethedefinitionandexpressionandclassificationofscheduling,aswellastheresearchoftheschedulingproblemwithlearningeffectandtheschedulingproblemwithsetuptimes.Inthechapter2,wemainlydiscussthesingle-machineschedulingproblemswithtime-dependentlearningeffectan

7、dlinearsetuptimesconsiderations.Theactualprocessingtimeofajobdependsnotonlyontheprocessingtimesofthejobalreadyprocessedbutalsoonitsschedulingposition.Thesetuptimesareproportionaltothelengthofthealreadyprocessedjobs,i.e.,thesetuptimesarepast-sequence-depende

8、nt(p-s-d).Weshowthatthemakespanminimizationproblem,thetotalcompletiontimeminimizationproblemandthesumofkthpowersofcompletionminimizationproblemcanbesolvedinpolynomialtime.Inaddition,theproblemstominimi