带不可用时间段的部分可续型单机最大完工时间调度

《带不可用时间段的部分可续型单机最大完工时间调度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第29卷第4期2009年4月系统工程理论与实践SystemsEngineering—Theory＆PracticeVbl．29．No．4Apr．，2009文章编号：1000—6788(2009)04．0128—08带不可用时间段的部分可续型单机最大完工时间调度马英-，一，杨善林，，一，储诚斌-，s(1．合肥工业大学管理学院，合肥230009；2．过程优化与智能决策教育部重点实验室，合肥230009；3．特鲁瓦工业大学工业系统优化实验室，特鲁瓦10010)摘要研究了机器带有一个不可用时间段的单机最小化最大完工时间调度问题，并假定被中断工件是部分可续的，即其已加工部分在机

2、器重新可用之后需部分进行重新加工．文中简单说明了此问题为NP一难问题，并证明了最大加工时间优先LPT规则的误差上限是o／2(其中Q为重加工系数)，进而提出了一个基于LPT规则的启发式算法．实验结果证明了此算法的高效性，此外对不同参数对此算法性能的影响也进行了分析．关键词单机调度；部分可续型；最长加工时间优先中图分类号0221；F406．2；TP301文献标志码AMinimizingm出汜spaninsemiresumablecalseofsingle—machines(血edulingwithanaVailabilityconstraintMAYin91，_，YANGShan

3、_linl，_，CHUChen争binl，3(1．SchoolofM粕agement，HefeiUniver8ityof，Ikhnology'Hefei230009，China；2．KeyLaboratoryofProcess0ptimization锄dIntelligentDecision-Making，MinistryofEducation，Hefei23009，China；3．Laboratoired’optimisationde8SysteIIl船Industriels，univer8it6deTechnologieden9yes，noyes10010noy昭cede

4、x，nance)AbstractSinglemachineschedulingwithanunaⅣailabilityintervaltominimizemak唧anisconsideredinthisp印erunderthe够8umptionthatthedi8ruptedjobhastop盯tiallyrestartaRerthemachinebecome8av面lablea舀ain．Itiseasilyshowntha七thisproblemi8NP—hard，anditisshawntha七theLonP犯stP蛉ces8ingTime(L】?T)algorithmh

5、嬲arelativewor8t—ca鹋errorboundofn／2，whereai8re-processingrate．Further】[nore，aJlex锄pleisprovidedtoshoWthatthisboundistight．ThenaLPT-ba8edheuristici8pr伊po∞d．Computation以re8ult8sllowthatthishellristicisquitee任色ctiveinfindiⅡganoptimalorne龃．optimalschedllle．E丘&t8ofdi珏．erentpar锄etersonthisheuristi

6、carea180aJlalyzedinthi8paper．Key、Ⅳords8ingle-machine8cheduUng；∞mir髑umablecase；longestproce88ingtime矗r8t1引言对企业来说，对机器的日常维护保养不仅可以提高机器精度，而且可以将可能发生的故障消灭在萌芽状态，减少停机时间，还能使设备的使用寿命得以延长，从而获得最佳的使用效率，为企业赢得更大的经济效益．因此目前企业已经越来越认识到维护保养这种主动维修的重要性，主张摒弃传统的被动维修，提倡主动维修，收稿日期：2007．08-27资助项目：国家自然科学基金(70631003)；国家高技

7、术研究发展计划863重点项目(2008AA042901)作者简介：马英(1979-)，女，安徽淮北人，合肥工业大学博士研究生，主要研究方向为生产调度，Tel：0551-2901489．8403，Email：maying_chb@yahoo．com．cn；杨善林(1948-)，男，安徽怀宁人，合肥工业大学教授，博上生导师；储诚斌(1965-)，男，原籍安徽潜山，现籍法国特鲁瓦，法国特鲁瓦工业大学教授，博士生导师；合肥工业大学长江学者，教授，博士生导师．万方数据第4期马英，等：带不可用时间段的部分可续型单机