• • 上一篇    下一篇

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

栗苹1,张新功1,万庆2   

  1. 1. 重庆师范大学数学科学学院, 重庆 401331; 2. 重庆育才中学, 重庆 400050
  • 出版日期:2018-04-25 发布日期:2021-06-29

栗苹, 张新功, 万庆. 关于总加权提前损失的单机排序问题[J]. 系统科学与数学, 2021, 41(4): 1068-1078.

LI Ping, ZHANG Xingong, WAN Qing. Single Machine Scheduling Problem with Minimize Total Weighted Early Work[J]. Journal of Systems Science and Mathematical Sciences, 2021, 41(4): 1068-1078.

Single Machine Scheduling Problem with Minimize Total Weighted Early Work

LI Ping1 ,ZHANG Xingong1, WAN Qing2   

  1. 1. School of Mathematical Science, Chongqing Normal University, Chongqing 401331; 2. Chongqing Yucai High School, Chongqing 400050
  • Online:2018-04-25 Published:2021-06-29
研究了最小化总加权提前损失单机排序问题, 其中提前损失是工件在工期之前完成的各部分的持续加工时间. 首先, 文章分析了总加权提前损失问题在中断情况下的复杂性, 提出了中断排序算法, 用算例进行了验证; 接着通过设计拟多项式动态规划算法, 说明该问题在非中断情况下是一般意义下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.
()
No related articles found!
阅读次数
全文


摘要