工件带简单线性恶化函数和共同交货期单机排序问题

《工件带简单线性恶化函数和共同交货期单机排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２５卷第１期运筹与管理Ｖｏｌ．２５，Ｎｏ．１２０１６年２月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＦｅｂ．２０１６工件带简单线性恶化函数和共同交货期单机排序问题１２１余英，舒彤，曾春花（１．凯里学院数学科学学院，贵州凯里５５６０１１；２．湖南大学工商管理学院，湖南长沙４１００００）摘要：本文研究单机排序问题，其中工件加工时间具有简单线性恶化函数．同时，所有工件均具有一个给定共同交货期．目标函数为最小化提前有奖延误受罚之和．在逆一致性条件下，给出了求解该排序问题的一个伪多项式时间动态规划算法．同时借

2、助于几何舍入技巧，对求解这类排序问题给出了一个充分多项式时间的近似算法（ＦＰＴＡＳ）。关键词：单机排序；动态规划算法；近似算法（ＦＰＴＡＳ）；几何舍入技巧中图分类号：Ｏ２２３文章标识码：Ａ文章编号：１００７-３２２１（２０１６）０１-０１５４-０４doi：１０．１２００５／ｏｒｍｓ．２０１６．００２０SchedulingSimpleLinearDeterioratingJobsOnaSingleMachinewithCommonDueDate１２１ＹＵＹｉｎｇ，ＳＨＵＴｏｎｇ，ＺＥＮＧＣｈｕｎ-ｈｕａ（１．SchoolofMathem

3、aticalScienceKaiLiUniversity，Kaili５５６０１１，China；２．SchoolofBusinessHuNanUniver-sity，ChangSha４１００００，China）Abstract：Ａｓｉｎｇｌｅｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｓｉｍｐｌｅｌｉｎｅａｒｄｅｔｅｒｉｏｒａｔｉｏｎｐｒｏｃｅｓｓｉｎｇｔｉｍｅｉｓｓｔｕｄｉｅｄ．Ｔｈｅｄｕｅｄａｔｅｔｉｍｅｓｏｆａｌｌｊｏｂｓａｒｅａｓｓｕｍｅｄｔｏｂｅｃｏｍｍｏｎｓｉｍｕｌｔａｎｅｏｕｓｌｙ．Ｏｕｒａｉｍｉｓｔｏｆｉｎｄａ

4、ｎｏｐｔｉｍａｌｓｅｑｕｅｎｃｅｓｏａｓｔｏｍｉｎｉｍｉｚｅｔｈｅｔｏｔａｌｏｆｔｈｅｅａｒｌｉｎｅｓｓａｗａｒｄａｎｄｔａｒｄｉｎｅｓｓｐｅｎａｌｔｙ．Ａｐｓｅｕｄｏ-ｐｏｌｙｎｏｍｉａｌｔｉｍｅｓｏｌｖａｂｌｅｄｙｎａｍｉｃａｌｇｏｒｉｔｈｍｉｓａｄｄｒｅｓｓｅｄｔｏｉｔｕｎｄｅｒｉｎｖｅｒｓｅａｇｒｅｅａｂｌｅｒａｔｉｏｃｏｎｄｉｔｉｏｎ．Ｗｅａｌｓｏｐｒｏｐｏｓｅａｆｕｌｌｙｐｏｌｙｎｏｍｉａｌｔｉｍｅｓｏｌｖ-ａｂｌｅａｐｐｒｏｘｉｍａｔｉｏｎｓｃｈｅｍｅ（ＦＰＴＡＳ）ｔｏｔｈａｔｐｒｏｂｌｅｍｂｙｇｅｏｍｅｔｒｉｃｒｏｕｎ

5、ｄｉｎｇｔｅｃｈｎｉｑｕｅ．Keywords：ｓｉｎｇｌｅｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇ；ｄｙｎａｍｉｃａｌｇｏｒｉｔｈｍ；ａｐｐｒｏｘｉｍａｔｉｏｎｓｃｈｅｍｅ；ｇｅｏｍｅｔｒｉｃｒｏｕｎｄｉｎｇｔｅｃｈｎｉｑｕｅ［２］Ｃｈｅｎｇ等在２００４年，补充并完善了上述排序问［３］０引言题的综述性介绍．Ｍｏｓｈｅｉｏｖ针对单机排序问题，其中工件带简单线性恶化函数展开研究，并给定出［４］工件的加工时间在传统排序问题中通常假定了六类多项式时间可解的情形．在文献中，成常数，可它在有实际背景的问题中，由于受到加Ｍｏｓｈｅｉｏｖ探讨了流水车间作业

6、问题，其中工件带简工环境和位置等因素的影响，开始加工时间越往后单线性恶化函数，得出的结论与经典问题近似．［５］［６］加工时间就越长。在现代排序论中，称这类工件为Ｗａｎｇ和Ｘｉａ考虑了带优势集的流水车间排序具有恶化加工时间工件。例如在钢铁制造业里，温问题，其中工件带简单线性恶化函数．Ｗａｎｇ，Ｌｉｎ［７］度因素对工件加工有极为重要的影响，工件的加工和Ｓｈａｎ研究了单机成组排序问题，其中工件带时间越往后，工件的温度将越低。如此，不管是重简单线性恶化函数，他们指出了极小化加工全程和新加温还是在低温之下继续加工，加工时间都会延极小化加权总完工

7、时间问题依然是多项式时间可［８］长．又如在瓷器生产中，将瓷器从设计图变成实物求解的．Ｏｒｏｎ探讨了单机排序问题，其中工件加粘土坯的塑形阶段，粘土等原材料肯定会随着风化工时间恶化，目标函数为极小化完工时间的绝对偏干燥越来越硬，如此塑形加工的消耗时间就会越来差的排序问题．他基于最优序的一些性质，对上述［１］越长．Ａｌｉｄａｅｅ和Ｗｏｍｅｒ在１９９９年对工件带有恶排序问题给定出了两个启发式算法．Ｗａｎｇ和Ｗａｎｇ［９］化加工时间排序问题给定出了综述性介绍．随后，中探讨了单机排序问题，其中工件具有简单线收稿日期：２０１４-０５-１３基金项目：

8、国家自然科学基金项目（７１１７２１９４）；贵州省科技厅与凯里学院２０１４年度省校合作协议项目：（黔科合ＬＨ字［２０１４］７２３２）；贵州凯里学院院级课题自科类重点课题（Ｚ１４０２）；贵州省科技厅、黔东南州科技局、凯里学院