搜索结果: 1-12 共查到“数学 平行机”相关记录12条 . 查询时间(0.088 秒)
研究机器带学习效应, 目标函数为时间表长的两台平行机排序问题, 问题是NP-难的. 首先建立了求解该问题最优解的整数规划模型. 其次, 基于模拟退火算法给出了该问题的近似算法SA, 并证明了该算法依概率1 全局收敛到最优解. 最后, 通过数值模拟对所提出的算法进行了性能分析. 数值模拟结果表明, 近似算法SA可以达到最优值的99%, 准确度高, 算法较有效.
本文研究一个两阶段物流排序问题,即第一阶段工件在平行机上加工,在第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.优化的目标是使工件带权送到的时间与运输费用的总和为最小.应用动态规划及组合优化方法,分别研究``满足一致性条件''和一般情形下该问题的多项式时间近似算法,并分析算法的性能比.
本文考虑了两台平行机的排序问题, 其中一台机器带有一个固定的不可用约束区间,任务的加工是不可中断的, 而且每一个任务带有一个运输时间, 目标函数是 最小化最大运输完工时间. 这个问题是强 NP 难的. 我们提出一个最坏例子比是 8/5 的多项式时间近似算法, 并指出这个界是紧界, 同时还用动态规划方法求解该问题.
带机器准备时间的平行机排序问题
运筹学 排序 带机器准备时间 多项式时间近似方案 全多项式时间近似方案
2010/8/31
研究了带机器准备时间的$m$台平行机排序问题，设计出了一个多项式时间近似方案(PTAS),并给出了一个机器数$m$为固定常数的情形下的全多项式时间近似方案 (FPTAS).
预知工件大小上界的平行机排序问题
排序 半在线 算法设计与分析 竞争比
2010/8/31
平行机排序问题广泛出现并应用于各领域,如通讯网信道分配的负载均衡, 大型计算中的并行计算,柔性制造系统的任务编排等等.研究了预知工件大小上界的半在线平行机排序问题.考察了仅预知工件大小上界和既预知工件大小上界又预知最优目标值的两类半在线模型.基于资源分配公平性和提高服务质量的考虑,针对每类模型都分别考察了两个目标:$C_{\rm max}$(极小化机器最大负载~makespan) 和~$C_{\r...
平行机排序问题的列生成解法
排序 整数规划 列生成
2009/9/21
基于整数规划的线性松弛,探讨求解大规模带权总完工时间排序问题的列生成算法的基本原理.
然后,结合动态规划和分枝定界技术,对大规模排序问题$P||\sum{w_{j}C_{j}}$提出一类求解精确(最优)解的列生成算法.
可拆分有调整时间的平行机排序问题的一个算法
平行机排序 调整时间 最坏情况分析
2008/4/16
考虑有独立调整时间的同型号平行机排序问题，极小化最迟完工时间.产品允许拆分，同一产品被拆分后各部分可以在不同机器上同时加工.该问题是NP-hard问题.本文首先给出该问题的一个启发式算法ML，然后证明了其最坏情况估计不超过7/4-1/m(m≥2).
平行机的实时到达on-line算法下界的改进
排序 on-line算法 性能比
2008/4/16
本文考虑了平行机实时到达的在线问题.模型中，工件是陆续到达的，工件的个数、到达时间是事先未知的，而且只有当工件到达，才知其加工时间，目标是使所有工件都加工完的时间达到最小.Chen与Vestjens(1996年)证明了该在线问题不存在性能比小于1.3473的on-line算法.本文将此界改进为(5-)/2.
带机器准备时间的平行机ordinal排序及近似算法
半在线排序 近似算法 最坏情况界
2007/12/11
本文研究带机器准备时间的$\ssize m$台平行机ordinal在线排序问题．讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法．对第一个目标, 我们得到了$\ssize 3/2$的下界和最坏情况界为$\ssize 2-1/m$的近似算法．对第二个目标, 我们得到了最坏情况界为$\ssize m$的最好近似算法．我们还对一些特殊情况进行了分析.
平行机中关于关于同类机近似算法的研究
排序问题 同类机 近似算法 半定松弛
2007/12/11
我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和$\s...
两台平行机的实时到达在线排序
排序 在线算法 近似比
2007/12/11
该文考虑一类新的在线平行机排序模型——实时到达在线问题.该模型中,工件是陆续到达的.工件的个数及到达时间是事先未知的,而且只有当工件到达,才知其加工时间,所求目标是使所有工件都加工完的时间达到最小.对两台平行机的情形,Chen与Vestjens给出了近似比为3/2的在线LPT算法,并证明不存在近似比小于(5-〖KF(〗5〖KF)〗)/2的算法.利用黄金分割数设计了一个新的算法,其近似比不超过(18...