具有可控和依赖位置负荷处理时间的资源约束单机排序问题

摘要

cqvip:本文研究具有与任务和位置有关的可控处理时间的凸资源单机排序问题。任务的实际加工时间是所获得的资源量、与任务所在位置有关负荷的函数。考虑两个问题。第一个问题是在资源总量有上界限制条件下,确定任务排序、资源分配方案,使得时间表长最小。第二个问题中资源总量没有限制,目标是求出最小资源总量、任务排序和资源分配方案,使得由时间表长和资源总量加权和取最小值。分别证明了上述问题可以在多项式时间内求出最优解,并给出了求解相应问题的多项式时间最优算法。