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

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