带有恶化效应和维修恶化的单机工期指派问题

Single Machine Scheduling with Due-Date Assignment and Aging Effect under a Deteriorating Maintenance

研究了同时带有恶化工件和机器恶化维修的单机工期指派问题。工件的实际加工时间是与工件基本加工时间和工件在排序中的实际加工位置相关的一般函数。机器维修时间与其开始维修时间有关,是其线性恶化函数。研究的目标函数是加权提前、延误和工期之和,目的是确定工件的最优加工顺序、公共工期及维修位置,使目标函数最小。将此问题转化为指派问题,从而证明了该问题在多项式时间内是可解的。对于问题的一种特殊情况进一步给出了一个复杂性为O(n2log n)的最优算法。

This paper investigates single-machine due-date assignment and scheduling problems with a job-dependent aging effect un-der a deteriorating maintenance activity consideration simultaneously. The actual processing time of a job is a general function of itsbasic processing time and its position in a sequence. The machine maintenance duration is a deteriorative function of its starting timeand the function is linear. The objective is to find the optimal schedule and maintenance position as well as the optimal location of thecommon due-date for minimizing the total of earliness, tardiness and due-date costs. We introduce a polynomial time solution for theproblem by transforming this problem into the assignment problem. We also present a special case of the problem and show that itcan be optimally solved by a better algorithm in O（nlog n） polynomial time.