共查询到20条相似文献,搜索用时 93 毫秒
1.
2.
带约束的平行机排序的一个近似算法 总被引:3,自引:0,他引:3
何勇 《高校应用数学学报(A辑)》2001,16(1):114-118
讨论有资源约束和有机器准备时间的平行机排序问题,资源约束为每个机器至多可加工k个工件,在极小化makespan的上给出了一个匹配算法,证明其最坏情况最紧界是2-m^-1,并进一步给出了它的两个带参数的最坏情况界。 相似文献
3.
徐淼鑫 《应用数学与计算数学学报》1995,9(2):73-79
本文讨论一类工序连续的生产排序,由于约束条件的特殊;通常启发式垢优先规则较难应用,故用一种“探索排序路线”的方法来处理问题。 相似文献
4.
由于约束单机排序问题是经典装箱问题的一种推广并且同经典装箱问题有一些相同的特征。本文主要讨论了经典装箱问题的一些启发式算法在在线约束单机排序问题上的推广和最坏界估计。 相似文献
5.
孙联中.油田井下作业质量的工序等级排序控制管理本文对油田作业施工中的质量后果进行分析,建立排序模型,排序后建立与危害相关的工序等级排序进行控制管理,提高质量控制效果. 相似文献
6.
讨论了任务具有优先约束的可中断不完全恒速机排序问题,若处理机具有不同开始加工时间的可中断排序问题存在最优算法,则相应的不完全恒速机排序问题也有最优算法。 相似文献
7.
本文研究了一种新的排序问题:带“广义偏序”约束的folw-shpo排序问题。如工件Jj与工件Jk之间有广义偏序,则Jj→Jk,且Jj的完工时间与Jk的开工时间的间隔洋小于ljk和不大于ujk,0≤ljk≤ujk。问题的目标函数是最大完工时间。 相似文献
8.
一类加工时间依赖资源的单机排序问题 总被引:1,自引:0,他引:1
讨论了一类有准备时间且任务的加工时间依赖资源的单机排序问题.目标函数为最大完工时间与分配给各任务资源消耗量的加权线性组合.给出了问题的若干相关性质.在此基础上,对于任务之间无优先约束和有任意优先约束的情况.分别给出了最优排列算法和最优资源分配方法.并用数值例子作了说明. 相似文献
9.
带序约束的恒同机分批作业排序问题 总被引:3,自引:0,他引:3
研究一类由林诒勋教授提出的带序约束的恒同机分批作业排序问题,证明了这类排序问题均是NP—困难的,给出了其执行比为32的一种启发式算法。 相似文献
10.
一类带机器准备时间的排序复杂性及算法 总被引:3,自引:0,他引:3
1引言文[2-4]中考虑了如下定义的一个排序模型:m台同型机器加工n个工件,每个工件在零时刻到达,第i个工件需加工时间pi,而各机器有各自的准备时间Tj≥0,怎样安排工件加工顺序,使机器总完工时间(makespan)尽可能早.这是一个强NP-完全问题.本文考虑增加这样一个约束,即每 相似文献
11.
文中讨论了任务具有优先约束的不完全同速机排序问题,对问题Pm|brkdwn,intree,pj=1|Cmax给出了最优算法,对问题Pm|brkdwn,prec,pj=1|Cmax给出了界为2-2m的算法。 相似文献
12.
一类资源约束排序问题 总被引:2,自引:2,他引:0
引入与研究 1| pj=fj( uj) ,∑uj U| ∑ ( wj Cj+ uj)型资源约束排序问题 .针对系统中加工顺序确定的情况 ,给出三个寻求最优资源分配的算法 ;就 fj=f和 fj=bj+ g,wj=w等情况研究系统的最优排序 . 相似文献
13.
处理机具有不同开始加工时间的可中断排序问题 总被引:6,自引:0,他引:6
本文对处理机具有的不同开始加工时间的可中断排序问题进行讨论,得到下面结论:若处理机具有相同开始加工时间的可中断排序问题存在最优排序算法,则相应的处理机具有不同开始加工时间的可中断排序问题也存在最优排序算法。 相似文献
14.
本文在分析了现有的网络资源分配的几个优化准则和在工序排序过程中各种因素对工期产生影响的基础上,基于灰色系统理论,提出了以关联度为工序优先级的多资源网络计划分配问题的优化准则,并通过算例和与其它优化准则对比分析,说明依据该准则可使网络计划满足多资源约束条件,并使工期延长最少 相似文献
15.
研究带凸资源和恶化效应的单机窗口指派排序问题,其中窗口指的是松弛窗口,凸资源和恶化效应指的是工件的实际加工时间是其开始加工时间的线性函数,是其资源消耗量的凸函数。目标是确定工件的加工顺序,资源分配量以及窗口的开始加工时间和长度使其在总资源消耗费用(与窗口有关的排序费用)有上界限制的条件下,极小化与窗口有关的排序费用(总资源消耗费用)。获得了求解上述问题的最优算法,证明了该问题是多项式时间可解的。 相似文献
16.
讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法. 相似文献
17.
有区间约束单机延误排序问题 总被引:1,自引:0,他引:1
研究一类推广的从准备时间ri到交工期di的多重r/d区间排序问题——有区间约束单机延误排序问题。就该问题的一般情形而言证明了它是NP—困难的,对问题的特殊情形证明了它是多项式时间可解的。 相似文献
18.
19.