加工时间是开工时间线性分段函数的单机总误工问题

研究工件加工时间是开工时间的线性分段函数的单机排序问题,其中工件的加工时间是开工时间的线性增加函数,但是有一个上界,在时刻T(T是已知常数)以后开始加工的工件,其加工时间不再因开工时间的推迟而增大,优化的目标是极小化总误工工件数.当工件的工期与加工时间满足某种一致性关系的时候,不管工件的加工时间是开工时间的简单线性分段函数,还是其基本加工时间是与恶化率有关的分段线性函数,证明这两种情况都是多项式时间可解的.

Single Machine Scheduling Problem to Minimize the Number of Tardy Jobs With Job Processing Time being Piecewise Linear Function of its Start Time

We consider the single machine scheduling with job processing time being a linearly increasing function of its start time,where job processing time is not steadily increasing, but being a up-bound,when the starting time after T,the job processing time is not increasing.The problem to minimize the number of tardy jobs is discussed.For the case of agreeability of processing time with due date,either job processing time is simple piecewise linear function or job processing time is piecewise linear function with the basic processing time relating to the deterioration rate,we prove both of the two cases are polynomial time solvable.