可变加工时间和维护的松弛交货期与凸资源分配单机排序问题

摘要

本文研究带有可变加工时间和维护的松弛交货期与凸资源分配的单机排序问题。工件的实际加工时间是所分配的不可再生资源量和与工件位置、开始时间有关的退化效应的函数。在规划时间内最多允许执行一次维护活动。确定最优工件排序、最优公共松弛时间、最优维护位置和最优资源分配方案,使得由工件的提前惩罚、延误惩罚、交货期公共松弛时间、资源分配费用、最大完工时间和总完工时间构成的总费用最小。根据优化的相关知识,将问题转化为匹配问题,证明了该问题在多项式时间内是可解的,给出了多项式时间最优算法。