具有退化维护和资源分配的单机排序问题

Single machine scheduling problem with deteriorating maintenance and resource allocation

研究具有退化维护和资源分配的单机松弛交货期指派排序问题。工件的实际加工时间是所获得的资源量和与工件位置、时间有关的退化效应的函数。为了消除机器的退化效应,可以对其进行维护,假设在规划范围内最多只能允许执行一次维护活动,且任何一个工件加工完成之后可以立即进行维护,维护的持续时间依赖于它的开始时间。在资源总量有限的条件下确定最优公共松弛时间、最优维护位置、最优资源分配方案和最优工件排序,使得由工件的提前惩罚、延误惩罚、交货期公共松弛时间、最大完工时间、总完工时间构成的总费用最小。根据凸优化的相关知识,将问题转化为指派问题,证明了该问题在多项式时间内是可解的,给出了多项式时间最优算法。

This paper studies a single machine scheduling and slack due-date assignment problem with deteriorating maintenance and resource allocation.The actual processing time of a job is a function of the resource amount allocated,position-dependent and time-dependent deterioration effect.In order to counteract the deterioration effect on the machine,we can add a maintenance activity and we assume that at most one maintenance is allowed throughout the planning horizon and the maintenance can be performed immediately after the processing of any job completed,the maintenance duration is dependent on its starting time.The objective is to determine the optimal common slack time,the optimal maintenance position,the optimal resource allocation and the optimal job schedule to minimize the total costs of the earliness and tardiness of the jobs,the common slack time,the makespan and the total completion time under the condition that the total resource amount is limited.According to the related knowledge of convex optimization,we show that the problem is polynomial solvable by transforming it into an assignment problem.We present a polynomial time optimal algorithm to solve the problem.