基于双向动态规划的无向图的无向图调度

基于双向动态规划的无向图的无向图调度

在线应用不仅是应用方案中最简单的问题，也是应用方案中最重要的问题。理论上通常把单机调度作为复杂调度系统的一个子系统,实际生产中比较复杂的调度问题也可以分解为多个单机问题来解决,研究单机调度问题可以帮助理解和解决更为复杂的多机调度问题。对单机的合理调度有助于实现资源的合理分配、降低成本、提高生产效率和设备的利用率,因而对其进行研究具有十分重要的实际意义。单机总加权完成时间调度是单机调度中的一个经典问题。在激烈的市场竞争中,能够在最短的时间内完成客户的订单可以有效提高一个企业的竞争力,因此,最小化1||∑w1具有无向环的多级连接图单机总加权完成时间调度问题具体描述如下:在1台机器上,有n个工件按照一定的优先级要求进行连续加工,通过计算工件完成时间{C单机加工过程中,工件间的优先级关系所构成的图形称为优先级图。图1举例说明了一个含有无向环的优先级连接图,工件OP5,OP6,OP7,OP8和工件OP8,OP9,OP10,OP11分别构成了一个无向环。以工件OP5为例,工件OP1,OP2,OP3和OP4是工件OP5的紧前工件,工件OP6和OP7是工件OP5的紧后工件。这里的“紧前”及“紧后”关系只表明工件的优先级关系,不一定指的是工件的加工顺序。例如在实际生产中,只有工件OP1,OP2,OP3,OP4都完成后才能开始工件OP5的加工,在单机上只能有1个工件在工件OP5开始前进行加工,因此,不能确定工件OP1,OP2,OP3和OP4的加工顺序。2计划时间范围参数表示如下:I—工件集,I={1,2,…,n}),其中,n为总工件数GpwK—计划时间范围,K=∑pC决策变量为根据以上参数,建立1|prec|∑w满足条件如下:在上述模型中,目标函数式(1)表示最小化所有工件的总加权完成时间之和。约束式(2)表示优先级图中工件间的加工优先级顺序;约束式(3)和(4)规定了变量的取值范围,其中,CN3拉格朗日协议算法的解决方案拉格朗日松弛算法是一种高效的优化算法3.1乘子的确定根据单机总加权完成时间调度的数学模型,给定一组拉格朗日乘子{u满足式(1)~(3)和(5)以及式(7)~(8)。令则有L为原问题的一个下界,为了获得最紧的下界,定义如下的拉格朗日对偶问题(LD):3.2拉格朗日松弛算法的建立由于前向动态规划只能处理有多个紧前工件的调度,而不能处理有多个紧后工件的情况,后向动态规划则刚好相反,因此,设计双向动态规划处理1个工件既有紧前工件又有紧后工件的情况。该方法由Zhang等使用双向动态规划求解优先级图中含无向环的调度问题时,必须先对优先级图做一定的转化。首先,任意打破1个环,即忽略环中1组工件的优先级关系以使优先级图中不存在环。然后,找到G用Z从工件的最后一个节点τ式中:从而得到松弛问题的下界:算例分析如下:以图1的工件优先级关系为例,表1给出了各个工件的加工时间和权重。应用拉格朗日松弛求解时,设其乘子{u(1)当打破环(1)和环(3)时,转换后的优先级图如图2所示。根据工件在树中的位置排序得到:1-5-2-3-4-6-8-7-9-11-10-12-13-14-15。(2)计算每个工件的最早和最晚可能完成时间,(3)从最后一个工件开始向前计算,由R(4)由R(5)由R(6)由R(7)由R(9)由R(10)RZ(11)由R(12)由R(13)由R(14)由R(15)由R(16)由R(17)由R计算下界和{C(19)通过向前追踪得到松弛问题的解:3.3拉格朗日乘数更新求解拉格朗日对偶问题LD是一个不断迭代的过程:给定一组可行的拉格朗日乘子{u3.4解的可行性分析因为对偶问题得到的解可能违反机器的能力约束,因此它的解对于原问题一般是不可行的。为构造可行解,本文基于拉格朗日松弛问题的解以及局域搜索设计启发式法将不可行解转化为可行解。4拉格朗日松弛法实验测试在PentiumⅣ主频3.0GHz的微机上运行,当对偶间隙小于0.05%或迭代次数达到100次时,程序停止。实验测试了7种问题规模,每种组合有15个实例,共有105个实例用于本实验,工件数从20~80个变化,随机产生的工件加工时间和权重都满足[2,8]之间的均匀分布。每个实例中,工件的优先级关系给定,假设工件优先级图为连接图。用拉格朗日松弛法求解调度问题时,对偶问题的最优解(L由表2和图3可得出如下结论:(1)在平均4.04s内,用拉格朗日松弛算法计算得到的总平均对偶间隙为0.63%,说明此算法可在较短的CPU时间内得到一个较高质量的解。(2)随着工件数的增加,对偶间隙、计算时间和迭代次数也随之增加。这是因为工件数的增多增强了调度难度,从而使问题变得更加复杂。(3)迭代初期,算法的收敛性比较快,但随着迭代数的增加,收敛性趋于平缓,得到的对偶间隙变化不大;迭代后期,由于利用启发式构造可行解时采用了局域搜索,这进一步提高了解的质量。5基于双向动态规划的拉格朗日松弛算法本文扩展了单机调度的研究,进一步对工件优先级关系中含无向环的单机调度问题进行了深入探讨,目标函数