公共工期指派和可控处理时间资源约束下最大费用最小化单机排序问题

摘要

本文研究具有公共工期指派的凸资源单机排序问题。任务的实际加工时间是所获得的资源量的凸函数,目标函数是所有任务费用中的最大值。考虑两个问题。在第一个问题中,假设可用资源总数量有限,决策者需要寻找任务的最优排序、公共工期和资源分配方案,使得最大费用最小。第二个问题与第一个问题互补,资源总量没有限制,目标是在最大费用有上界限制条件下,求出最小资源总量、任务排序和公共工期及资源分配方案,使得资源总量最小。分别将上述问题转化为非线性凸规划问题加以处理。证明了两个问题均可以在多项式时间内求出最优解,提供了求解上述问题的多项式时间最优算法。分别给出实例说明算法的运算过程和有效性。