摘要
研究了最小化总加权提前损失单机排序问题,
其中提前损失是工件在工期之前完成的各部分的持续加工时间. 首先,
文章分析了总加权提前损失问题在中断情况下的复杂性,
提出了中断排序算法, 用算例进行了验证;
接着通过设计拟多项式动态规划算法,
说明该问题在非中断情况下是一般意义下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.
关键词
单机排序, 总加权提前损失, 动态规划算法.
{{custom_keyword}} /
栗苹, 张新功, 万庆.
关于总加权提前损失的单机排序问题. 系统科学与数学, 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
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}