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

Minmax Single Machine Scheduling Problem with Common Due-Date and Controllable Processing Time and Resource Restriction

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

Abstract: This paper studies a common due-date assignment and scheduling problem. The objective function is the maximal cost among all jobs. The processing time of a job is a convex function of a resource allocated to it. Two problems are considered. In the first problem, the aim is to find imultaneously the job sequence and common due-date, as well as the resource allocation policy to optimilty that minimize the maximal cost among all jobs, subject to an upper bound on resourse amount. The second problem is complementary with the first one. The objective is to find imultaneously the optimal job sequence and due-date that minimize the resource amount of all jobs, subject to an upper bound on maximal cost among all jobs. The problems are converted to nolinear convex programmings. We present optimal algorithms that can be used to solve the above problems, respectively. Two examples are given to show how to realize the algorithms.