几类加工时间可变的单机排序问题

《几类加工时间可变的单机排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、１０１６６单位代码：＠＿先於邸栓？５硕±学位论文几类加工时间可变的单机排序问题论文作者：隋敏学科专业：管理科学与工程专业指导教师：赵传立培养单位：数学与系统科学学院培养类别：全日制完成时间：２０１６年０５月２５日沈阳师范大学学位评定委员会学位论文独创性声明本人所呈交的学位论文是在导师的指导下取得的研巧成果。据我所知，除文中己经注明引巧的内容外，本论文不包含其他个人己经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均己在文中作了明确说明并表示了谢意。。＞。作者签名：

2、玲如日期；＞／讀辦巧学位论文使用授权声明本人授权沈阳师范大学研究生处，将本人硕壬学位论文的全部或部分内容编入有关数据库进斤检索；有权保留学位论文并向国家主管部口或其指定机构送交论文的电子版和纸质版，允许论文被查阅和借。阅；有权可采用影印、缩印或扫描等复制手段保存、汇编学位论文保密的学位论文在解密后适用本规定。＞八革。巧义作者签名：肉沁日期：几类加工时间可变的单机排序问题摘要本文考虑几类加工时间可变的单机排序问题，详述如下：首先，第一章介绍排序问题的研究背景、研究现状及研究内容。其次，第二章针对带有学习效应、加工时间可控和退

3、化工件在单机环境下进行了研究，目标为确定工件最优排序、最优加工时间和最优资源分配量，将最大完工时间、总完工时间、完工时间差和资源消耗的费用之和进行极小化。考虑了学习因子与工件有关的线性资源函数，学习效应与工件的实际加工时间依赖开始时间结合在一起的凸资源函数两种情况，通过分析最优解的一些重要性质，将这3两个问题分别转化为指派问题，给出了两个计算复杂性为On的最优算法。再次，第三章针对带有配送时间、加工时间与位置相关和多个工期在单机问题下进行研究。假设工件配送时间与工件等待时间成比例，将带有配送时间和加工时间依赖位置的单机排序问题与多个工期的单机排序问题结合成

4、新的模型。首先分析了此类问题相关重要的性质；然后将这个问题转化为一个指派问题，证明3出这个问题可以在多项式时间内可以解决的；最后，通过复杂性为On的算法,确定了最优排序、最优工期和极小化工件的提前、延误和工期的总费用。然后，第四章研究了带有分段线性递减加工时间和拒绝工件的单机排序问题。在这一模型中，工件的实际加工时间是关于开始时间的分段线性递减函数，目标是使被接受工件最大完工时间与被拒绝工件总惩罚达到最优的值，即最小值。该问题为NP难的问题。在对此问题的分析的基础上，设计了一个全多项式443近似策略。全多项式近似策略的计算复杂性为OnL(/)。最后，对本

5、文的主要结论进行归纳总结。关键词：加工时间可控，加工时间依赖位置，分段线性递减，拒绝，全多项式近似策略ISinglemachineschedulingproblemswithvaryingprocessingtimesAbstractThispaperconsiderssinglemachineschedulingproblemswithvaryingprocessingtimes,whicharedescribedbelow:Firstofall,thefirstchapterstudiesthebackground,theresearchstatusand

6、theresearchcontents.Secondly,thesecondchapterstudiessinglemachineschedulingwithlearningeffectandcontrollabledeterioratingjobs.Theobjectiveistofindtheoptimalsequenceofjobs,theoptimalprocessingtimeandtheoptimalresourceallocation,minimizingacostfunctioncontainingmakespan,totalcompletio

7、ntime,totalabsolutedifferencesincompletiontimesandtotalresourcecost.Twoversionsareconsidered.Firstisalinearresourcefunctionofthejobdependentlearningfactorofjob.Secondisaconvexresourcefunctionwhichcombinethelearningeffectandtheactualprocessingtimeofajobthatdependsitsstartingtime.Wean

8、alyzesomeimportantp