带机器准备时间的平行机在线与半在线排序 被引量：21

1

作者 谈之奕 何勇 《系统科学与数学》 CSCD 北大核心 2002年第4期414-421,共8页

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的... 本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。 展开更多

关键词 机器准备时间 平行机 半在线排序 在线排序 近似算法 最坏情况分析

原文传递

一类带机器准备时间的排序复杂性及算法 被引量：4

2

作者 陈仕平 何勇 姚恩瑜 《应用数学学报》 CSCD 北大核心 1998年第3期474-476,共3页

关键词 机器准备时间 排序 复杂性 算法

原文传递

带机器准备时间的同类机在线与半在线排序问题 被引量：7

3

作者 丁际环 曲桂东 +2 位作者 张伟 岳丽 张玉忠 《曲阜师范大学学报（自然科学版）》 CAS 2003年第3期1-5,共5页

研究带机器准备时间的m台同类机 (uniformmachines)在线和半在线排序问题 ,目标函数为极小化最大机器 (工件 )完工时间 .对于在线情形 ,证明了LS算法的最坏情况为 ρ =( 1+ 5 ) 2 ,m =2 ,1+ 2m - 2 2 ,m≥ 3 ,并且当m =2时 ,LS算法是... 研究带机器准备时间的m台同类机 (uniformmachines)在线和半在线排序问题 ,目标函数为极小化最大机器 (工件 )完工时间 .对于在线情形 ,证明了LS算法的最坏情况为 ρ =( 1+ 5 ) 2 ,m =2 ,1+ 2m - 2 2 ,m≥ 3 ,并且当m =2时 ,LS算法是最好的近似算法 ;当m =2 ,3 ,… ,6时界是紧的 ,特别地 ,当s1 =s2 =… =sm - 1 ,sm ≥ 1时 ,证明了LS算法的最坏情况界为 ρ =( 1+ 5 ) 2 ,m =2 ,3 - 4 (m + 1) ,m≥ 3 ,而且界是紧的 ;对于已知加工时间递减的半在线排序问题 ,证明了LS算法的最坏情况界为 2 - 2 (m + 1) . 展开更多

关键词 在线排序 半在线排序 机器准备时间 同类机 近似算法 最坏情况 LS算法

下载PDF 职称材料

带机器准备时间的同类机调度问题的启发式算法 被引量：6

4

作者 马英 杨善林 汤大为 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2012年第9期2022-2030,共9页

研究了带机器准备时间的同类机最大完工时间调度问题,首先证明了工件互换的四个性质.进而提出了一种启发式算法,此算法以LPT算法得到的序列作为初始解,利用互换性质重复对最大完工时间最大和最大完工时间最小的两台机器上的工件进行交换... 研究了带机器准备时间的同类机最大完工时间调度问题,首先证明了工件互换的四个性质.进而提出了一种启发式算法,此算法以LPT算法得到的序列作为初始解,利用互换性质重复对最大完工时间最大和最大完工时间最小的两台机器上的工件进行交换,以提高解的质量.实验结果证明了此算法的有效性. 展开更多

关键词 同类机调度 机器准备时间 LPT

原文传递

带准备时间的两台同类机半在线排序的近似算法 被引量：1

5

作者 华荣伟 《浙江大学学报（理学版）》 CAS CSCD 北大核心 2007年第5期515-519,共5页

研究带准备时间的两台同类机已知工件最大加工时间的半在线排序问题,分别讨论了极小化最大机器完工时间和极小化最大工件完工时间这两个目标函数.对这两个目标函数给出了竞争比为32的近似算法,并证明了不存在竞争比小于2的近似算法.

关键词 排序 同类机 半在线算法 机器准备时间 竞争比

下载PDF 职称材料

带机器准备时间的平行机ordinal排序及近似算法 被引量：1

6

作者 谈之奕 何勇 《应用数学学报》 CSCD 北大核心 2002年第2期223-229,共7页

本文研究带机器准备时间的m台平行机ordinal在线排序问题.讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法.对第一个目标;我们得到了3/2的下界和最坏情况界为2-1/m的近似算法.对第二... 本文研究带机器准备时间的m台平行机ordinal在线排序问题.讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法.对第一个目标;我们得到了3/2的下界和最坏情况界为2-1/m的近似算法.对第二个目标,我们得到了最坏情况界为m的最好近似算法.我们还对一些特殊情况进行了分析. 展开更多

关键词 机器准备时间 平行机 ordinal排序 近似算法 半在线排序 最坏情况界 排序问题

原文传递

机器带准备时间的平行机排序问题的并行阈值算法

7

作者 范静 《科学技术与工程》 2008年第7期1649-1654,共6页

针对带准备时间的最小机器完工时间最大化排序问题,结合原始阈值算法、对偶阈值算法并加以修正,提出并行层次阈值算法,证明了三台机器情况下当参数ε=1/4时,此线性时间算法的最坏情况界为3/4。这是到目前为止最坏情况界最小且时间复杂... 针对带准备时间的最小机器完工时间最大化排序问题,结合原始阈值算法、对偶阈值算法并加以修正,提出并行层次阈值算法,证明了三台机器情况下当参数ε=1/4时,此线性时间算法的最坏情况界为3/4。这是到目前为止最坏情况界最小且时间复杂性为线性时间的算法。进一步通过计算实验,表明并行阈值算法对于3台至50台机器、5至50 000个工件数量的规模下,具备很高效率。 展开更多

关键词 排序 阈值算法 最坏情况界 机器准备时间 线性时间

下载PDF 职称材料

两个带机器准备时间的半在线排序

8

作者 邵晶晶 《广西科技师范学院学报》 2017年第6期128-131,121,共5页

研究两个带机器准备时间的半在线排序算法,一个是当总加工时间已知时,工件在有准备时间的同类机上加工的半在线排序,证明了其竞争比的上下界分别为2ν和ν+1/2ν+1,都与机器加工速度有关;另一个是当最大加工时间已知时,工件在有准备时... 研究两个带机器准备时间的半在线排序算法,一个是当总加工时间已知时,工件在有准备时间的同类机上加工的半在线排序,证明了其竞争比的上下界分别为2ν和ν+1/2ν+1,都与机器加工速度有关;另一个是当最大加工时间已知时,工件在有准备时间的同型机上加工的半在线排序,证明了其竞争比为2/3. 展开更多

关键词 机器准备时间 排序 半在线算法 竞争比

下载PDF 职称材料

带有机器准备时间且允许重排的在线排序(英文)

9

作者 侯丽英 康丽英 《运筹学学报》 CSCD 2010年第3期19-30,共12页

本文中,我们考虑了带有机器准备时间且允许重排的两台平行机在线排序问题.其目标为极小化最大完工时间.我们研究了两种不同的模型,并分别给出了最好可能的算法.

关键词 运筹学 在线排序 机器准备时间 重排 竞争比

下载PDF 职称材料

高效之二：降低准备时间

10

《中国印刷》 2010年第1期62-65,共4页

从接受印件到印出合格印刷品的时间，包括各种准备和机器调整。统称为印前准备时间。现在一般的机器准备时间已经由过去的一个小时甚至数小时缩短到十几分钟，已经有了很大的提高。但对于一个小时需要更换数次印刷品来说，仍然显得太长... 从接受印件到印出合格印刷品的时间，包括各种准备和机器调整。统称为印前准备时间。现在一般的机器准备时间已经由过去的一个小时甚至数小时缩短到十几分钟，已经有了很大的提高。但对于一个小时需要更换数次印刷品来说，仍然显得太长，占用时间太多。 展开更多

关键词 机器准备时间 印刷品 小时 印件 印前

下载PDF 职称材料

带准备时间的两台同类机已知工件总加工时间的半在线排序问题的近似算法

11

作者 华荣伟 洪哲 《浙江大学学报（理学版）》 CAS CSCD 北大核心 2008年第4期395-399,共5页

主要研究带准备时间的两台同类机已知工件最大加工时间的半在线排序问题,目标函数极小化最大机器完工时间和极小化最大工件完工时间.对此问题给出了竞争比为2的近似算法,并证明了不存在竞争比小于1+32的近似算法.

关键词 排序 同类机 半在线算法 机器准备时间 竞争比

下载PDF 职称材料

带准备时间的同类机半在线问题的近似算法

12

作者 武光华 苑丽华 《菏泽学院学报》 2009年第5期1-4,共4页

研究了带机器准备时间的两台同类机已知工件最大加工时间的半在线排序问题,讨论了极小化最大工件完工时间这个目标函数,并给出了一个竞争比为分段函数的近似算法.

关键词 同类机 半在线 竞争比 机器准备时间

下载PDF 职称材料

考虑投放期、交货期和机器准备时间的平行机问题改进遗传算法

13

作者 熊禾根 孔建益 《武汉科技大学学报》 CAS 2006年第4期376-379,共4页

针对考虑工件投放期、交货期和机器准备时间的平行机问题,分别以最小化最大机器完工时间和最小化工件总延期惩罚费用为优化目标,建立相应的平行机问题模型,提出一种求解该问题的改进遗传算法。该算法中采用了基于工件和机器的多参数级... 针对考虑工件投放期、交货期和机器准备时间的平行机问题,分别以最小化最大机器完工时间和最小化工件总延期惩罚费用为优化目标,建立相应的平行机问题模型,提出一种求解该问题的改进遗传算法。该算法中采用了基于工件和机器的多参数级联编码,染色体由工件子串和机器子串连接而成;提出了机器的加工能力、加工能力指数和冗余机器集的概念及相应的初始种群生成方法;对工件子串采用部分映射交叉,而对机器子串不作交叉运算;在变异算子中,提出基于机器负荷的启发式变异算子。 展开更多

关键词 平行机问题 投放期 交货期 机器准备时间 改进遗传算法

下载PDF 职称材料