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

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