具有截断学习效应和工件带准备时间的单机排序问题

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

1、第２３卷第６期运筹与管理Ｖｏｌ．２３，Ｎｏ．６２０１４年１２月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＤｅｃ．２０１４具有截断学习效应和工件带准备时间的单机排序问题１２２，３白静，刘璐，王吉波（１．中山火炬职业技术学院公共课教学部，广东中山５２８４３６；２．沈阳航空航天大学经济与管理学院，辽宁沈阳１１０１３６；３．沈阳航空航天大学理学院，辽宁沈阳１１０１３６）摘要：研究工件加工时间具有截断学习效应且带有准备时间的单机排序问题。截断学习效应指的是工件的加工时间是它所排位置和

2、一个控制参数的函数，其中，“截断”是一个控制参数。由于在现实生活中，与工件的排列位置有关的“学习”不可能无止境的进行下去，所以给定了一个参数来进行控制，使得工件的学习效应随着排列位置的靠后而逐渐趋于稳定。目标函数为最小化总完工时间，这个问题是ＮＰ-难的，进而结合几个优势性质和下界给出了分支定界算法来求此问题的最优解。关键词：排序；单机；截断学习效应；准备时间；分支定界算法中图分类号：Ｏ２２３；Ｃ９３４文章标识码：Ａ文章编号：１００７-３２２１（２０１４）０６-０１５２-０５Single-machineSch

3、edulingJobswithTruncatedLearningEffectandReleaseTimes１２２，３ＢＡＩＪｉｎｇ，ＬＩＵＬｕ，ＷＡＮＧＪｉ-ｂｏ（１．DepartmentofPublicCourse，ZhongshanTorchPolytechnic，Zhongshan５２８４３６，China；２．SchoolofEconomicsandManagement，ShenyangAerospaceUniversity，Shenyang１１０１３６，China；３．SchoolofScience

4、，ShenyangAerospaceUniversity，Shenyang１１０１３６，China）Abstract：Ｔｈｉｓｐａｐｅｒｉｎｖｅｓｔｉｇａｔｅｓａｓｉｎｇｌｅ-ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｔｒｕｎｃａｔｅｄｌｅａｒｎｉｎｇｅｆｆｅｃｔａｎｄｒｅｌｅａｓｅｔｉｍｅｓ．Ｔｈｅｔｒｕｎｃａｔｅｄｌｅａｒｎｉｎｇｅｆｆｅｃｔｍｅａｎｓｔｈａｔｔｈｅａｃｔｕａｌｐｒｏｃｅｓｓｉｎｇｔｉｍｅｏｆａｊｏｂｉｓａｆｕｎｃｔｉｏｎｏｆｉｔｓｐｏｓｉｔｉｏｎａｎｄａｃｏｎｔｒｏｌｐａ

5、ｒａｍｅｔｅｒ，ａｎｄｔｈｅｆａｃｔｏｒ“ｔｒｕｎｃａｔｅｄ”，ｗｈｉｃｈｍｅａｎｓａｃｏｎｔｒｏｌｐａｒａｍｅｔｅｒ．Ｂｅｃａｕｓｅｏｆｔｈｅ“ｌｅａｒｎｉｎｇ”ｒｅｌａｔｅｄｔｏｔｈｅｐｏｓｉｔｉｏｎｏｆｊｏｂｓｔｏｂｅｐｒｏｃｅｓｓｅｄｃａｎｎｏｔｂｅｅｎｄｌｅｓｓ，ａｐａｒａｍｅｔｅｒｗｉｌｌｂｅｇｉｖｅｎｔｏｍａｋｅｔｈｅｌｅａｒｎｉｎｇｅｆｆｅｃｔｔｅｎｄｔｏｂｅｓｔａｂｌｅａｓｔｈｅｊｏｂｓ’ｐｏｓｉｔｉｏｎｉｎｃｒｅａｓｅｓ．Ｔｈｅｏｂｊｅｃｔｉｖｅｆｕｎｃｔｉｏｎｉｓｔｏｍｉｎｉｍｉｚｅｔ

6、ｈｅｔｏｔａｌｃｏｍｐｌｅｔｉｏｎｔｉｍｅ，ａｎｄｔｈｉｓｐｒｏｂｌｅｍｉｓＮＰ-ｈａｒｄ．Ｔｈｅｒｅｆｏｒｅ，ａｂｒａｎｃｈ-ａｎｄ-ｂｏｕｎｄａｌｇｏｒｉｔｈｍｃｏｍｂｉｎｉｎｇｗｉｔｈｓｅｖｅｒａｌｄｏｍｉｎａｎｃｅｐｒｏｐｅｒｔｉｅｓａｎｄｌｏｗｅｒｂｏｕｎｄｓｉｓｐｒｏｐｏｓｅｄｔｏｄｅｒｉｖｅｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｆｏｒｔｈｅｐｒｏｂｌｅｍ．Keywords：ｓｃｈｅｄｕｌｉｎｇ；ｓｉｎｇｌｅ-ｍａｃｈｉｎｅ；ｔｒｕｎｃａｔｅｄｌｅａｒｎｉｎｇｅｆｆｅｃｔ；ｒｅｌｅａｓｅｔｉｍｅ；

7、ｂｒａｎｃｈ-ａｎｄ-ｂｏｕｎｄａｌｇｏｒｉｔｈｍ０引言［１－１０］［１］加工时间带有学习效应的排序问题受到了广泛的关注。Ｂｉｓｋｕｐ首次提出具有学习效应的排序a问题，即工件Jj的实际加工时间为pjh＝pjh，其中pj是工件Jj的正常加工时间，h代表Jj的加工位置，pjh代表工件Jj位于第h个位置上的实际加工时间。他证明了总完工时间问题和一个多目标问题能够多项［２］［１］式时间解决。王吉波和夏尊铨把Ｂｉｓｋｕｐ的成果推广到流水作业排序问题，他们对最大完工时间问题［３］和总完工时间问题给出了启发式算法，并分析

8、了最坏情况界。王吉波等研究了在学习效应下的两个单机排序问题，对加权总完工时间极小问题，他们把加权加工时间优先（ＷＳＰＴ）规则作为启发式算法，对最收稿日期：２０１３-０３-２０基金项目：国家自然科学基金项目（１１００１１８１）；辽宁省高等学校优秀人才支持计划资助项目（ＬＪＱ２０１１０１４）作者简介：白静（１９７５-），女，硕士研究生，副教授，主要从事运筹学与控制论的研究；刘璐（１９８９-），女，硕士研究生，主要从事