带并行工件的平行机排序问题的一个新近似算法 被引量：6

1

作者 沈灏 杨启帆 何勇 《浙江大学学报（理学版）》 CAS CSCD 2004年第2期138-142,共5页

讨论并行工件平行机排序问题,目标为极小化所有工件的总完工时间.这是一个强NP-难的问题.通过对(0,1]区间划分的深入研究,提出了一个多项式时间的近似算法,其渐近性能比的上界为1.6,下界为1.5.该算法比LI(1999)中提出的算法的渐近性能... 讨论并行工件平行机排序问题,目标为极小化所有工件的总完工时间.这是一个强NP-难的问题.通过对(0,1]区间划分的深入研究,提出了一个多项式时间的近似算法,其渐近性能比的上界为1.6,下界为1.5.该算法比LI(1999)中提出的算法的渐近性能比明显地小. 展开更多

关键词 近似算法 平行机排序 渐近性能比 并行工件

下载PDF 职称材料

有两个服务等级的平行机排序问题 被引量：4

2

作者 周萍 蒋义伟 何勇 《高校应用数学学报（A辑）》 CSCD 北大核心 2007年第3期275-284,共10页

对有两个服务等级的平行机排序问题的m台机情形,证明了修正的MF算法的最坏情况界不超过4/3＋（1/2）^k,其中k是算法中预先给定的迭代次数.而已有的算法仅为2-1/m-1,从而大大改进了已有文献中的结果.

关键词 平行机排序 服务等级 近似算法 最坏情况界

下载PDF 职称材料

带约束的平行机排序问题 被引量：4

3

作者 樊保强 董广龙 +1 位作者 曲桂东 张玉忠 《曲阜师范大学学报（自然科学版）》 CAS 2003年第4期11-14,共4页

讨论了带资源约束和机器准备时间的平行机排序问题 ,资源约束是指每个机器最多加工k个工件 .首先对一般情况下的同型机的PLPT排序进行了讨论 ;并首次对同类机排序进行了研究 ,给出了一个FLPT近似算法 ,同时对m =2时证明了PLPT排序的最... 讨论了带资源约束和机器准备时间的平行机排序问题 ,资源约束是指每个机器最多加工k个工件 .首先对一般情况下的同型机的PLPT排序进行了讨论 ;并首次对同类机排序进行了研究 ,给出了一个FLPT近似算法 ,同时对m =2时证明了PLPT排序的最坏情况紧界是 2 . 展开更多

关键词 平行机排序 资源约束 PLPT排序 约束排序 最坏性能比 FLPT近似算法

下载PDF 职称材料

工件带安装时间平行机排序问题的列生成算法 被引量：1

4

作者 樊保强 唐国春 《同济大学学报（自然科学版）》 EI CAS CSCD 北大核心 2006年第5期680-683,693,共5页

研究了工件带与加工次序有关的安装时间的平行机排序问题,给出它的整数规划模型,并结合动态规划和分支定界方法,给出它的列生成算法.通过试验表明:算法对中等规模的问题是有效的,它可以计算到10台机器和60个工件甚至含有更多大工件的大... 研究了工件带与加工次序有关的安装时间的平行机排序问题,给出它的整数规划模型,并结合动态规划和分支定界方法,给出它的列生成算法.通过试验表明:算法对中等规模的问题是有效的,它可以计算到10台机器和60个工件甚至含有更多大工件的大规模问题. 展开更多

关键词 平行机排序 列生成 动态规划 分支定界

下载PDF 职称材料

带准备时间的平行机排序的LPT算法 被引量：1

5

作者 何勇 《浙江大学学报（自然科学版）》 CSCD 1996年第3期333-339,共7页

本文考虑带准备时间的平行机排序问题，讨论在使最早机器完工时间达到最大目标下的优化问题．这是ＮＰ－ｈａｒｄ问题，本文证明ＬＰＴ排序解至少是最优解的倍．

关键词 平行机排序 准备时间 LPT算法

下载PDF 职称材料

可拆分有调整时间的平行机排序问题的一个算法

6

作者 邢文训 张家伟 《高校应用数学学报（A辑）》 CSCD 北大核心 1999年第4期480-484,共5页

考虑有独立调整时间的同型号平行机排序问题，极小化最迟完工时间．产品允许拆分，同一产品被拆分后各部分可以在不同机器上同时加工．该问题是 Ｎ Ｐｈａｒｄ 问题．本文首先给出该问题的一个启发式算法 Ｍ Ｌ，然后证明了其最坏情... 考虑有独立调整时间的同型号平行机排序问题，极小化最迟完工时间．产品允许拆分，同一产品被拆分后各部分可以在不同机器上同时加工．该问题是 Ｎ Ｐｈａｒｄ 问题．本文首先给出该问题的一个启发式算法 Ｍ Ｌ，然后证明了其最坏情况估计不超过７／４－ １／ｍ （ｍ ≥２） 展开更多

关键词 平行机排序 调整时间 最迟完工时间 排序 算法

下载PDF 职称材料

极大化提前完工总量平行机排序问题的LPT算法

7

作者 周萍 季敏 蒋义伟 《运筹学学报》 CSCD 北大核心 2022年第3期151-156,共6页

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断,目标是极大化所有工件的提前完工量,即在交货期前所加工工件(或部分)的总加工时长。由于该问题是NP-难问题,本文应用经典LPT算法来解决该问题。我们证明了LPT算法... 研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断,目标是极大化所有工件的提前完工量,即在交货期前所加工工件(或部分)的总加工时长。由于该问题是NP-难问题,本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为15/13,并给出实例说明最坏情况界的下界为27/25。 展开更多

关键词 平行机排序 LPT算法 最坏情况界 提前完工总量

下载PDF 职称材料

工件带到达时间和服务器的平行机排序问题复杂性和启发式算法

8

作者 时凌 《湖北民族学院学报（自然科学版）》 CAS 2004年第3期15-18,共4页

研究带到达时间和单服务器的平行机排序问题,工件在加工之前均有一定的安装时间,且所有安装时间均由单服务器来完成.证明在只有两台平行机的情况下,带到达时间和单服务器的平行机排序问题是强NP-困难的,对于有m台平行机的情况,给出一种... 研究带到达时间和单服务器的平行机排序问题,工件在加工之前均有一定的安装时间,且所有安装时间均由单服务器来完成.证明在只有两台平行机的情况下,带到达时间和单服务器的平行机排序问题是强NP-困难的,对于有m台平行机的情况,给出一种改进的启发式算法,并证明该算法的紧界为2. 展开更多

关键词 平行机排序问题 到达时间 服务器 复杂性 启发式算法

下载PDF 职称材料

已知工件最大加工时间的平行机排序问题 被引量：3

9

作者 吴用 黄宜坤 杨启帆 《浙江大学学报（理学版）》 CAS CSCD 北大核心 2008年第1期23-26,共4页

研究了已知工件最大加工时间,目标为极小化最大机器负载的半在线平行机排序问题.证明了对于一般的m(>6)台机器,任意的半在线算法的竞争比至少是(33+3)/6.同时还设计了一个半在线算法,算法的竞争比为2-1/(m-1).

关键词 平行机排序 竞争比 半在线

下载PDF 职称材料

平行机排序邻域搜索算法设计 被引量：3

10

作者 欧锦文 施保昌 《计算机工程与应用》 CSCD 北大核心 2003年第18期103-104,110,共3页

为了提高平行机调度的精度,提出了邻域搜索算法。数值试验表明了该算法能找到最优解或跟最优解非常接近的近似解。交换下降算法能有效地应用于多种平行机排序问题。

关键词 平行机排序 邻域搜索算法

下载PDF 职称材料

可能产生中断且考虑运输的两台平行机排序问题

11

作者 魏小兰 沈灏 叶赛英 《浙江大学学报（理学版）》 CAS CSCD 北大核心 2009年第2期144-146,152,共4页

讨论两台平行机排序问题.有一台机器在某一个特定时刻可能产生中断,中断持续时间长短满足相应的概率,且工件转移到另一台机器上加工需要考虑运输时间.证明该问题是NP-困难的,设计一个复杂性为O(n3(TP)4)的动态规划算法,调整机器原有的... 讨论两台平行机排序问题.有一台机器在某一个特定时刻可能产生中断,中断持续时间长短满足相应的概率,且工件转移到另一台机器上加工需要考虑运输时间.证明该问题是NP-困难的,设计一个复杂性为O(n3(TP)4)的动态规划算法,调整机器原有的工件排序,使得目标函数为带权重的总完工时间期望值最小.其中,n是工件的个数,TP是所有工件的加工时间之和. 展开更多

关键词 动态规划 平行机排序 中断 运输

下载PDF 职称材料

带有不可用区间中断可恢复的平行机排序问题

12

作者 张琦 罗成新 《沈阳师范大学学报（自然科学版）》 CAS 2014年第4期466-470,共5页

讨论带有不可用区间且工件中断可恢复的两台平行机排序问题。其中一台机器带有不可用区间,在不可用区间内不能加工工件。工件在加工时被不可用区间中断后,可以在不可用区间之后继续加工。目标是最小化加权总完工时间。这个问题是一般定... 讨论带有不可用区间且工件中断可恢复的两台平行机排序问题。其中一台机器带有不可用区间,在不可用区间内不能加工工件。工件在加工时被不可用区间中断后,可以在不可用区间之后继续加工。目标是最小化加权总完工时间。这个问题是一般定义下NP-难的,因此需要寻找满足指定精确度的近似解。首先给出全多项式近似方案的定义,其次提出了一个动态规划的算法,最后利用划分程序的方法得到了一个全多项式近似方案(FPTAS),该近似方案的时间复杂性为O(n5 L5/ε4),其中:n为输入工件的个数;L为输入规模;ε>0为误差精度。 展开更多

关键词 平行机排序 不可用区间 中断可恢复 NP-难 全多项式近似方案

下载PDF 职称材料

关于平行机排序问题的两点注记

13

作者 陈志龙 赵小平 《运筹学杂志》 CSCD 1992年第1期71-72,共2页

本文考虑了有完工约束的平行机排序问题,证明了问题 pm|T|∑c_i是 NP-完全的,而对问题 pm|T,[_i≡p|∑w_ic_i 提出 O(n^2)的算法,并证明其最优性.将 n 个互相独立的工件(工件集 N={1,2,…,n))放在 m 台等速率平行机(机器M={M_i,…,M_m}... 本文考虑了有完工约束的平行机排序问题,证明了问题 pm|T|∑c_i是 NP-完全的,而对问题 pm|T,[_i≡p|∑w_ic_i 提出 O(n^2)的算法,并证明其最优性.将 n 个互相独立的工件(工件集 N={1,2,…,n))放在 m 台等速率平行机(机器M={M_i,…,M_m})上加工.已知每个工件必须且仅须在一台机器上加工一次,并且加工时不允许中断.工件 i(i∈N)在不同机器上加工时间不变,设为 p_i,罚权 w_i 也与机器无关,p_i 和 w_i 皆为非负实数.我们将多台机器加工工件的一个安排称为一个时间表.当时间表π确定后,记工件 i 的完工时间为 展开更多

关键词 平行机排序 排序

下载PDF 职称材料

一类带核的平行机排序问题

14

作者 鲁海燕 《数学研究》 CSCD 2000年第1期77-84,共8页

研究了一类工件具有相似加工时间的带核的平行机排序问题 ,运用 L PT算法求解 ,得到 L PT算法界的精确估计并对问题的某些情形 ,给出了界紧的例子 .

关键词 平行机排序 LPT算法 相似性 相似加工时间 工件

下载PDF 职称材料

带有装卸服务器的三台平行机排序问题的LS算法

15

作者 马春磊 胡觉亮 蒋义伟 《浙江理工大学学报（自然科学版）》 2019年第1期122-126,共5页

针对一个装载服务器和一个卸载服务器的情形,研究三台平行机上的排序问题。每个工件在加工前需要由装载服务器安装到机器上,加工结束后由卸载服务器进行卸载。装载和卸载时间均为单位时间,目标是极小化最大完工时间。该问题是NP-难问题... 针对一个装载服务器和一个卸载服务器的情形,研究三台平行机上的排序问题。每个工件在加工前需要由装载服务器安装到机器上,加工结束后由卸载服务器进行卸载。装载和卸载时间均为单位时间,目标是极小化最大完工时间。该问题是NP-难问题,因此采用经典的List scheduling(LS)算法进行求解。通过引入块的概念对LS排序的结构进行分析,进而证明了LS算法的最坏情况界至多为17/9。 展开更多

关键词 平行机排序 服务器 最坏情况界 MAKESPAN LS算法

原文传递

机器和工人都有加工资质约束的平行机排序问题研究

16

作者 赵晓成 李大刚 《运筹学学报》 CSCD 北大核心 2018年第3期99-108,共10页

研究一类新型的平行机排序问题,即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下,如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_(max).将研究工件加工时间均为单位时间的情况,通过建立网络流模型以及采... 研究一类新型的平行机排序问题,即在机器和工人都是必需的加工资源并且都有加工资质约束的情况下,如何在一组平行机上进行工件排序(或称调度)以最小化时间表长C_(max).将研究工件加工时间均为单位时间的情况,通过建立网络流模型以及采用二分搜索技术,可以在多项式时间内精确地求解上述问题,算法复杂度为O(n^3logn).同时提供了一种基于双重动态柔性选择(DDFS)策略的启发式算法,可以获得较好的排序效果,算法复杂度为O(n^2). 展开更多

关键词 平行机排序 加工资质约束 时间表长 单位时间

下载PDF 职称材料

具有树和路约束的平行机排序问题

17

作者 程佳乐 李伟东 《计算机工程与科学》 CSCD 北大核心 2018年第12期2273-2279,共7页

考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得... 考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论:在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。 展开更多

关键词 平行机排序 K-树 最短路径树 最短路 近似算法

下载PDF 职称材料

加工时间可控和简单线性增长的平行机排序 被引量：3

18

作者 周伟刚 高成修 黄凯 《应用数学学报》 CSCD 北大核心 2010年第4期741-749,共9页

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递... 本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法. 展开更多

关键词 平行机排序 可控的加工时间 恶化的加工时间 0-1非线性整数规划 贪婪算法

原文传递

基于最优解下限的单工序平行机排序启发式算法 被引量：1

19

作者 朴惠淑 贾春玉 常留贤 《工业工程与管理》 CSSCI 北大核心 2015年第2期62-67,共6页

针对单工序平行机排序LPT方法计算步骤多等问题,提出了一种适用于中小企业现场排序的最优解下限截取启发式算法。传统平行机排序最优解下限表达式存在因偏离最优解过大而难以引导排序走向最优的缺陷,改进后的下限表达式更加接近于最优... 针对单工序平行机排序LPT方法计算步骤多等问题,提出了一种适用于中小企业现场排序的最优解下限截取启发式算法。传统平行机排序最优解下限表达式存在因偏离最优解过大而难以引导排序走向最优的缺陷,改进后的下限表达式更加接近于最优解。从计算步骤多少和偏离最优解下限的最大偏差率两个角度,比较分析了最优解下限截取法与LPT法的特点。经实验数据验证,得出零件数与平行机数之比非整除且满足一定条件时,简单易行的截取法更优于LPT法的结论。 展开更多

关键词 平行机排序 最优解下限 LPT法 截取法

下载PDF 职称材料

平行机器的分批排序问题 被引量：2

20

作者 林诒勋 原晋江 周贤伟 《河南科学》 1992年第4期323-330,共8页

本文研究一类具有分批约束的平行机排序问题.在恒同机情形导出Greedy算法,在m=2情形建立了匹配算法,在两台一致机器情形讨论了2-交换算法,并得到若干计算复杂性结果。

关键词 排序问题 平行机排序 设备

下载PDF 职称材料