具有恶化效应和凸资源分配关系的单机排序问题

研究工件加工时间具有恶化效应和凸资源关系的单机排序问题,其中工件的实际加工时间是其正常的加工时间,工件开工时间(具有恶化效应)及消耗资源量的函数。目标为在最大完工时间(总完工时间、总等待时间、完工时间总绝对差与等待时间总绝对差)小于或等于给定常数的条件下找到工件的最优排序和最优的资源分配使工件的总资源消耗量最少。在单机状态下,证明了此问题是多项式时间可解的,并给出了求解该问题的算法和数值实例。

Single Machine Scheduling with Deterioration Effectand Convex Resource Allocation

In this paper we consider the single machine scheduling problem with deterioration effect and convex resource allocation, in which the actual processing time of a job is the function of its normal processing time, its starting time(deterioration effect)and resource quantities. The objective is to find the optimal schedule and the resource allocation of jobs so as to minimize total resource quantities consumed when the makespan(total completion time, total waiting time, total absolute differences in completion times, total absolute differences in waiting times) is up bounded by a given parameter. In the single machine case, we prove that this problem can be solved in polynomial time. Also, we give an algorithm and a numerical example to show how to solve an example problem.