一类线性加工时间单机调度问题(英文)  

Single Machine Scheduling with Linear Processing Times

作　　者：赵传立[1] 张庆灵[1] 唐恒永[2] 

机构地区：[1]东北大学理学院,沈阳110004 [2]沈阳师范大学数学系,沈阳110034

出　　处：《自动化学报》2003年第5期703-708,共6页Acta Automatica Sinica

基　　金：SupportedbyDoctorThesisFoundationofNortheasternUniversity(2 0 0 2 0 8)

摘　　要：讨论一类线性加工时间单机调度问题 .在这类问题中 ,工件具有相同的基本加工时间 ,但每个工件的实际加工时间以其开工时间线性增长 .对满足无延迟工件条件下极小化提前惩罚和问题 ,满足最大完工时间限制条件下极小化资源消耗总量的问题和满足资源消耗总量限制条件下极小化最大完工时间的问题 ,分别给出了最优算法 .This paper considers the single machine scheduling problem. It is assumed that jobs have the same basic processing time, but the actual processing time of each job grows linearly with its starting time. Based on the analysis of the problem, optimal algorithms are presented for the problems to minimize the sum of earliness penalties subject to no tardy jobs, to minimize the total resource consumption with makespan constraints, and to minimize makespan with the total resource consumption constraints.

关 键 词：单机调度问题 线性加工时间 最优算法 提前惩罚问题 

分 类 号：TP13[自动化与计算机技术—控制理论与控制工程]