加工时间依赖工件位置的树约束单机排序问题  

Single machine scheduling with tree-restricted and position-dependent processing times

作　　者：石国春[1] 

机构地区：[1]兰州工业高等专科学校基础学科部,甘肃兰州730050

出　　处：《商丘师范学院学报》2010年第12期43-46,共4页Journal of Shangqiu Normal University

摘　　要：讨论了工件的加工时间依赖于工件位置的树约束单机排序问题,给出了目标函数为最大完工时间的多项式算法.结果表明,最大家庭树中的工件优先于其它家庭树中的工件加工,并且其工件要连续加工所得到的排序为最优排序.The single machine scheduling problem is considered with tree-structured and processing time dependent on their position in the sequence.A Polynomial algorithm of makespan is obtained.In this case,jobs in the maximal family tree should be proceed prior to other jobs in family tree and the optimal schedule is obtained if their jobs aren＇t be preempted by the other jobs.

关 键 词：单机 排序 树约束 最大完工时间 最大家庭树 

分 类 号：O221.1[理学—运筹学与控制论]