带有工期窗口和凸资源分配的单机排序问题

Single-Machine Scheduling with Due-Window Assignment and Convex Resource Allocation

摘要: 讨论具有学习效应和退化效应且工件的加工时间依赖于资源分配的单机排序问题。在凸资源消费函数条件下研究目标函数，所有工件有一个公共工期窗口，工件的实际加工时间依赖于分配给工件的任务量以及不可再生资源数量，同时依赖于工件的开始加工时间，分别考虑了三种情况，第一种是使带有提前，延误，公共工期开始时间，工期窗口大小，资源成本费用，最大完工时间以及总完工时间和最小的问题；第二种是资源费用受限的情况下，极小化带有提前，延误，公共工期开始时间，工期窗口大小，资源成本费用，最大完工时间以及总完工时间和问题。第三种是在带有提前，延误等总费用受限的情况下，极小化总资源量。将上述三种问题转化为匹配问题，并证明其是多项式时间可解的，分别给出三个最优算法。

Abstract: We consider a single machine scheduling problem with learning effect and deterioration effect. The actual processing time of a job is a convex function of the resource amount allocated to it. All jobs have a common due-window. The actual processing time of each job is a convex function dependent on the workload of the job, its starting time and its allocation of non-renewable resource. We consider three models. For the first we aim to minimize the weighted costs of earliness, tardiness, the starting time of the common due-window, the size of the due-window, the makespan and the total completion time. For the second, we constrain the total resource amount to minimize the weighted costs of earliness, tardiness, the starting time of the common due-window, the size of the due-window, the makespan and the total completion time. For the third, we are subject to the constraint that the total cost with early and tardy cost is less than or equal to a fixed amount to minimize the total resource. We show that the problems are polynomial solvable by transforming them into matching problems. Three optimal algorithms are given.