具有非线性恶化函数和安装时间的单机排序问题

Scheduling with a nonlinear deterioration function and setup time in a single machine

研究了具有非线性恶化函数的加工时间,同时工件的安装时间与已加工完工件的实际加工时间有关(即p-sd)的单机排序问题.证明了极小化最大完工时间,极小化完工时间和是多项式时间可解的.另外极小化加权完工时间和,极小化总延误以及极小化最大延误在一定的条件下是多项式时间可解的.

The single machine scheduling with a nonlinear deterioration function processing time and the pastsequence-dependent （p-s-d） setup time was considered. The problem was proved to minimize the makespan, total completion time were polynomial time solvable. In addition, the problem to minimize the total weighted completion time, the total tardiness and the maximum lateness were polynomial time solvable under certain condition.