摘要
研究了具有线性恶化工件的单机排序问题,其中线性恶化工件指的是工件的加工时间是开工时间的线性增长函数.在一般情况下,对目标函数为极小化完工时间平方和与极小化总误工数问题分别给出了最优算法.此外,在分段情况下,对目标函数为极小化最大完工时间问题也给出了最优算法.
We consider the single machine scheduling with linearly deteriorating jobs, where linearly deteriorating jobs mean that the job processing time of a job is a linearly increasing function of its start time. For the general case, optimal algorithms are presented respectively for minimizing the sum of quadratic completion times and the number of tardy jobs. In addition, for the piecewise case, optimal algorithm is also presented for minimizing the maximal makespan.
出处
《数学的实践与认识》
CSCD
北大核心
2009年第3期146-153,共8页
Mathematics in Practice and Theory
基金
辽宁省教育厅科技研究项目资助(20060662)
关键词
排序
单机
线性函数
完工时间平方和
总误工数
最大完工时间
scheduling
single machine
linear function
sum of quadratic completion times
number of tardy jobs
maximal makespan
