同时具有学习效应和退化效应的单机排序问题

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

1、第2l卷第3期2012年6月运筹与管理oPERAl"IONSRESEARCHANDMANAGEMENTSCIENCEV01．21，No．3Jun．2012同时具有学习效应和退化效应的单机排序问题刘洋，唐恒永，赵传立(沈阳师范大学敷学与系统科学学院．辽宁沈阳lZ0034)摘要：本文给出了一种同时具有一般化学习效应和退化效应的单机排序模型。在此模型中，工件的实际加工时问既与工件所在位置又与其开工时间有关，且工件在加工之后具有一个配送时间。其中学习效应是工件所在位置的函数，退化效应是工件开工时间的函数。证明了极小化最大完工时间和极小化总完

2、工时间问题是多项式可解的，在满足一定的条件下，极小化加权总完工时间和极小化最大延误问题也是多项式可勰的。推广了一些已有文献中的结论。关键词：运筹学；单机；排序；学习效应；退化效应中围分类号：0223文章标识码：A文章编号：1007-3221【2012)03—0081．06Single—machineSchedulingProblemswithGeneralEffectsofLearningandDeteriorationLIUYang。TANGHang·yong。ZHAOChuan-li(SchoolofMathematicsand

3、systemsScience，ShenyangNormalUniv．，Shenyang110034。China)Abstract：Inthispaper。weintroduceageneralsinglemachineschedulingmodelwithlearningeffectanddeterio·ratingjobssimultaneously．Inthismodel，theactualprocessingtimeofajobdependsnotonlyonitsschedulingpositionbutalsoonitss

4、tartingtime，andthereisapast-sequence-dependentdeliverytimeaftereachjobispro·cessod．Thelearningeffectis8functionoftheschedulingpositionofthejobinaschedule．Thedeteriorationisafunctionofthestartingtimeofthejohinaschedule．Weshowthatthemakesptmminimizationproblemandthetotal

5、completiontimeminimizationproblemarepolynomiaHysolvableunderthemodel．Wealsoshowthattheto—talweightedcompletiontimeminimizationproblemandthemaximumlatenessminimizationproblemcanbesolvedinpolynomialtimeundercertainconditions．Weextendtheconclusioninsomeoftheexistinglitera

6、tures．Keywords：operationalresearch；single-machine；scheduling；learningeffect；deterioratingjobs0引言从20世纪50年代起，排序问题一直受到众多学者的关注。在经典的排序问题中，工件的加工时间是一个常数，不受其它因素影响。然而在实际问题中，会因为反复加工很多同样的工件，而获得知识与经验，可能会使得实际加工时间缩短，工件所在位置越靠后，其加工时间越短，这种现象称为“学习效应“。Wright在文献[1]中首次研究了学习效应。Biskup在文献[2]中

7、把学习效应引入了排序问题中。wu和Lee在文献[3]中考虑了机器和人同时具有学习效应的情况。Wang等人在文献[4]中对最大完工时间和总完工时间两个问题给出了最优算法，并讨论了具有共同工期限制问题。Biskup在文献[5]中讨论了一牧幡日期：2011·OI-20基金项目：田家自然科学基全项目(10471096)作者简介：刺洋(1984·)女．厦士研宽生．主要研竞方由为排序理论与算法。82运筹与管理2012年第2l卷些具有学习效应的经济模型，对学习效应进行了综述性讨论。另一类具有较强实际背景的翔题是工件具有“退化效应”的模型。在这类模

8、型中，等候加工的时间对工件的实际加工时间有影响，工件的开工时间越晚，其实际加工时间越长。Gupta在文献[6]中首次提出了退化效应。Mosheiov在文献[7]中，对工件的加工时间是开工时同I的简单线性函数的单机问题进行了讨论。Pin