排序方式: 共有99条查询结果,搜索用时 31 毫秒
11.
研究两台平行机环境下加工时间线性退化的可拒绝排序问题,工件的实际加工时间是关于该工件开始加工时间的线性函数,每个工件都有一个独立的截止工期,在截止工期之前或之后完工的任务将分别受到提前和误工工件惩罚。工件允许被拒绝,如果工件被拒绝则需要支付一定的拒绝费用。目标是分别确定接受工件和拒绝工件的任务集合,找到接受任务的最优排序和每个被接受工件的最优任务工期最小化工期、误工工件惩罚、总完工时间以及被拒绝工件的惩罚费用之和。证明了此 NP 难问题可以通过动态规划方法求得最优解,并通过动态规划运用简化执行空间的方法给出了复杂度为o(n5D2/ε2)的全多项式近似策略(FPTAS),其中 n 表示工件的数量,ε 是允许误差界。
相似文献
相似文献
12.
考虑了二机流水作业第一台机器带不可用区间、工件可拒绝的调度问题.所有的工件都是加工可中断的,即当某一工件在不可用区间出现之前开始加工但在机器不可用时并未加工完成,在不可用区间结束后可以接着加工.目标函数是最小化接受加工工件的最大完工时间与拒绝工件的惩罚之和.此问题是NP-难的.首先提出了一个动态规划的最优算法以求解小规模问题,并给出了数值计算实例.所提出的动态规划算法的运算时间随着问题的规模成指数增长,进而又提出了一个启发式算法,并证明了该启发式算法的最坏性能比是3. 相似文献
13.
【目的】考虑带有退化工件、拒绝和不可用区间的单机排序问题。【方法】假设工件有不同的基本加工时间和相同的退化率,工件可以被拒绝,被拒绝的工件需要支付拒绝惩罚,机器在给定的时间区间内是不可用的且工件不可恢复。目标是极小化接受工件的总完工时间与被拒绝工件的总拒绝惩罚之和。【结果】对于这个NP-难问题,在不可用区间前、后,工件按照基本加工时间aj的非减顺序排列可以得到最优解,给出一个拟多项式时间动态规划算法和一个完全多项式时间近似策略。【结论】推广了已有文献的模型。 相似文献
14.
《中南民族大学学报(自然科学版)》2017,(3):131-136
针对现在对低速率分布式拒绝攻击的研究不足,提出了一种在软件定义网络(SDN)环境下,利用Renyi熵来检测L-DDoS的方法.该方法首先在控制器上收集PACKET_IN数据包,然后基于目的 IP来计算Renyi熵,最后通过设定一定的阈值来检测异常流量.实验结果表明:相比于利用香农熵的检测方法,该方法通过调整一定目的 IP熵的阶数可以检测L-DDoS攻击流量从而降低误警率. 相似文献
15.
考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.如果拒绝一个工件,要花费一定的惩罚费用;如果接受这个工件,在m台机器中的一台上分批加工,定义一批的加工时间为这批中所包含的最长工件的加工时间.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的数时,给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案. 相似文献
16.
使用傅里叶变换处理结构突变是单位根检验中的流行方法之一,其中整数频率和分数频率分别对应暂时性结构变化和永久性结构变化,这一区分在实证应用中具有重要的经济含义,但其对计量理论的影响尚不清楚.本文研究当真实数据生成过程包含分数频率傅里叶型结构变化时,忽略傅里叶项对标准Dickey-Fuller单位根检验性质的影响.通过重新参数化,推导了相应的极限分布,探讨极限结果对标准Dickey-Fuller检验性质的理论预测,给出了Dickey-Fuller检验伪拒绝发生的条件.模拟的证据与本文的理论结果一致.研究结果表明:永久性结构变化更容易引起DickeyFuller检验的伪拒绝问题.因此,忽略分数频率傅里叶项或将其误设为整数频率都会导致错误的实证结果. 相似文献
17.
18.
讨论了带有交货期窗口和工件可拒绝的单机排序问题﹐这一问题是将所有的工件分成两个集合﹐一个是被接受的工件集﹐一个是被拒绝的工件集。假设被接受的每个工件都有一个待定的交货期窗口﹐且所有工件的交货期窗口的大小是相同的﹐如果工件在窗口中完工﹐则不产生任何费用;否则工件提前或延误﹐会产生相应的提前或延误的费用。而对于拒绝工件而言﹐它的费用只与工件有关。这类问题的总费用是2个工件集的费用之和。目标函数是确定被接受工件的最优排序﹐极小化总费用﹐给出了一个动态规划算法﹐并证明了这个问题是多项式时间可解的。 相似文献
19.
考虑的是机器需要维护,且需要对若干个退化工件进行加工的单机排序问题。所谓退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工件允许被拒绝,如果工件被拒绝,那么需要支付拒绝惩罚;如果被加工,那么工件被排在机器上(机器需要在某一个固定的时间段内进行维修以提高其加工速度,且在这段时间内机器不能加工任何工件)进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚之和最小。对于单机情形,利用划分程序的方法给出了一个全多项式近似方案,并得出该近似方案的时间复杂性,说明该问题是一般意义下NP-难的。 相似文献
20.
针对《计算机图形学》中线裁剪算法要点较多、从思想到具体算法的实现需要一定的技巧性和数据结构较复杂等特点,通过简单的裁剪实例,在引导学生积极思考、讨论的过程中,使学生发现裁剪中拒绝线段或接受线段的一些规律。通过引导学生主动地发现知识,而非被动地接受知识,从而较好地达到了教学目的。 相似文献