带无向环优先级的单机总加权完成时间调度问题

摘要：

单机调度是生产调度领域的一个经典问题,研究了工件间有加工优先级要求的单机总加权完成时间调度问题,考虑了若将工件优先级关系构成的优先级图视为无向图,包含有环的情况.针对该问题,设计了结合双向动态规划的拉格朗日松弛算法进行求解,使得可以求解一个工件可能有多个紧前或紧后工件的情况.大量实验测试结果表明,该算法能够在较短时间内得到令人满意的近优解.

关键词：单机总加权完成时间问题、无向环优先级、拉格朗日松弛、双向动态规划

所属期刊栏目：22

分类号：TB49(工业通用技术与设备)

资助基金：国家自然科学基金资助项目71001090,71001091;2009年河南省教育厅自然科学研究计划项目2009A120002

在线出版日期：2013-07-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：415-419