工件优先级图为非连接图且含环的单机总加权拖期调度问题

《工件优先级图为非连接图且含环的单机总加权拖期调度问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２３卷第２期运筹与管理Ｖｏｌ．２３，Ｎｏ．２２０１４年４月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＡｐｒ．２０１４工件优先级图为非连接图且含环的单机总加权拖期调度问题轩华，　刘静，　李冰（郑州大学管理工程学院，河南郑州４５０００１）摘要：为满足实际生产环境对工件加工顺序和工件到达时间的要求，提出了具有新特征的单机总加权拖期调度问题，其特点体现在：工件有动态到达时间，且由工件优先级关系构成的优先级图为非连接图且存在环的情况，对该问题建立数学规划模型，在扩展Ｔａｎｇ和Ｘｕａｎ等的基础

2、上，提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中，提出双向动态规划算法求解拉格朗日松弛问题，使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况，采用次梯度算法更新拉格朗日乘子，基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示，所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解，为更复杂的调度问题的求解提供了思路。关键词：系统工程；单机总加权拖期调度；拉格朗日松弛算法；非连接优先级图；双向动态规划中图分类号：ＴＢ３９９　　　文章标识码：Ａ文章编号：１０

3、０７-３２２１（２０１４）０２-０２４４-０６SingleMachineTotalWeightedTardinessSchedulingwithUnconnectedPrecedenceGraphandLoopConstraintsＸＵＡＮＨｕａ，ＬＩＵＪｉｎｇ，ＬＩＢｉｎｇ（SchoolofManagementEngineering，ZhengzhouUniversity，Zhengzhou４５０００１，China）Abstract：Ｉｎｏｒｄｅｒｔｏｓａｔｉｓｆｙｔｈｅｄｅｍａｎｄｓｆｏｒｊｏｂｐｒｏｃｅｓｓｉｎ

4、ｇｏｒｄｅｒａｎｄａｒｒｉｖａｌｔｉｍｅｉｎｐｒａｃｔｉｃａｌｐｒｏｄｕｃｔｉｏｎｅｎｖｉｒｏｎ-ｍｅｎｔ，ｔｈｉｓｐａｐｅｒｓｔｕｄｉｅｓａｓｉｎｇｌｅｍａｃｈｉｎｅｔｏｔａｌｗｅｉｇｈｔｅｄｔａｒｄｉｎｅｓｓｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｓｏｍｅｎｏｖｅｌｆｅａｔｕｒｅｓ．Ｔｈｅｓｅｆｅａｔｕｒｅｓａｒｅｔｈａｔｅａｃｈｊｏｂｈａｓａｒｅｌｅａｓｅｄａｔｅａｎｄｔｈｅｐｒｅｃｅｄｅｎｃｅｇｒａｐｈｆｏｒｍｅｄｂｙｊｏｂｐｒｅｃｅｄｅｎｃｅｒｅｌａｔｉｏｎｓｉｓｕｎｃｏｎｎｅｃｔｅｄａｎｄｃｏｎｓｉｓｔ

5、ｓｏｆｕｎｄｉｒｅｃｔｅｄｌｏｏｐ．Ａｍａｔｈｅｍａｔｉｃａｌｐｒｏｇｒａｍｍｉｎｇｍｏｄｅｌｉｓｔｈｅｎｆｏｒｍｕｌａｔｅｄ．Ｆｕｒｔｈｅｒ，ＬａｇｒａｎｇｉａｎｒｅｌａｘａｔｉｏｎｃｏｍｂｉｎｅｄｗｉｔｈｈｙｂｒｉｄｂａｃｋｗａｒｄａｎｄｆｏｒｗａｒｄｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｉｓｐｒｏｐｏｓｅｄｔｏｓｏｌｖｅｔｈｉｓｐｒｏｂｌｅｍａｓａｎｅｘｔｅｎｓｉｏｎｏｆＴａｎｇａｎｄＸｕａｎｅｔａｌ．．Ｉｎｔｈｉｓａｌｇｏｒｉｔｈｍ，ｈｙｂｒｉｄｂａｃｋｗａｒｄａｎｄｆｏｒｗａｒｄｄｙｎａｍｉｃｐｒｏ-ｇｒａｍ

6、ｍｉｎｇｉｓｄｅｓｉｇｎｅｄｔｏｄｅａｌｗｉｔｈｔｈｅｃａｓｅｔｈａｔａｊｏｂｍａｙｈａｖｅｍｕｌｔｉｐｌｅｐｒｅｄｅｃｅｓｓｏｒｓｏｒｓｕｃｃｅｓｓｏｒｓ．Ａｓｕｂｇｒａｄｉ-ｅｎｔａｌｇｏｒｉｔｈｍｉｓｔｈｅｎｕｓｅｄｔｏｕｐｄａｔｅＬａｇｒａｎｇｉａｎｍｕｌｔｉｐｌｉｅｒｓａｎｄａｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄｔｏｃｏｎｓｔｒｕｃｔａｆｅａｓｉｂｌｅｓｃｈｅｄｕｌｅｂａｓｅｄｏｎｔｈｅｓｏｌｕｔｉｏｎｓｏｆｔｈｅＬａｇｒａｎｇｉａｎｒｅｌａｘａｔｉｏｎｐｒｏｂｌｅｍ．Ｅｘｐｅｒｉｍｅ

7、ｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｉｓａｌｇｏｒｉｔｈｍｃａｎｏｂｔａｉｎｓａｔｉｓｆａｃｔｏｒｙｓｏｌｕｔｉｏｎｓｗｉｔｈｉｎａｓｈｏｒｔｅｒｃｏｍｐｕｔａｔｉｏｎｔｉｍｅａｎｄｉｔｃａｎｐｒｏｖｉｄｅａｎｉｄｅａｔｏｓｏｌｖｅｍｏｒｅｃｏｍｐｌｉｃａｔｅｄｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ．Keywords：ｓｙｓｔｅｍｓｅｎｇｉｎｅｅｒｉｎｇ；ｓｉｎｇｌｅｍａｃｈｉｎｅｔｏｔａｌｗｅｉｇｈｔｅｄｔａｒｄｉｎｅｓｓｓｃｈｅｄｕｌｉｎｇ；ｌａｇｒａｎｇｉａｎｒｅｌａｘａｔｉｏｎ；ｕｎｃｏｎｎｅｃｔｅｄｐｒ

8、ｅｃｅｄｅｎｃｅｇｒａｐｈ；ｈｙｂｒｉｄｂａｃｋｗａｒｄａｎｄｆｏｒｗａｒｄｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇ０　引言在生产调度领域，单机调度问题一直是专家和学者研究的热点。作为单机调度问题中的一类经典问收稿日期：２０１２-０９-０３基金项目：国家自然科学基金项目（７１００１０９０，７１００１０９１）；２０１３年河南省教育厅科学技术研究重点项