两台流水机器协调分解调度问题

• 作者: 关静 唐立新 宋国骄
• 来源期刊: 控制与决策
• 学科: 工学
• 关键词: 流水机 调度 分解 算法复杂性 动态规划 界分析
• 年，卷（期）: 2009,（1）
• 所属期刊栏目: 论文与报告
• 页码范围: 55-60,65
• 页数: 7页
• 分类号: TP29
• 语种: 中文
• DOI: 10.3321/j.issn:1001-0920.2009.01.011

摘要

研究钢管加工流程中一类新型两台机器流水车间调度问题,工件在第一台机器上加工后被分解成多个子工件.对于最小化最大完成时间的情况,给出一个多项式时间的最优算法;对于最小化最大完成时间与惩罚费用之和的情况,给出一个拟多项式时间的动态规划算法;对于考虑生产前运输的最小化最大完成时间的情况,分析了问题的复杂性.证明了第一种情况的最优算法可作为后两种情况的2-近似算法.数值实验表明了算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐立新	东北大学信息科学与工程学院	106	2154	24.0	41.0
2	关静	东北大学信息科学与工程学院	4	14	3.0	3.0
6	宋国骄	东北大学信息科学与工程学院	1	0	0.0	0.0