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

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

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

[Purposes]A common due-date assignment and scheduling problem is studied.The objective function is the maximal cost among all jobs.[Methods]The processing time of a job is a convex function of a resource which is allocated to it.Two problems are considered.In the first problem.assuming that the total number of available resources is limited,the aim is to find job sequence,common due-date and the resource allocation policy simultaneously to minimize the maximal cost among all jobs.The second problem is complementary with the first one.There is no limit on the total amount of resources with an upper bound on the maximum cost,the objective is to find minimum amount of resources,task ordering,public schedule and resource allocation simultaneously to minimize the resource amount of all jobs.[Findings]The problems are converted to nonlinear convex programming.[Conclusions]Two optimal algorithms are presented that can be used to solve the above problems respectively.Two examples are given to show how to realize the algorithms.