一类耦合工件组作业问题的多项式时间算法

• 作者: 徐平生
• 来源期刊: 华东交通大学学报
• 学科: 数学
• 关键词: 耦合工件 时间表 加工全长 多项式时间算法
• 年，卷（期）: 2004,（5）
• 所属期刊栏目: 基础科学
• 页码范围: 130-132
• 页数: 3页
• 分类号: O224
• 字数: 2175字
• 语种: 中文
• DOI: 10.3969/j.issn.1005-0523.2004.05.036

摘要

耦合工件是指一个需经两次不同操作的工件,且这两次操作具有先后次序和一定的时间间隔.给定一组耦合工件,要求确定这些工件在一台机器上的加工顺序及时间安排,使加工全长达到最小,这就是耦合工件组作业问题.对一般情形,该问题已被证明为NP困难.本文讨论并给出了由n个相同的耦合工件构成的耦合工件组作业问题的多项式时间算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐平生		7	17	3.0	4.0