Abstract: In the real medical processes, logistics management and industry production processes, scheduling problems and models with deterioration effects and resource allocations are all very important. In addition, under the just-in-time (JIT) principle, scheduling problems for meeting the due window assignment are also very important. The due window, i.e., the time interval of delivery time, and the earliness-tardiness penalties will be negotiated in advance when customers purchase products.
In this paper, we investigate the single processor (machine) due window assignment scheduling problems with deterioration effects and resource allocations simultaneously. The due window assignment includes the common due window (CONW) assignment and slack due window (SLKW) assignment. There are n independent and non-preemptive jobs to be processed on a single processor, where the processor and all jobs are available at time zero and the processor can only process one job at a time. The actual processing time of a job depends on its start processing time, i.e., a non-decreasing function of its start processing time-deterioration effects, and its allocation of non-renewable resources, i.e., a non-increasing function of resource allocated to this job. For the due window assignment, jobs completed within the due window incur no penalties or costs, but other jobs incur earliness or tardiness penalties. For the CONW assignment, the starting time and finishing time of the common due window are decision variables. For the SLKW assignment, each job is assigned a different due-window based on two common flow allowances, where these two common flow allowances are decision variables.
In linear and convex resource allocation models, our goal is to determine the optimal schedule, resource allocation of jobs, the starting and finishing times of due window assignment, so as to minimize the sum of scheduling cost and resource consumption cost. The scheduling cost includes the linear weighted sum of earliness cost, tardiness cost and due-window assignment cost, and the weights are position-dependent weights, i.e., the weigh only depends on its position in a schedule, but does not correspond to some job. For the CONW assignment, some optimal properties of these problems are presented, i.e., the starting time and finishing time of the common due window are equal to some job completion times; for a given schedule, the optimal resource allocation can be obtained by the properties of linear and convex resource allocation functions. For the SLKW assignment, optimal properties of these problems are also presented, i.e., the common flow allowances are equal to some job completion times; for a given schedule, the optimal resource allocation can be obtained.
In the linear resource allocation model, i.e., the resource consumption function is a bounded linear non-increasing function of non-renewable resource, it is proved that the optimal schedule of these both problems, i.e., the common and slack due window assignments, can be translated into the assignment problem, and the optimal solution algorithm is proposed to solve both problems. The algorithm is analyzed, it is showed that these problems are polynomially solvable, and the time complexity is O(n³), where n is the total number of jobs. In the convex resource allocation model, i.e., the resource consumption function is a convex non-increasing function of non-renewable resource, we show that both problems, i.e., the common and slack due window assignments, can be translated into the two vector matching problem by the optimal properties of convex function, and the optimal solution algorithm is presented to solve both problems. The algorithm is analyzed. It is demonstrated that these both problems can be solved in polynomial time, and the time complexity is O(n log n).
For future research, it is worth investigating the due window assignment problems under flow shop or parallel machine setting, examining the due window assignment problems with job dependent weights, i.e., the weight only depends on the job, but does not correspond to the position in a schedule, or extending the models to general linear and non-linear deterioration functions.

Key words: scheduling, due window assignment, deterioration effect, position-dependent weight, resource allocation

摘要： 考虑工件同时具有恶化效应和资源分配的单机窗口指派排序问题,其中窗口指的是共同窗口和松弛窗口。在线性资源和凸资源分配模型下,目标是确定工件的最优排序、资源分配、窗口的开始和结束时间,使排序费用和资源消耗费用的和最小,其中排序费用为提前费用、延误费用和窗口指派费用的线性加权和,权重为位置权重。对这些问题给出了最优解满足的性质,在线性资源和凸资源分配模型下,证明此问题可分别转化为指派问题和向量匹配问题,并给出了具体求解算法。算法分析表明这些问题都是多项式时间可解的,时间复杂性分别为O(n³)和O(n log n),其中n为工件个数。

关键词: 排序, 窗口指派, 恶化效应, 位置权重, 资源分配