复合并行机排序问题的启发式算法研究  

Research of heuristic algorithms for scheduling multi-processor tasks

作　　者：于蓉[1] 赵梗明[1] 

机构地区：[1]上海师范大学信息与机电工程学院,上海200234

出　　处：《计算机工程与设计》2011年第4期1311-1314,共4页Computer Engineering and Design

摘　　要：为有效解决复合并行机排序的极小化最大完成时间问题,提出了分支定界算法和改进的启发式动态规划算法。利用分支定界算法的3个工具:分支模型、边界和优先规则,构建出分支搜索树。按优先规则进行定界搜索,从而减小了问题求解规模。将原始作业转换为虚拟作业,根据Johnson法则,求解出原问题的最优排序。改进的动态规划算法复杂度分析和计算实验表明,这两个算法可靠性高并且可以解决实际问题。To minimize the Maximum Completion Time of one job scheduling model on complex parallel machines,a BB algorithm and a heuristic dynamic programming algorithm are proposed.A BB searching tree is constructed with three tools： BB model,boundary and priority rules.Priority rules are used to bound search,so as to limit the potential solutions’ boundary.Initial jobs are converted to virtual ones which meet Johnson Rule’s application conditions.By this way,using Johnson Rules,a solution of initial problem is achieved.These two algorithms are compared by complexity analysis and computational experiments.The result shows that both algorithms are reliable,and can be used in practical problems.

关 键 词：复合并行排序 分支定界算法 生产调度 动态规划 启发式算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]