恶化率与工件无关的线性加工时间调度问题  

Scheduling Problem with Job-independent Deterioration Rates and Linear Processing Times

作　　者：赵传立[1] 唐恒永[1] 

机构地区：[1]沈阳师范大学数学与系统科学学院,辽宁沈阳110034

出　　处：《数学的实践与认识》2005年第3期20-27,共8页Mathematics in Practice and Theory

摘　　要：讨论恶化率与工件无关的线性加工时间调度问题 .对于工件间具有平行链约束 ,目标函数为极小化最大完工时间的单机问题 ,分别就链不允许中断和链允许中断两种情况给出了最优算法 .对于工件间没有优先约束 ,目标函数为极小化完工时间和的平行机问题 ,证明了工件按基本加工时间不减排列可以得到最优调度 .This paper considers the scheduling problem with job-independent deterioration rates and linear processing times. We first consider the single machine problem with parallel chain-structured jobs, the objective is to minimize the makespan. For the two cases, the chains can be interrupted or not, the optimal algorithms are presented, respectively. Then for the parallel machine problem to minimize the sum of completion times, we show that an optimal schedule can be obtained by sequencing jobs in non-decreasing order of basic processing times.

关 键 词：恶化率 线性加工 时间调度 平行链约束 运筹学 单机问题 

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