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

发布时间：2017-12-30 23:25

  本文关键词：带无向环优先级的单机总加权完成时间调度问题　出处：《系统管理学报》2013年03期 　论文类型：期刊论文

  更多相关文章： 单机总加权完成时间问题 无向环优先级 拉格朗日松弛 双向动态规划

【摘要】：单机调度是生产调度领域的一个经典问题,研究了工件间有加工优先级要求的单机总加权完成时间调度问题,考虑了若将工件优先级关系构成的优先级图视为无向图,包含有环的情况。针对该问题,设计了结合双向动态规划的拉格朗日松弛算法进行求解,使得可以求解一个工件可能有多个紧前或紧后工件的情况。大量实验测试结果表明,该算法能够在较短时间内得到令人满意的近优解。
[Abstract]:Single machine scheduling is a classical problem in production scheduling field, studied the workpiece between the processing priority requirements of the single machine total weighted completion time scheduling problem, consider if the relationship will constitute the priority priority graph as undirected graph contains ring. Aiming at this problem, designed with bidirectional Lagrange relaxation algorithm dynamic programming to solve the problem which can solve a workpiece may have multiple precedence or tight workpiece. Experimental test results show that the algorithm can in a relatively short period of time to get satisfactory near optimal solution.

【作者单位】： 郑州大学管理工程系;中国金域黄金物资总公司;
【基金】：国家自然科学基金资助项目(71001090,71001091) 2009年河南省教育厅自然科学研究计划项目(2009A120002)
【分类号】：C931.6
【正文快照】： 单机调度不仅是调度问题中最简单的一类问题,也是调度问题中最重要的一类问题。理论上通常把单机调度作为复杂调度系统的一个子系统,实际生产中比较复杂的调度问题也可以分解为多个单机问题来解决,研究单机调度问题可以帮助理解和解决更为复杂的多机调度问题。对单机的合理调，

本文编号：1357014