可用性约束资源预留与分配算法 被引量：2

1

作者 李波 石冰心 沈斌 《计算机科学》 CSCD 北大核心 2005年第2期28-30,共3页

给定一系列作业和只能在有限的时间段可用的资源,如何预留和分配资源以实现作业的最大完成时间最小化的问题是NP难的。本文将其归结为一种新型的尺寸可变装箱问题并给出了作业信息和资源信息完全已知条件下的六种离线算法,理论分析表明... 给定一系列作业和只能在有限的时间段可用的资源,如何预留和分配资源以实现作业的最大完成时间最小化的问题是NP难的。本文将其归结为一种新型的尺寸可变装箱问题并给出了作业信息和资源信息完全已知条件下的六种离线算法,理论分析表明所给算法的渐进最坏比为2,在作业相互独立的条件下推广的降序最佳适合(Best FitDecreasing)算法的平均性能最优,在作业有先后依赖关系的条件下推广的最佳适合(Best Fit)算法的平均性能最优。 展开更多

关键词 算法 归结 完成时间 资源信息 资源预留 最优 可用性 务件 作业 平均

下载PDF 职称材料

基于统计量特征的数据库指纹方法

2

作者 方焱志 黄煜坤 彭煜玮 《软件学报》 EI CSCD 北大核心 2022年第9期3422-3436,共15页

在数据库中嵌入数字水印作为指纹是一种重要的数据库版权保护与身份溯源技术,它对推动数据的共享融合起到了重要的保障作用.针对现有数据库指纹方法在数据普适性上的不足开展研究,提出了一种基于统计量特征的数据库指纹方法.首先,采用... 在数据库中嵌入数字水印作为指纹是一种重要的数据库版权保护与身份溯源技术,它对推动数据的共享融合起到了重要的保障作用.针对现有数据库指纹方法在数据普适性上的不足开展研究,提出了一种基于统计量特征的数据库指纹方法.首先,采用了迭代哈希的数据划分方法将数据划分为多个子集;然后,通过最优化算法将过滤极值后的数据子集特征最大/最小化,根据基于最小错误率的贝叶斯决策计算得到最优阈值作为指纹信息.通过理论分析验证了该方法的可行性与有效性,同时也通过真实数据集上的实验结果证明了所提算法在抗攻击能力和普适性上的优势. 展开更多

关键词 数字水印 数据库指纹 统计量特征 可用性约束 鲁棒性水印

下载PDF 职称材料

带有可变加工时间和可用性限制的排序问题 被引量：1

3

作者 党蕊 赵玉芳 《沈阳师范大学学报（自然科学版）》 CAS 2015年第1期28-32,共5页

研究带有恶化效应、学习效应和可用性限制的单机和2台平行机的排序问题。在这个模型中,工件的实际加工时间与其基本加工时间、加工过程中所排位置及开始加工时间有关;同时由于维修、保养等原因,使得机器在某段时间不能加工工件,即机器... 研究带有恶化效应、学习效应和可用性限制的单机和2台平行机的排序问题。在这个模型中,工件的实际加工时间与其基本加工时间、加工过程中所排位置及开始加工时间有关;同时由于维修、保养等原因,使得机器在某段时间不能加工工件,即机器具有可用性限制,且维修之后机器性能完全恢复,讨论的目标函数为总完工时间。对于可以在任意时间只维修一次的单机问题,以及只有一台机器具有可用性限制的2台平行机问题,分别给出了拟多项式时间的动态规划算法。特别对于一台机器只在零时刻开始维修另一台机器无可用性限制的特殊情况,通过将其转化为指派问题,给出了复杂性为O(n4)的多项式时间最优算法,并通过一个数值例子说明了其计算过程。 展开更多

关键词 排序 可用性限制 恶化效应 学习效应 指派问题

下载PDF 职称材料

异构系统中一种基于可用性的抢占式任务调度算法 被引量：1

4

作者 余莹 李肯立 《计算机应用研究》 CSCD 北大核心 2010年第7期2498-2501,共4页

针对大多数现有的异构系统调度算法没有考虑由多类任务特别是抢占式任务所引起的可用性需求的不足,在现有基于可用性的非抢占式任务调度算法的基础上,通过计算任务的平均等待时间来确定优先级等级,对异构系统中多类抢占式任务的可用性... 针对大多数现有的异构系统调度算法没有考虑由多类任务特别是抢占式任务所引起的可用性需求的不足,在现有基于可用性的非抢占式任务调度算法的基础上,通过计算任务的平均等待时间来确定优先级等级,对异构系统中多类抢占式任务的可用性约束的调度问题进行了探索,提出了一种基于可用性的抢占式优先调度算法P-SSAC。该算法在不增加硬件代价的前提条件下通过调度增加了系统的可用性,缩短了任务的平均等待时间,同时该算法可对抢占式的任务进行有效调度。仿真实验结果表明,该算法有效实现了异构系统可用性和任务等待时间之间的折中。 展开更多

关键词 异构系统 可用性约束 多类任务 优先调度 抢占式

下载PDF 职称材料

机器带有不可用区间的可拒绝平行机排序问题（英文）

5

作者 池晶晶 《曲阜师范大学学报（自然科学版）》 CAS 2016年第3期42-48,共7页

主要研究了机器带有拒绝和不可用区间的可拒绝排序问题.针对这一问题的两种情形进行研究.一方面,考虑了每台机器有一个不可用区间,且目标函数是极小化总完工时间与拒绝费用之和的平行机排序问题.另一方面,考虑了工件的实际加工时间是开... 主要研究了机器带有拒绝和不可用区间的可拒绝排序问题.针对这一问题的两种情形进行研究.一方面,考虑了每台机器有一个不可用区间,且目标函数是极小化总完工时间与拒绝费用之和的平行机排序问题.另一方面,考虑了工件的实际加工时间是开始时间的按比例函数的平行机排序问题,并且每台机器在一段特定的区间内不可用.当然,可以通过支付拒绝惩罚费用而拒绝加工工件,这一问题的目标是极小化总加权完工时间与拒绝费用之和.对于以上两个问题,分别给出了时间复杂性为O（nm（∏i=1^mSi）（P_n）^m）和O（n∏i=1^m（S_i-t_0）∏i=1^mT_i（A_n）^m）的伪多项式时间动态规划算法. 展开更多

关键词 排序 拒绝 不可用区间 退化效应

下载PDF 职称材料

带不可用时间段和恶化加工时间的单机调度 被引量：5

6

作者 马英 左春荣 杨善林 《系统工程学报》 CSCD 北大核心 2010年第3期371-378,共8页

对机器带有一个不可用时间段并且加工时间恶化的不可续型单机最大完工时间调度问题进行了研究,简单说明了此问题的NP-困难性,提出了一种动态规划算法以得到最优解,并给出了最短正常加工时间优先规则的最坏情况误差界限,最后提出了一种... 对机器带有一个不可用时间段并且加工时间恶化的不可续型单机最大完工时间调度问题进行了研究,简单说明了此问题的NP-困难性,提出了一种动态规划算法以得到最优解,并给出了最短正常加工时间优先规则的最坏情况误差界限,最后提出了一种启发式算法来寻求近似解.实验结果表明该启发式算法无论从时间上还是解的质量上都是非常优异的,与动态规划给出的最优解相比,其平均相对误差仅为0.082%,最大误差也仅为3.448%,并且将近有一半的算例能得到最优解. 展开更多

关键词 单机调度 不可用时间段 恶化加工时间 动态规划 启发式算法

下载PDF 职称材料

带有学习效应和机器可用性限制的排序问题 被引量：5

7

作者 王纯 赵传立 《系统工程与电子技术》 EI CSCD 北大核心 2009年第6期1372-1375,共4页

针对单机和两台机器的平行机排序问题,建立了机器具有学习效应和可用性限制的排序模型。在这个模型中,机器具有学习效应。在学习效应下,工件的加工时间与所排位置有关,对于需要在同台机器上加工的工件,工件随位置的靠后其实际的加工时... 针对单机和两台机器的平行机排序问题,建立了机器具有学习效应和可用性限制的排序模型。在这个模型中,机器具有学习效应。在学习效应下,工件的加工时间与所排位置有关,对于需要在同台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。同时由于定期维修等原因而导致机器在某段时间内不能加工工件。考虑了目标函数为极小化总完工时间的单机和两台机器的平行机问题。对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法。 展开更多

关键词 排序 可用性限制 学习效应 动态规划 指派问题

下载PDF 职称材料

机器具有可用性限制的加权总完工时间问题 被引量：5

8

作者 崔苗苗 赵玉芳 王松丽 《沈阳师范大学学报（自然科学版）》 CAS 2012年第2期157-163,共7页

研究一种带有学习和恶化效应,并且机器具有可用性限制的排序问题。讨论的目标函数为加权总完工时间的单机和两台机器的平行机问题。在某些实际生产过程中,工件加工时间的变化既受生产设备长时间使用,导致恶化现象的影响,也受生产设备或... 研究一种带有学习和恶化效应,并且机器具有可用性限制的排序问题。讨论的目标函数为加权总完工时间的单机和两台机器的平行机问题。在某些实际生产过程中,工件加工时间的变化既受生产设备长时间使用,导致恶化现象的影响,也受生产设备或工人加工效率提高的影响。因此,在这种模型中,工件的实际加工时间不仅与它的所排位置有关,而且还与工件的开始加工时间有关。此外,由于机器发生故障或进行维护与保养等原因,导致其在某一区间内无法加工工件。针对某种学习和恶化效应模型下机器在任意时间段维修的单机和2台机器的平行机的某些情况,分别给出了拟多项式时间动态规划算法,分析了算法复杂性,并给出相应数值例子表明算法的有效性。 展开更多

关键词 排序 学习效应 恶化效应 机器可用性限制 动态规

下载PDF 职称材料

机器使用有限制的两台同类机排序 被引量：1

9

作者 李红英 苏纯洁 《华东理工大学学报（自然科学版）》 EI CAS CSCD 北大核心 2005年第4期512-516,共5页

研究两台同类机的排序问题,其中一台机器在一个给定的时间段内不可用,目标函数为工件的最大完工时间。证明了LPT算法的性能比是max{32,1s2},并说明了这个界是紧的。

关键词 同类机 使用限制 算法 性能比

下载PDF 职称材料

带不可用时间段的两台同类机加权完工时间和调度 被引量：1

10

作者 马英 左春荣 杨善林 《中国科学技术大学学报》 CAS CSCD 北大核心 2009年第6期665-672,共8页

研究了两台同类机加权完工时间和调度,其中一台机器在一个固定的时间段内不可用,并且被不可用时间段中断的工件是部分可续的,即被中断工件在机器不可用之前已加工的部分在机器重新可用之后需进行部分重新加工.首先简单说明了此问题的NP... 研究了两台同类机加权完工时间和调度,其中一台机器在一个固定的时间段内不可用,并且被不可用时间段中断的工件是部分可续的,即被中断工件在机器不可用之前已加工的部分在机器重新可用之后需进行部分重新加工.首先简单说明了此问题的NP难性,然后证明了最优调度的一个性质,并在此基础上提出了一种动态规划算法来求得小规模问题的最优解,另外还提出了一种启发式算法来求得中大规模问题的近优解.实验结果表明了这两种算法的有效性. 展开更多

关键词 同类机调度 不可用时间段 部分可续型 加权最短加工时间优先规则 动态规划

下载PDF 职称材料

基于逆高斯退化过程的面向任务系统CBM优化模型

11

作者 陈云翔 李京峰 +1 位作者 项华春 李恒年 《系统工程与电子技术》 EI CSCD 北大核心 2022年第1期338-346,共9页

针对现有单调退化系统视情维修(condition-based maintenance, CBM)优化模型中不完全维修影响考虑单一,且未同时融入可用度约束的问题,提出一种考虑不完全维修双重影响与可用度约束的单调退化系统CBM优化模型。首先,基于具有随机漂移系... 针对现有单调退化系统视情维修(condition-based maintenance, CBM)优化模型中不完全维修影响考虑单一,且未同时融入可用度约束的问题,提出一种考虑不完全维修双重影响与可用度约束的单调退化系统CBM优化模型。首先,基于具有随机漂移系数的逆高斯过程,建立系统退化模型并得到相关概率分布;其次,描述任务背景下系统演化过程,建立不完全维修后的剩余损伤模型,提出随机漂移系数更新公式;然后,结合可用度约束给出系统维修或在3种时机更换的概率公式,并建立CBM优化模型;最后,通过数值实验对模型进行对比和敏感性分析,验证了该模型的可行性和应用价值。 展开更多

关键词 不完全维修 可用度约束 单调退化系统 逆高斯过程 视情维修优化

下载PDF 职称材料

机器有使用限制的两台同类机排序的在线LS算法

12

作者 李红英 《华东理工大学学报（自然科学版）》 EI CAS CSCD 北大核心 2006年第9期1134-1137,共4页

研究了机器有使用限制的两台同类机排序问题的在线算法,对于Q2 a(M1)Cmax和Q2 a(M2)Cmax问题,证明了LS算法的竞争比分别为1+s12和s2+s12,并举例说明了这两个界是紧的。

关键词 同类机 使用限制 在线算法 竞争比

下载PDF 职称材料

带有一个不可用区间的两台平行机可拒绝排序问题（英文）

13

作者 池晶晶 孙燕 《曲阜师范大学学报（自然科学版）》 CAS 2016年第1期36-41,共6页

本文主要研究两台平行机排序问题,其中一台机器上有一个固定的不可用区间。此外,生产商可以通过支付惩罚费用来拒绝工件。目标是极小化最大时间表长与惩罚费用之和。本文针对工件可恢复和不可恢复两种情形,分别给出了时间复杂性为O(ns_1... 本文主要研究两台平行机排序问题,其中一台机器上有一个固定的不可用区间。此外,生产商可以通过支付惩罚费用来拒绝工件。目标是极小化最大时间表长与惩罚费用之和。本文针对工件可恢复和不可恢复两种情形,分别给出了时间复杂性为O(ns_1P^2)和O(np_(max)s_1P^2)的伪多项式时间动态规划算法. 展开更多

关键词 排序 拒绝 一个不可用区间 动态规划

下载PDF 职称材料

同时具有学习效应和恶化效应的机器可用限制性排序问题

14

作者 韩翔凌 张淑娟 《枣庄学院学报》 2010年第5期28-35,共8页

针对单机和两台机器的平行机排序问题,建立了工件同时具有学习效应和恶化效应,机器有可用性限制的排序模型.考虑了目标函数为极小化总完工时间的单机、两台机器的同型机问题和两台机器的同类机问题.对于机器在任意时间进行维修的一般情... 针对单机和两台机器的平行机排序问题,建立了工件同时具有学习效应和恶化效应,机器有可用性限制的排序模型.考虑了目标函数为极小化总完工时间的单机、两台机器的同型机问题和两台机器的同类机问题.对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法. 展开更多

关键词 排序 可用性限制 学习效应 恶化效应 动态规划

下载PDF 职称材料

机器使用时间受限的线性恶化成组排序问题

15

作者 金霁 闻振卫 《苏州市职业大学学报》 2007年第3期82-84,共3页

讨论了单机成组加工问题,工件加工时间是开工时间的简单线性恶化函数,并假设机器在某一时间段内不能进行工件的加工,目标函数为极小化时间表长。给出了该问题的一种0-1整数规划解法。

关键词 单机 线性恶化函数 成组技术 时间表长

下载PDF 职称材料

有使用限制的两台机器排序问题的近似算法

16

作者 李刚刚 李浩 《华中师范大学学报（自然科学版）》 CAS 北大核心 2015年第1期11-13,20,共4页

研究了两台机器有使用限制的排序问题,其中一台机器在给定的一个时间段内不可用,而另一台机器一直可用,目标为最小化最大完工时间.每台机器每次至多可以加工一个工件.工件在加工过程中不可中断.对于该问题,文章给出了一个FPTAS(fully po... 研究了两台机器有使用限制的排序问题,其中一台机器在给定的一个时间段内不可用,而另一台机器一直可用,目标为最小化最大完工时间.每台机器每次至多可以加工一个工件.工件在加工过程中不可中断.对于该问题,文章给出了一个FPTAS(fully polynomial-time approximation scheme). 展开更多

关键词 排序 使用限制 算法 FPTAS

下载PDF 职称材料

单台机器有使用限制的排序问题

17

作者 李刚刚 李浩 《河南师范大学学报（自然科学版）》 CAS 北大核心 2014年第4期18-21,共4页

研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法... 研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法. 展开更多

关键词 排序 动态规划 使用限制 算法

下载PDF 职称材料

带运输时间和一个不可用约束的两台平行机排序 被引量：1

18

作者 陈伯龙 《兰州大学学报（自然科学版）》 CAS CSCD 北大核心 2009年第4期140-144,共5页

考虑了两台平行机的排序问题,其中一台机器带有一个固定的不可用约束区间,任务的加工是不可中断的,而且每一个任务带有一个运输时间,目标函数是最小化最大运输完工时间.这个问题是强NP-难的.提出一个最坏情况比是8/5的多项式时间近似算... 考虑了两台平行机的排序问题,其中一台机器带有一个固定的不可用约束区间,任务的加工是不可中断的,而且每一个任务带有一个运输时间,目标函数是最小化最大运输完工时间.这个问题是强NP-难的.提出一个最坏情况比是8/5的多项式时间近似算法,并指出这个界是紧界.同时还用动态规划方法求解该问题. 展开更多

关键词 不可用约束 运输时间 最坏情况比 近似算法 动态规划

下载PDF 职称材料