具有线性恶化加工时间的调度问题

摘要

讨论了工件具有线性恶化加工时间的调度问题.在这类问题中,工件的恶化函数为线性函数.对单机调度问题中目标函数为极小化最大完工时间加权完工时间和,最大延误以及最大费用等问题分别给出了最优算法.对两台机器极小化最大完工时间的Flowshop问题,证明了利用Johnson规则可以得到最优调度.对于一般情况,如果同一工件的工序的加工时间均相等,则Flowshop问题可以转化为单机问题.%This paper considers the scheduling problem under linear deterioration. It is assumed that the deterioration function is a linear function. Optimal algorithms are presented respectively for single machine scheduling problems of minimizing the makespan, weighted sum of completion times, maximum lateness and maximum cost. For two-machine flow shop scheduling problem to minimize the makespan, it is proved that the optimal schedule can be obtained by Johnson′s rule. If the processing times of operations are equal for each job, flow shop scheduling problems can be transformed into single machine scheduling problems.