工期窗口指派可控处理时间资源约束最大费用最小化排序问题

【目的】研究具有公共工期窗口指派的凸资源单机排序问题。【方法】任务的处理时间与所在位置有关,并且可以通过分配一定的资源加以控制,是所获得的资源量的凸函数。目标函数是所有任务费用中的最大值。考虑两个问题。第1个问题是在资源总量有上界限制条件下,确定任务的最优排序、公共工期窗口位置和大小以及资源分配方案,使得最大费用最小。第2个问题是在最大费用有上界限制条件下,求出最小资源总量、任务排序和公共工期窗口位置和大小,使得资源总量最小。【结果】将上述问题转化为非线性凸规划问题和指派问题加以处理。证明了两个问题均可以在多项式时间内求解。【结论】对于考虑的两个问题分别给出了多项式时间最优算法。

Minmax Scheduling Problem with Common Due-Date and Controlled Processing Times and Resource Restriction