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

• 作者: 于蓉 赵梗明
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 复合并行排序 分支定界算法 生产调度 动态规划 启发式算法
• 年，卷（期）: 2011,（4）
• 所属期刊栏目: 软件与算法
• 页码范围: 1311-1314
• 分类号: TP301.6
• 字数: 4552字
• 语种: 中文

摘要

为有效解决复合并行机排序的极小化最大完成时间问题,提出了分支定界算法和改进的启发式动态规划算法.利用分支定界算法的3个工具:分支模型、边界和优先规则,构建出分支搜索树.按优先规则进行定界搜索,从而减小了问题求解规模.将原始作业转换为虚拟作业,根据Johnson法则,求解出原问题的最优排序.改进的动态规划算法复杂度分析和计算实验表明,这两个算法可靠性高并且可以解决实际问题.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵梗明	上海师范大学信息与机电工程学院	17	37	3.0	6.0
2	于蓉	上海师范大学信息与机电工程学院	1	1	1.0	1.0