论文研究-基于改进DP算法的具有优先序的变速机最小化成本调度.pdf,  研究了工件具有任意标准优先序、一台机器在同一时间只可加工一个工件、最小化工件加工成本与机器使用成本之和的变速机调度问题.为该问题建立了DP模型,通过启发式规则和常规动态规划方法相结合、引入工件完工时间界限并保存每一步函数值,得到改进的DP算法,数值实验显示该算法具有较强的寻优能力和稳定性.
278 系统工程理论与实践 第31卷 目标方程(1)为最小化完成所有工件的总成本括号里第一项为完成工件i的时间成本,第二项为完成工件 使用机器的成本,约東(2)、(3)分别为优先级约束和开始时间约東.一台机器在同一时间只可加工一个工 件的约束已包含在方程(1)中 3动态规划(DP)模型 下面把目标约束方程转化为DP模型求解.对于任何非零正整数x=1,2,3,…,ⅵ∈N,Ⅶ∈M,令 +∞,ifx<t Q(x)+ a,a,ifx≥t, x,表示工件i在机器t上于x时刻完成加工的成本 我们在原优先序最后增加一个虚拟工件m+1,令其在各机器上的加工时间为0,其先驱工件集合为原优 先序中没有后继工件的工件集合,则日标约束方程方程等价于如下方程 N+1 mIn TC u∈M2 服从约束(2)因为约束(3)已经在(4中考虑了,所以此时不用考虑 令(x)为到x时刻完成乃2中所有工件的最小成本.如果f(m)不存在,就令 令为存在∫(x)时完成工件i的最短时问,u为存在f(x)时对应于c的加工工件i的机器.现在 有两种情况 如果c<m,有f(x)=f(x-1) 如果C=x,由式(2)得,对于k∈P,有≤c-t,=x-t,因为B2={}u( Jkep Bk),以及 ∈M2,所以有:f(x)= min Jwi+fam-ta)当P=0,有∑f(x-t)=0 u∈M k∈P k∈P 无论哪种情况,可以合并为如下递归方程: fi(r)=min fi(c-1) min w ∈MI ∑(n-t,)},k∈P k∈P 边界条件为(6).令虚拟工件n+1的最晚完L时间=∑m1(maxt),则+1(p)为调度问题的 最优解 4DP算法及计算复杂性分析 虽然上述DP模型可求得问题E的最优解,但不能在多项式时间内完成,实际应用价值不大,所以本文 采用改进的DP算法(简称DP算法)来求解问题E 41算法描述 stcp1把η个工件按其前任工件个数非减的顺序排列,如果前任工件数相等,则按工件最小加工时间 非减的顺序排列,末尾添加虚拟工件7+1,最后排列为{s1,S2,…,Sn,…,Sn,Sn+1},s为工件标号,Sn+1 7+1.令C为工件S完工时间下界,C为工件S完工时间上界,具体在42节阐述 Sep2令v=1到 ①jn(x)=+∞0(0≤x<Cen); ②令x=C。"到C (a)fsn(x)-f6(x-1); (b)y-mn|u;+∑f U∈Ma2 e,k(x-ts,n),k∈P (c)如果y<f,(x),令∫。,(x)=; (d)保存∫。n(x),工件s的开工时间st、完工时间et,以及工件s指派的机器u. Step3fn+1(C+1)即为目标函数值 第2期 柳春锋,等:基于改进DP算法的具有优先序的变速机最小化成本调度 279 42算法说明 在Step1中,我们首先把m个工件按其前任工件个数非减的顺序排列是基于以下考虑,因为每个工件 先驱工件的前任工件个数小于该工件的前任工件个数,所以按此排列必使每个工件的先驱工件排在该工件之 前.因此当我们计算工件sυ的函数∫s时,我们已经算出工件s的先驱工件k的函数fk.另外,引入启发 式规则,当前任工件数相等时,按工件最小加工时间非减的顺序排列,可减小每个工件对后续工件成本的影 响 在Ste2-②中引入工件完工时间界限,降低了计算复杂性.界限确定如下:1)工件完工时间下界.如 果把约束“一台机器在同一时间只可加工一个工件”松弛为“一台机器在同一时间可加工多个工件”,可得到 以下结论:令没有先驱的工件s的最早开工时间r8=0,最早完工时间为C8= min ts;对于其他工件 s(有先驱工件)的最早开工时间m=x(m+mnt),最早完工时间为C=re+mint,m max(n+mnt1u)+ min ts,a.C代表工件S完工时间下界2)工件完工时间上界考虑到如果每个 工件的完工时间成本远小于使用各机器的成本,且各机器的使用成本差异很大,可能出现所有工件都依次使 用同一台机器加工(每个工件使用该机器的加工时间都为最大)而能使总成本最小.因此工件。完工时间 上界为C-∑=1 max ts, 在Step2-②-(d)中,保存每个函数值fsn(x),使得该算法能在多项式时间内完成 43计算复杂性分析 1)时间复杂度 对于每个工件s来说f的时间复杂度为O(∑m=cM).所以总的时问复杂度为 ),远小于常规动态规划算法指数次方的复杂度 2)空间复杂度 我们必须存储每个∫s()的值,存储每个工件的∫的空间复杂度为O(C8-C),所以总的空间复 杂度为O∑+(C 表1算例计算过程和结果 C st* et 19 1 26 3,26 51 43 104 5 42 2 [4,42] 106 4 6 51 4,51 6 5 153 5 3 5 66 79] 402 10.66 5 56 [79 711 10,66 10 4.4算例 为测试DP算法的正确性,我们给出如下算例:有8个工件,5台机器,工件加工具有优先序,工件9为 虚拟工件(见图1),图中数字表示工件标号;工件完工的时间成本Q(c)=2c;在单位时间段使用机器 的成本ann=10+x;加工时甸矩阵T为9×5矩阵(见图2),ml[u表示工件i在机器u上加工的时间 系统工程理论与实践 第31卷 工件按Step1排序后排列为{2,4,1,3,5,8,6,7,9}.计算过程和结果见表1,表中st*和et*分别表示工 件s在x等于所属区间下界时的开工时间和完工时间 f=1,计算f2(x)其中当x∈[1.9时,f2(x)-33,工件2在x=1时的开工时间为0、完工时间为 1,指派机器3 当υ=2,计算f4(x).其中当x∈1,17时,f4(x)=23,工件4在x=1时的开工时间为0、完工时间 为1,指派机器2 当υ=3,计算f1(∞).其中当x=2时,f1(x)=+∝,说明工件2不可能在时刻x=2时完成;当 T∈B3,26]时,f1(m)=51.工件1在T=3时的开工时间为1、完工时间为3,指派机器2.同理,计算所有工 件 计算结果的DP算法目标函数值为684.调度情况绘制成甘特图(见图3) 工件标号 所有方框内数字 机器标号 42894 4 6913 57264 81654 T=78391 88292 2 65635 87654321 867 00000 2 图1工件加工优先序图 T>时间 图2加工时间矩阵 图工件加工调度甘特图 5数值实验及数据分析 首先确定问题E的下界.把问题E中的条件“一台机器在同一时间只可加工一个工件”松弛为“一台 机器在同一时间可加工多个工件”,其余不变,松弛后的问题为问题E可以把DP算法的Step2-②-(b)更 改为y-minn+∑f(x-ts,),k∈P,其余不变,得到间题E’的精确算法,其最优解即为问题 ∈M k∈P3 E的下界.显然,问题E的下界必小于或等于其最优值 为评介DP算法的性能,我们使用四个影响因子,包括机器数(m)、工件数(m)、加工时间(t;,)和优先 序图密度(D) 为检验变量m和m的影响,选择4个不同的m值(m=5,10,15,20),以及4个不同的m值(n=20,30,40,50) 为检验变量t,的影响,选择4个不同的t;,的分布,包括t,~DU[1,10、t,a~DU[1,20、t,~ DU[1,30、t,~DU1,40,这里nU,b代表从a到b的均匀分布 为检验变量D的影响,我们定义,有工件、j,Pr为概率, D=优先序图密度=Pr{存在arc(,y),即是j的前任工件|l≤t<y≤m} P3=Pr{在 arc_immediate(,),即是的先驱工件} 根据Ha和 Posner的证明,当D∈(0,1)时,有 P D(1-D)--1 -D[1-(1-D) 因此,如果已知优先序图密度D,可计算存在 arc immediate(,)的概卒P我们从0,1均匀分布中产生 个随机数rx,如果P2>T;则优先序图中存在arc- immediate(,).D反映了优先序图中工件间优先关 系的强弱,D越大,优先关系越强(即存在优先关系的概率越大),反之,优先关系越弱(即存在优先关系的概 率越小).极端情况,当D=0时,工件间无优先关系,当D=1时,优先关系为链式类型.显然当D越大时, 第2期 柳春锋,等:基于改进DP算法的具有优先序的变速机最小化成本调度 281 问题E的下界离其最优值越近,所以本文选取3个较大的D值(D=0.7,0.8.0.9)来检验DP算法的计算 性能 我们仍假设工件完工的时间成本Q(c)=2c;在单位时间段使用机器u的成本an,=10u+x 下面进行两组实验.第一组实验假定D=0.8、t,~DU[1,10,观察不同机器数和工件数的DP算法 性能(见表2);第二组实验假定m=5、m=20,观察不同工件加工时间分布和优先序图密度的DP算法性 (见表3).该算法在VC++6.0编译伓境下用C++语言实现.实验环境为: Intel(R) Pentium(R)4、CPU 240GHz、内存496MB、操作系统 Microsoft windows XP sp3 表2和表3中符号定义如下:gqp值为gqp=(C-LB)/LB·100,其中TC为DP算法的目标 函数值、LB为问题E的下界,由于呵题E的下界必小于或等于其最优值,因此DP算法目标函数值相对 于最优解的误差程度不会大于gωp.另外,对于表格中每个相同间题情形,进行10次不同随机数据实验, AVE、MIN、MAX分别对应它们的平均值、最小值和最大值.为显示DP算法中Step2-②引入工件完工时 间界限的效果,定义未引入此界限的算法为DP算法(即采用DP模型中每个工件的=1到up).cm_DP 表示DP算法的CPU时间,c_DP*表示DP*算法的CPU时间, cpu Decrease表示DP算法比DP算 法的CPU时间降幅程度即cpu- Decrease=( CPU_DP*-cDP)/cp_DP*100 由表2可以看出.当优先序图密度(D)和工件加工时间(t,n)分布相同时,DP算法目标函数值相对于 问题E下界的平均误差程度(gqp)与机器数(m)、工件数(m)没有明显相关性;DP算法的平均CPU时间 (qpu_〃)随机器数、工件数的増加増加,且随工件数的増加而増加铰快,因为工件数的増加引起外层循环 变量υ和中间层循环变量α的同时增加,而机器数的增加仪引起内层循环变量Mε,的增加 由表3可以看出,当机器数(m)、工件数(m)和优先序图密度(D)相同时,平均90与工件加工时间 (t;a)分布没有明显相关性,但当机器数(m)、工件数(m)和工件加工时间(t;,)分布相同时,平均gap随优 先序图密度(D)的增加而减小、这也印证了前文所说的,当D越大时,问题E的下界离其最优值越近;当机 器数、工件数和工件加工时间分布相同时,平均cpu-DP基本不随D发生变化,而当工件加工时间分布区间 增大时,平均αP_DP也增加,因为总体来说每个工件的完工时间上界增加了,即循环次数增加了 由表2和表3综合看出,平均gωp的最小值为2.03%、最大值为15.60%、统计值(即平均值)为8.06%,说 明DP算法具有较强的寻优能力和稳定性;DP算法比DP*算法的平均CPU时间降幅程度(cpu- Decrease) 与机器数(m)、工件数(n)、工件加工时间(t;,)分布、优先序图密度(D)没有明显相关性,平均 ca-Decrease 的最小值为5.39%、最大值为18.1%、统计值(即平均值)为10.39%,说明引入工完工时间界限能有效提 高计算效率 表2不同机器数和工件数的DP算法性能比较 D=0.8l,x~DU1,10 qup(‰) vU_DP(秒) CD-DP(秒 cpru_Decrease(% AVE MIN MAX AVE MIN MAX AVE MIN MAX AVE MIN MAX 5.00 20.00 15600.2838.861.631.361.991.821.612.0810.894.4816.37 30.00 12980.0067.037876349.089.217.6610.7311.569.5621.12 40.00 14.160.0050.9027.2524.1133.4530.0227.4134619.303.3414.71 50.00 2.630.0026.2764.5356.6368.6971.8063.0976.8910.115.8413.60 l0.0020.00 5.790.8616.113.332.863.943.703.314.389896.0115.15 30.00 5330.0027.2118.4115.6720.6919.4816.8122315.451.097.77 40.00 9.540.0032.6256.6950.59622060.0354.2866.175.541.549.96 50.00 4.040.0025.42145.93134.91159.26157.98139.20166.697.521.7111.99 6.610.0026.605.394.836.195815.147.00703-1.3511.61 30.00 2.210.0080928.5626.1932.8330.8528.9136.147.382.5911.14 40.00 9.010.0025.9188.8683.16100.1394.3885.63104.335.752.0012.85 50.00 3.800.0022.5821778197.97236.66233.05216.61253.316.553.20865 20.00 20.00 4340.068727.346.708.037.906849.286.882.0613.48 30.00 11.030.0031.3636.2531.6939.3038.6732.3941.776.162.1711.78 40.00 8.190.0025.68124.43114.50134.08131.60118.02146.635.391.488.74 50.00 2.150.0021.47307.34277.23336.63324.99291.28352.235.421.659.48 82 系统工程理论与实践 第31卷 表3不同工件加工时间分布和优先序图密度的DP算法性能比较 m=5n=20 gap(‰) p_D)P(秒)cm-DP(秒) cpu_Decrease(%) ti. u AVE MIN MAX AVE MIN MAX AVE MIN MAX AVE MIN MAX 1U[1,10 14.510.5138811.511281.761.731.501.9712.867.531582 0.80 11.120.0039.701.501.411.661.761.661.9415.1412.401723 0.90 2.030.007.141.351.111.501.651.491.8618.1110.7925.54 DU[120 0.70 11.640.6230.975.895.247.026.686.017.4111.935271832 0.80 12.660.0042.345.664.597.506.465.537.8612.763.9916.96 0.90 4.850.0012785.144.286.696.195.287.2417.127.1524.11 DU[1.30 0. 12.220.0020.7311.829.0813.3313.5911.0215.7513.117.1217.59 l1.890.0052.4913.2311.7815.1715.4413.9117.7514.206.7919.61 0.90 4.400.0017.1011.8710.3413.4113.9212.09160914.609.5518.67 DU[1.40 0.70 11.280.0030.01223920.0227.2324.7021.6929.099.322.3915.44 6.610.0038.5121.0418.4424.7024.4421.41268813.968.082125 0.90 4970.0023.9520.9015.1126.1724.2219.0228.7514.038.9720.54 表1和本表合并后的统计值(即平均值)8.060.0828.9145.1440.6249.9748.6543.5353.4710.394115.34 6结论及进一步的研究方向 本文考虑了工件加工具有任意标准优先序、一台机器在同一时间只可加工一个工件的变速机调度问题, 调度目标是最小化工件完工总成本.对该问題建立了DP模型和改进的DP算法,通过算例测试了DP算法 的正确性:并进行了两组不同参数情形的数值实验,大量随机数据表明:DP算法具有较强的寻优能力和稳定 性;DP算法中引入工件完工时间界限能有效提高计算效率 由于当D值较大时本文给出的问题E的下界才适宜反映其最优值,所以可寻找更合适的下界,以更好 显示DP算法的计算性能.另外,可进一步研究具有s-优先序的变速机最小化成本调度问题 参考文献 1 Adolphson D, Hu T C Optimal linear ordering[J]. SIAM Journal on Applied Mathematics, 1973, 25: 403-423 2 Lawler E L. Sequencing jobs to minimize total weighted completion time subject to precedence constraints Annals of Discrete Mathematics, 1978(2):7590 3 Sidney J B. Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs[J]. Operations Research, 1975, 23: 283-298 4 Chudak F, Hochbaum D. A half-integral linear programming relaxation for scheduling precedence-constrained jobs On a single machine[J]. Operations Research Letlers, 1999, 25: 199-204 5 Chang ], Hsu C. Task scheduling with precedence constraints to minimize the total completion time[]. Interna tional Journal Systems Science, 1995, 26: 2203-2217 6 Nilson N J. Principles of Artificial Intelligence M. Palo Alto, CA: Tioga, 1980 7 Dror M, Kubiak W, Dell'Olmo P. Scheduling chains to minimize mean flow time[J. Information Processing Letters.1997,61:297-301 8 Queyranne M, Schulz A S Approximation bounds for a general class of precedence constrained parallel machine scheduling problems[J]. SIAM Journal on Computing. 2006, 35: 1241-1253 9 lvan D B, Waleed MM, Alexandre E Lower bounds on precedence-constrained scheduling for parallel proces- sors[J. Information Processing Letters, 2002, 83: 27-32 10 Isto A, Erkki M. On a parallel machine scheduling problem with precedence constraints[J. Journal of Scheduling, 2006,9:493-495 11 Kim E S, Sunga C S, Lee I S. Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints[J]. Computers Operations Research, 2009, 36: 698-710 12 Chen H, Chu C, Proth J M. An improvement of the Lagrangean relaxation approach for job shop scheduling: A dynamic programming method J. IEEE Irans Actions on Robotics and Automation, 1998, 14(5 ):786-795 13 Du J, Leung JY T, Young G H Scheduling chain-structured tasks to minimize makespan and mean flow time[] Information and Computation, 1991, 92(2): 219-236 [14 Hall N G, Posner M F. Generating experiment al data for computational testing with machine scheduling appli- cations[J. Operations Research, 2001, 19: 8541-865