基于拉氏松弛的生产系统调度子问题序贯更新法

摘要

本发明公开了一种可以处理同种任务、同型设备、同类资源的生产系统优化调度的基于拉氏松弛的子问题序贯更新法,其特点是在拉氏松弛的框架下,每个设备或任务相对应的子问题带有与其它设备或任务有关的惩罚项,只对一个子问题采用序贯求解或更新后,就对拉氏乘子(系统价格)更新,从而根本解决了拉氏松弛框架下优化调度算法的同构难题,同时保留了拉氏松弛的框架、伪次梯度法和增广拉氏松弛法的优点,即便生产系统中不含有同型号设备,本发明中提出的方法依然适用,且效果也比标准伪次梯度法和标准拉氏松弛法好。

主权项

1.一种可处理同种任务、同型设备、同类资源的优化调度的基于拉氏松弛的生产系统调度子问题序贯更新法，其特征在于：在降低计算量的前提下，将非线性惩罚与序贯求解的思想相结合，从而得到与原问题最优调度更接近的调度方案，并保证方法的收敛性；按以下方法进行：假定有I套设备的生产系统生产某种产品，调度周期为T个时段，生产时需要J种原料，本发明考虑的生产系统调度问题可描述为：$\min \underset{i=1}{\overset{I}{\Sigma }}\underset{t=1}{\overset{T}{\Sigma }}[C_i\left(p_i\left(t\right)\right)+S_i(x_i(t-1),x_i\left(t\right))]-----\left(1\right)$ $s.t.\underset{i=1}{\overset{I}{\Sigma }}{p}_i\left(t\right)=p_d\left(t\right)-----\left(2\right)$ $\underset{i=1}{\overset{I}{\Sigma }}{r}_i^j\left(p_i\left(t\right)\right)\le p_r^j\left(t\right)-----\left(3\right)$ 其中pi(t)是设备i在第t时段内的产量；Ci(pi(t))为设备i在第t时段内的生产成本；xi(t)为设备i在第t时段所处的开关机状态，它记录到第t时段为止设备i已开(正值)或已关(负值)的时段数；Si(xi(t-1)，xi(t))为开、关机费用，仅当xi(t)与xi(t-1)异号时取非零值；是设备i在第t时段内产量为pi(t)时对原料j的消耗量；pd(t)是第t时段的合同产量；是第t时段内原料j的供应限制。除了(2)和(3)两个系统约束外，各设备还有自身的物理及运行约束，主要包括：生产能力限制约束：其中pimax(t)，pimin(t)分别为设备i在第t时段内的最大、最小产量；最小开关机时间约束：其中τiup，τidown分别为设备i的最小开、关机时段数；此外还有检修计划约束(即某些时段内某些设备必须开机或关机)、产量变化限制约束(同一设备在连续两个开机时段产量变化不能过大)等等，所有这些都视具体的生产系统而定；针对问题(1)-(5)的增广拉氏函数为：$L(\lambda ,\mu ,P,X,w)=\underset{i=1}{\overset{I}{\Sigma }}\underset{t=1}{\overset{T}{\Sigma }}[C_i\left(p_i\left(t\right)\right)+S_i(x_i(t-1),x_i\left(t\right))]+\underset{t=1}{\overset{T}{\Sigma }}\lambda \left(t\right)(p_d\left(t\right)-\underset{i=1}{\overset{I}{\Sigma }}{p}_i\left(t\right))$ $+\underset{t=1}{\overset{T}{\Sigma }}\underset{j=1}{\overset{J}{\Sigma }}{\mu }_j\left(t\right)(\underset{i=1}{\overset{I}{\Sigma }}{r}_i^j\left(p_i\left(t\right)\right)-p_r^j\left(t\right))+w\underset{t=1}{\overset{T}{\Sigma }}\left\{\right|p_d\left(t\right)-\underset{i=1}{\overset{I}{\Sigma }}{p}_i\left(t\right)|$ $+\underset{j=1}{\overset{J}{\Sigma }}\max [0,\underset{i=1}{\overset{I}{\Sigma }}{r}_i^j\left(p_i\left(t\right)\right)-p_r^j\left(t\right)]\}-----\left(6\right)$ 式中一些记号含义为：P＝[pi(t)]l×T，X＝[xi(t)l×T是两个矩阵，且P和X要满足(4)-(5)两个约束和其它的单设备约束；λ＝[λ(1)，λ(2)，Λ，λ(T)]是对应于约束(2)的乘子向量，μ＝[μj(t)]l×T是对应于约束(3)的乘子矩阵，且μj(t)≥0。w≥0是罚因子；与之相应的对偶问题为：${\Phi }^{*}\left(w\right)=\underset{\mu \ge 0,\lambda }{\max }\Phi (\lambda ,\mu ,w)=\underset{\mu \ge 0,\lambda }{\max }\left(\underset{P,X}{\min }L(\lambda ,\mu ,P,X,w)\right)----\left(7\right)$ 其中对增广拉氏函数求极小时P和X要满足(4)-(5)两个约束和其它的单设备约束；经过对式(6)的整理，可得到$L(\lambda ,\mu ,P,X,w)=\underset{i\ne k}{\Sigma }{L}_i(\lambda ,\mu ,P^{\left(i\right)},X^{\left(i\right)})+{\hat{L}}_k-----\left(8\right)$ 其中k∈{1，2，Λ，I}，P(i)，X(i)分别为P和X的第k行，且$L_i(\lambda ,\mu ,P^{\left(i\right)},X^{\left(i\right)})=\underset{t=1}{\overset{T}{\Sigma }}[C_i\left(p_i\left(t\right)\right)+S_i(x_i(t-1),x_i\left(t\right))-\lambda \left(t\right)P_i\left(t\right)+\underset{j=1}{\overset{J}{\Sigma }}{\mu }_j\left(t\right)r_i^j\left(p_i\left(t\right)\right)]$ (9)第k个子问题为：$\underset{p^{\left(k\right)},X^{\left(k\right)}}{\min }{\hat{L}}_k-----\left(10\right)$ 其中${\hat{L}}_k=L_k(\lambda ,\mu ,P^{\left(k\right)},X^{\left(k\right)})+w\underset{t=1}{\overset{T}{\Sigma }}\left\{\right|y_k\left(t\right)-p_k\left(t\right)|+\underset{j=1}{\overset{J}{\Sigma }}\max [0,r_k^j\left(p_k\left(t\right)\right)+z_k^j\left(t\right)\left]\right\}$ (11)$y_k\left(t\right)=p_d\left(t\right)-\underset{i\ne k}{\Sigma }{p}_i\left(t\right),z_k^j\left(t\right)=\underset{i\ne k}{\Sigma }{r}_i^j\left(p_i\left(t\right)\right)-p_r^j\left(t\right)-----\left(12\right)$ 在拉氏松弛的框架下，每个设备或任务相对应的子问题带有与其它设备或任务有关的惩罚项，只对一个子问题采用序贯求解或更新后，就对拉氏乘子(系统价格)更新，其描述如下：1)初始化：置迭代次数l＝0；给定乘子的初始值λl＝λ0，μl＝μ0≥0。在(6)中置w＝0并应用标准拉氏松弛调度方法对各个设备或任务独立进行调度(此时相同设备或任务的调度方案是相同的)，取得P0和X0，给定罚因子w0，然后，重置λ0为：${\lambda }^0\left(t\right)=\alpha (p_d\left(t\right)-\underset{i=1}{\overset{I}{\Sigma }}{p}_i^0\left(t\right))-----\left(13\right)$ 其中。记L0＝L(λ0，μ0，P0，X0，w0)，则(13)保证了L0＜Φ*(w0)；2)更新乘子(系统价格)：${\lambda }^{l+1}\left(t\right)={\lambda }^l\left(t\right)+s^l{g}_{\lambda }^l\left(t\right)-----\left(14\right)$ ${\mu }_j^{l+1}\left(t\right)={\mu }_j^l\left(t\right)+s^l{g}_{{\mu }^j}^l\left(t\right)-----\left(15\right)$ 其中$g_{\lambda }^l\left(t\right)=p_d\left(t\right)-\underset{i=1}{\overset{I}{\Sigma }}{p}_i^l\left(t\right)-----\left(16\right)$ $g_{{\mu }^j}^l\left(t\right)=\underset{i=1}{\overset{I}{\Sigma }}{r}_i^j\left(p_i^l\left(t\right)\right)-p_r^j\left(t\right)-----\left(17\right)$ 为相应的伪次梯度，sl是第1次迭代时的步长，且满足：0＜sl＜(Φ*(w0)-Ll)/‖gl‖2 (18)$L^l=L({\lambda }^l,{\mu }^l,P^l,X^l,w^0),{\left|\right|g^l\left|\right|}^2=\underset{t=1}{\overset{T}{\Sigma }}[g_{\lambda }^2\left(t\right)+\underset{j=1}{\overset{J}{\Sigma }}{g}_{{\mu }^j}^2\left(t\right)]-----\left(19\right)$ 3)依序对一个设备或任务调度并更新P和X：基于对(10)的求解对一个设备或任务进行调度，直到Ll+1＝L(λl+1，μl+1，Pl+1，Xl+1，w0)≤L(λl+1，μl+1，Pl，Xl，w0) (20)满足，转到下一步；4)更新迭代次数：l+1l，判断收敛准则是否满足，若满足则停止计算，否则转2)；可以用迭代次数限制或相邻两次迭代解的变化量或伪次梯度范数作为收敛性判据。