共查询到20条相似文献,搜索用时 0 毫秒
1.
讨论任务加工不可中断,处理机为变速机的排序问题Rm,ai||∑Cj.通过改变加工时间矩阵,将其转化为经典排序问题求解 相似文献
2.
3.
4.
本文给出处理机具有不同的开始加工时间的Q,ai|pmitn|Cmax排序问题的一个最优算法,算法的复杂性为O(m^2n^2)。 相似文献
5.
讨论任务的加工是不可中断,处理机是恒速机且处理机具有准备时间的排序问题,目标函数是极小化最大完工时间.对于2台处理机的情况,已经有了一个与处理机加工速度有关的排序的界.研究了对于m(m≥2)台处理机的一种特殊情况,给出了一个与处理机加工速度有关的算法的界. 相似文献
6.
王吉波 《大连理工大学学报》2013,53(6):930-936
具有学习效应的任务的加工时间和带有准备时间的任务问题是排序论中的重要研究内容,它们对任务的完工时间有重要影响.研究了具有学习效应且带有准备时间的任务单机排序问题,其中学习效应指的是任务的实际加工时间是该已经排好的任务对数加工时间的递减函数,目标函数为最小化总完工时间.这个问题是NP-难问题.用分支定界法给出了此问题的最优解,为了提高分支定界法的运行效率,同时给出了一个启发式算法、几个优势性质和两个下界.计算结果表明分支定界法和启发式算法求解此问题非常有效. 相似文献
7.
讨论了带准备时间和强制工期的单机排序问题. 在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小. 由于工件不允许延迟,首先考虑了问题的可行性. 通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法. 对于可行问题,给出了一个算法在多项式时间内获得最优排序. 相似文献
8.
9.
雷晓强 《云南大学学报(自然科学版)》2004,26(B07):12-15
设有p台处理机要加工n项任务,当每项任务t在时刻i和处理机j上被开始执行时,都有一个不可间断的加工时间l(t,i,j)∈{k1,k2},我们的目标是要找一个可行方案σ,使得总的完工时间最短.该问题是NP-完备的,本文给出该问题的一个近似算法。 相似文献
10.
考虑可拒绝排序中生产与配送的集成问题.有一个制造商和多个客户,不同的客户订购不同种类的工件.机器在加工不同种类的工件前要有一个准备时间.对于客户的工件制造商可以选择接受或拒绝加工,但当工件被拒绝时制造商需要支付相应的拒绝费用.每个工件有自己的工期并且生产完成后需要配送到相应的客户处,每一批配送需要花费一定的时间和费用.该文研究了排序理论中几个主要的目标函数,给出了相应的动态规划算法并分析了算法的复杂性. 相似文献
11.
12.
讨论任务具有相关调整时间的排序问题,首先把[2]中关于LPT算法的结论推广到一般算法,然后又进一步将新的结论推广到处理机为恒速机的情况。 相似文献
13.
带机器准备时间的同类机在线与半在线排序问题 总被引:4,自引:1,他引:4
研究带机器准备时间的m台同类机(uniform machines)在线和半在线排序问题,目标函数为极小化最大机器(工件)完工时间。对于在线情形,证明了LS算法的最坏情况为ρ={(1 √5)/2,m=2,1 √2m-2/2,m≥3,并且当m=2,LS算法是最好的近似算法;当m=2,3,…,6时界是紧的,特别地,当s1=s2=…=sm-1,sm≥l时,证明了LS算法的最坏情况界为ρ={(1 √5)/2,m=2,3-4/m 1,m≥3,而且界是紧的;对于已知加工时间递减的半在线排序问题,证明了LS算法的最坏情况界为2—2/(m 1)。 相似文献
14.
赵玉芳 《辽宁大学学报(自然科学版)》1998,25(4):309-311,315
本文对n个任务,2台同类处理机的排序问题Q2∥Cmax进行讨论,提出一个算法,用该算法得到的排序表长的界是2b+1/2bM,算法的复杂性为O(nlogn)。 相似文献
15.
针对带准备时间的最小机器完工时间最大化排序问题,结合原始阈值算法、对偶阈值算法并加以修正,提出并行层次阈值算法,证明了三台机器情况下当参数ε=1/4时,此线性时间算法的最坏情况界为3/4.这是到目前为止最坏情况界最小且时间复杂性为线性时间的算法.进一步通过计算实验,表明并行阈值算法对于3台至50台机器、5至50 000个工件数量的规模下,具备很高效率. 相似文献
16.
讨论了单机分批排序问题中目标是极小化加权总完工时间的问题.对于所有工件的加工时间都相等的情况,分别对常数个到达时间和任意个到达时间的情况给出了两个最优算法,并给出了其算法复杂性. 相似文献
17.
18.
讨论任务具有相关调整时间的排序问题 .首先把 [2 ]中关于LPT算法的结论推广到一般算法 ,然后又进一步将新的结论推广到处理机为恒速机的情况 . 相似文献
19.
20.
讨论了工件加工时间和排列中位置相关的单机排序问题.对工件加工时间和位置相关的两个线性模型Pi(v)=ai-biv和pi(v)=aiv^-b进行了讨论,目标函数是带折扣的加权总完工时间,并且对工件加工时间与给定权值之间具有一致关系的某些情况给出了最优算法。 相似文献