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

栗苹, 张新功, 万庆

系统科学与数学 ›› 2021, Vol. 41 ›› Issue (4) : 1068-1078.

PDF(482 KB)
PDF(482 KB)
系统科学与数学 ›› 2021, Vol. 41 ›› Issue (4) : 1068-1078. DOI: 10.12341/jssms20036

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

    栗苹1,张新功1,万庆2
作者信息 +

Single Machine Scheduling Problem with Minimize Total Weighted Early Work

    LI Ping1 ,ZHANG Xingong1, WAN Qing2
Author information +
文章历史 +

摘要

研究了最小化总加权提前损失单机排序问题, 其中提前损失是工件在工期之前完成的各部分的持续加工时间. 首先, 文章分析了总加权提前损失问题在中断情况下的复杂性, 提出了中断排序算法, 用算例进行了验证; 接着通过设计拟多项式动态规划算法, 说明该问题在非中断情况下是一般意义下NP难的, 并进行了数据实验, 验证了该算法的有效性.

Abstract

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.

关键词

单机排序, 总加权提前损失, 动态规划算法.

引用本文

导出引用
栗苹, 张新功, 万庆. 关于总加权提前损失的单机排序问题. 系统科学与数学, 2021, 41(4): 1068-1078. https://doi.org/10.12341/jssms20036
LI Ping, ZHANG Xingong, WAN Qing. Single Machine Scheduling Problem with Minimize Total Weighted Early Work. Journal of Systems Science and Mathematical Sciences, 2021, 41(4): 1068-1078 https://doi.org/10.12341/jssms20036
PDF(482 KB)

Accesses

Citation

Detail

段落导航
相关文章

/