关于总加权提前损失的单机排序问题  

Single Machine Scheduling Problem with Minimize Total Weighted Early Work

作　　者：栗苹 张新功 万庆 LI Ping;ZHANG Xingong;WAN Qing(School of Mathematical Science,Chongqing Normal University,Chongqing 401331;Chongqing Yucai High School,Chongqing 400050)

机构地区：[1]重庆师范大学数学科学学院,重庆401331 [2]重庆育才中学,重庆400050

出　　处：《系统科学与数学》2021年第4期1068-1078,共11页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金重大项目(11991020,11991022);国家自然科学基金面上项目(11971443);重庆市科委项目(cstc2018jcyjAX0631);重庆市教委重点项目(KJ202000540429672);重庆市研究生教育教学改革研究重点项目(yjg182019);重庆师范大学研究生科研创新项目(YKC20040)资助课题。

摘　　要：研究了最小化总加权提前损失单机排序问题,其中提前损失是工件在工期之前完成的各部分的持续加工时间.首先,文章分析了总加权提前损失问题在中断情况下的复杂性,提出了中断排序算法,用算例进行了验证,接着通过设计拟多项式动态规划算法,说明该问题在非中断情况下是一般意义下NP难的,并进行了数据实验,验证了该算法的有效性.In this paper,we consider the single machine scheduling problem to minimize the total weighted early work.The early work of a job is a duration of the parts of the job completed prior to its due-date.First,this paper analyzes the complexity of the total weighted early work problem with preemptive case,and proposes an Interruption Scheduling Algorithm.Second,the problem without preemptive case is illustrated to be NP-hard by designing a quasi-polynomial dynamic programming algorithm,and data experiments are performed to verify the effectiveness of the algorithm.

关 键 词：单机排序 总加权提前损失 动态规划算法 

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