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

【目的】研究与总加权提前损失有关的两个代理单机排序的问题。【方法】第1个代理工件的工期相同,目标函数是最小化总加权提前损失;第2个代理的目标函数是最大正则函数,它的特殊情形为最大完工时间。目标是寻找一个排序,使得在满足第2个代理目标可行的情况下,第1个代理目标函数值最小。【结果】利用背包问题证明了该问题是一般意义下NP难的。【结论】最终给出了总加权提前损失有关的两个代理单机排序问题的一个最优算法,并证明了该算法是拟多项式时间可解的。

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

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

单机下带有松弛工期的最小化总提前损失与误工损失问题

文章研究了具有松弛工期的单机排序问题,决策者需要在确定工件的工期之后确定工件的加工次序.松弛工期是工件的加工时间加上一个给定的常数,这个常数为决策变量,排序的任务是给所有工件分配松弛工期,同时使得目标函数值最小.目标函数值包括工件提前、误工和松弛工期.文章根据不同的损失系数关系,讨论松弛工期的范围,并提出了时间复杂性为O(n3P3logn)的动态规划算法.最后给出了算例分析.

单机带有不可用区间的松弛工期的排序问题

研究了在单机情形下具有不可用区间的松弛工期问题,不可用区间意味着在此区间不允许工件加工,且工件中断可恢复。松弛工期是工件加工时间加上1个给定的常数,这个常数为决策变量,排序的任务是给所有工件分配工期,同时确定工件的加工次序以使得目标函数值最小。目标函数值包括由于工件误工、提前及工期分配而导致的相关损失。根据不同的损失系数关系讨论了松弛工期的范围,提出动态规划算法。证明了动态规划的时间复杂性为O((P+T-p_(min))nP^(2))。通过算例分析说明了算法的可行性。