基于松弛工期的总加权误工单机双代理排序问题  

Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness

作　　者：崔同欣 夏倩 张新功 CUI Tongxin;XIA Qian;ZHANG Xingong(School of Mathematical Sciences,Chongqing Normal University,Chongqing 401331,China)

机构地区：[1]重庆师范大学数学科学学院,重庆401331

出　　处：《运筹学学报(中英文)》2025年第1期31-40,共10页Operations Research Transactions

基　　金：国家自然科学基金重大项目(No.11991022);国家自然科学基金面上项目(No.11971443);重庆市教委重点项目(No.KJZD-K202000501);重庆市教委研究生教改重点项目(No.YJG182019);重庆市科委项目(No.cstc2021jcyj-msxmX0229);重庆市自然科学基金创新发展联合基金项目(No.CSTB2023NSCQ-LZX0005)。

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

关 键 词：排序 双代理 总权误工 动态规划算法 

分 类 号：O223[理学—运筹学与控制论]