树约束线性加工时间的单机排序问题  

Single Machine Scheduling Problem with Tree-Structured and Linear Processing Times

作　　者：许川容[1] 谢政[2] 张洁[1] 

机构地区：[1]重庆后勤工程学院基础部,重庆400042 [2]国防科技大学数学与系统科学系,长沙410073

出　　处：《系统工程理论方法应用》2006年第5期471-474,共4页Systems Engineering Theory·Methodology·Applications

摘　　要：讨论工件具有线性加工时间,工件间优先约束为树约束的单机排序问题。当目标函数为极小化加权完工时间和时,问题比相应的经典排序问题复杂,在工件间优先约束为出、入树2种情况下,分别给出了该问题最优排序的多项式算法。The single machine scheduling problem is discussed with tree-structured and linear processing time. Although these problems are more complicated than the classical ones when the objective is to minimize the total weighted completion time. The optimal algorithms are given respectively in the case of the precedence being outtree and intree.

关 键 词：排序 线性加工时间 树约束 加权完工时间和 

分 类 号：O223[理学—运筹学与控制论]