欢迎来到天天文库
浏览记录
ID:46301683
大小:781.80 KB
页数:4页
时间:2019-11-22
《工件带简单线性恶化函数和共同交货期单机排序问题》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、第25卷第1期运筹与管理Vol.25,No.12016年2月OPERATIONSRESEARCHANDMANAGEMENTSCIENCEFeb.2016工件带简单线性恶化函数和共同交货期单机排序问题121余英,舒彤,曾春花(1.凯里学院数学科学学院,贵州凯里556011;2.湖南大学工商管理学院,湖南长沙410000)摘要:本文研究单机排序问题,其中工件加工时间具有简单线性恶化函数.同时,所有工件均具有一个给定共同交货期.目标函数为最小化提前有奖延误受罚之和.在逆一致性条件下,给出了求解该排序问题的一个伪多项式时间动态规划算法.同时借
2、助于几何舍入技巧,对求解这类排序问题给出了一个充分多项式时间的近似算法(FPTAS)。关键词:单机排序;动态规划算法;近似算法(FPTAS);几何舍入技巧中图分类号:O223文章标识码:A文章编号:1007-3221(2016)01-0154-04doi:10.12005/orms.2016.0020SchedulingSimpleLinearDeterioratingJobsOnaSingleMachinewithCommonDueDate121YUYing,SHUTong,ZENGChun-hua(1.SchoolofMathem
3、aticalScienceKaiLiUniversity,Kaili556011,China;2.SchoolofBusinessHuNanUniver-sity,ChangSha410000,China)Abstract:Asinglemachineschedulingproblemwithsimplelineardeteriorationprocessingtimeisstudied.Theduedatetimesofalljobsareassumedtobecommonsimultaneously.Ouraimistofinda
4、noptimalsequencesoastominimizethetotaloftheearlinessawardandtardinesspenalty.Apseudo-polynomialtimesolvabledynamicalgorithmisaddressedtoitunderinverseagreeableratiocondition.Wealsoproposeafullypolynomialtimesolv-ableapproximationscheme(FPTAS)tothatproblembygeometricroun
5、dingtechnique.Keywords:singlemachinescheduling;dynamicalgorithm;approximationscheme;geometricroundingtechnique[2]Cheng等在2004年,补充并完善了上述排序问[3]0引言题的综述性介绍.Mosheiov针对单机排序问题,其中工件带简单线性恶化函数展开研究,并给定出[4]工件的加工时间在传统排序问题中通常假定了六类多项式时间可解的情形.在文献中,成常数,可它在有实际背景的问题中,由于受到加Mosheiov探讨了流水车间作业
6、问题,其中工件带简工环境和位置等因素的影响,开始加工时间越往后单线性恶化函数,得出的结论与经典问题近似.[5][6]加工时间就越长。在现代排序论中,称这类工件为Wang和Xia考虑了带优势集的流水车间排序具有恶化加工时间工件。例如在钢铁制造业里,温问题,其中工件带简单线性恶化函数.Wang,Lin[7]度因素对工件加工有极为重要的影响,工件的加工和Shan研究了单机成组排序问题,其中工件带时间越往后,工件的温度将越低。如此,不管是重简单线性恶化函数,他们指出了极小化加工全程和新加温还是在低温之下继续加工,加工时间都会延极小化加权总完工
7、时间问题依然是多项式时间可[8]长.又如在瓷器生产中,将瓷器从设计图变成实物求解的.Oron探讨了单机排序问题,其中工件加粘土坯的塑形阶段,粘土等原材料肯定会随着风化工时间恶化,目标函数为极小化完工时间的绝对偏干燥越来越硬,如此塑形加工的消耗时间就会越来差的排序问题.他基于最优序的一些性质,对上述[1]越长.Alidaee和Womer在1999年对工件带有恶排序问题给定出了两个启发式算法.Wang和Wang[9]化加工时间排序问题给定出了综述性介绍.随后,中探讨了单机排序问题,其中工件具有简单线收稿日期:2014-05-13基金项目:
8、国家自然科学基金项目(71172194);贵州省科技厅与凯里学院2014年度省校合作协议项目:(黔科合LH字[2014]7232);贵州凯里学院院级课题自科类重点课题(Z1402);贵州省科技厅、黔东南州科技局、凯里学院
此文档下载收益归作者所有