摘要
讨论一类线性加工时间单机调度问题 .在这类问题中 ,工件具有相同的基本加工时间 ,但每个工件的实际加工时间以其开工时间线性增长 .对满足无延迟工件条件下极小化提前惩罚和问题 ,满足最大完工时间限制条件下极小化资源消耗总量的问题和满足资源消耗总量限制条件下极小化最大完工时间的问题 ,分别给出了最优算法 .
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.
出处
《自动化学报》
EI
CSCD
北大核心
2003年第5期703-708,共6页
Acta Automatica Sinica
基金
SupportedbyDoctorThesisFoundationofNortheasternUniversity(2 0 0 2 0 8)
关键词
单机调度问题
线性加工时间
最优算法
提前惩罚问题
Algorithms
Constraint theory
Enterprise resource planning
Job analysis
Optimization
Scheduling
Theorem proving
