本文研究了松弛工期下与总加权误工相关的单机双代理排序问题, 这里工件的松弛工期等于工件的加工时间加上某个松弛变量。涉及的两个模型分别为: 模型一是在第二个代理的误工工件个数不超过一个给定值的前提下, 使得第一个代理的总权误工最小; 模型二是在第二个代理的总完工时间不超过一个给定值的前提下, 使得第一个代理的总权误工最小。利用动态规划的方法对于两类问题分别给出了最优性质、拟多项式时间算法、以及时间复杂度分析, 并用算例实验来说明了算法的可行性。

This paper studies the scheduling problems with two competing agents on a single machine to minimize the total weighted tardiness under slack due date, where the slack due date of the job is equal to its actual processing time plus a certain slack variable. It includes two models: the first model is to minimize the total weighted tardiness of the first agent under the condition that the total number of tardiness jobs of the second agent does not exceed a given value; the second model is to minimize the total weighted tardiness of the first agent that the total completion time of the second agent does not exceed a given value. The optimal properties are given by dynamic programming. The pseudo-polynomial time algorithm and its time complexity is presented. Finally, two experiment examples are given to illustrate the feasibility of the algorithm.