带有退化效应和序列相关运输时间的排序问题

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.

Scheduling with simple deterioration and past-sequence-dependent delivery times

In this paper, the single-machine scheduling problem with simple deterioration and past-sequence-dependent (p-s-d) job delivery times is considered, in which the processing time of each job is a simple linear increasing function of its starting time. When the machine can process only one job at a time, firstly, the makespan, the total (weighted) completion time and the total lateness minimization problems are solvable in polynomial, the EDD rule is not an optimal solution to the maximum lateness minimization problem, and an optimal solution to the case where jobs have agreeable due dates and deteriorating rates is proposed. When the machine can process up to $b$ jobs simultaneously as a batch, i.e., the parallel-batch scheduling problems, two polynomial time optimal algorithms for the makespan minimization problem and the total weighted completion time minimization problem are presented, respectively.