具有指数和位置学习效应的机器排序问题

Some Scheduling Problems With Exponential Time-dependent and Position-based Learning Effect

本文考虑指数学习效应和位置学习效应同时发生的新的排序模型。工件的实际加工时间不仅依赖于已经加工过工件正常加工时间之和的指数函数,而且依赖于该工件所在的位置。单机排序情形下,对于最大完工时间和总完工时间最小化问题给出多项式时间算法。此外某些特殊情况下,总权完工时间和最大延迟最小化问题也给出了多项时间算法。流水机排序情形,对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法。

In this paper,we introduce a new scheduling model in which both exponential time-dependent learning effect and position-based learning effect exist simultaneously.The actual processing time of a job depends not only on an exponent function of the total normal processing time of the already processed jobs but also on its scheduled position.For the single-machine case,we derive polynomial-time optimal solutions for the problems to minimize makespan and the total completion time.In addition,we also show that the total weighted completion time problem and the maximum lateness problem can be solved in polynomial time under certain conditions.For the case of m-machine permutation flowshop,we present polynomial-time optimal for some special cases of the problems to minimize makespan and the total completion time.