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

A Polynomial Time Algorithm of the Coupled-task Scheduling

作　　者：徐平生[1] 

机构地区：[1]华东交通大学,江西南昌330013

出　　处：《华东交通大学学报》2004年第5期130-132,共3页Journal of East China Jiaotong University

摘　　要：耦合工件是指一个需经两次不同操作的工件,且这两次操作具有先后次序和一定的时间间隔.给定一组耦合工件,要求确定这些工件在一台机器上的加工顺序及时间安排,使加工全长达到最小,这就是耦合工件组作业问题.对一般情形,该问题已被证明为NP困难.本文讨论并给出了由n个相同的耦合工件构成的耦合工件组作业问题的多项式时间算法.A coupled-task is a job consisting of two distinct operations. These operations require to be processed in a predetermined order and at a specified interval apart. Given a group of coupled-task job, the coupled-task problem asks to find a processing sequence and a corresponding schedule on a single machine with the objective of minimizing the makespan. In general, this problem has been proved to be NP-hard. A polynomial time algorithm for the scheduling problem of identical coupled-task jobs is presented in this paper.

关 键 词：多项式时间算法 作业问题 耦合 加工顺序 次序 证明 一般 工件 机器 

分 类 号：U491.6[交通运输工程—交通运输规划与管理] O13-4[交通运输工程—道路与铁道工程]