生产调度的稳定性研究

摘要

生产调度中存在着大量的约束条件，它是否可行完全取决于所有约束条件是否都满足。文章研究了面向约束的调度稳定性问题。给出了硬约束、软约束和约束满意度的定义，提出了调度稳定度的概念，最后给出一个生产调度案例说明了调度稳定度在生产实际中应用的意义。

正文

《1 引言》

1 引言

在一个调度方案确定以前, 人们总是希望了解这个方案能否顺利执行或者说它的抗干扰能力有多大。这主要是由于生产过程中存在着许多不确定因素, 例如加工时间的变化^[1,2,3], 产品需求量的变化^[4], 交货期的改变^[1]及设备故障^[4,5]等。这些不确定因素的存在使得原来的优化调度不可能一直顺利执行, 而引起再调度问题, 这是决策者不希望的。决策者希望小改或不改变原有的调度, 只牺牲一点性能指标, 以保持生产的稳定性。

一个调度方案的优劣有许多方面可比较, 如利润、生产的稳定性、设备利用率、最低消耗等, 这些方面都可在调度的优化模型中体现出来。但就调度本身的稳定性而言, 其性能指标无法体现, 为此Enns^[6]给出了调度稳定性 (这里指调度被修改的频度) 的仿真评价准则。然而, 这个准则只是一个再调度频度的检测, 并没有指出通过什么手段减少再调度频度, 即没有从根本上解决调度的稳定性问题。

生产调度中存在着大量的约束条件, 它是否可行完全取决于所有约束条件是否都满足。为了能适应生产环境的动态性, 在进行静态调度设计时, 应充分估计生产过程的变化对约束造成的影响, 尽量使过程中的变化不会对原有静态调度造成大的改变, 即可通过部分软约束的松弛吸收小的变化 (如原料拖延供应、加工时间变化等) 。这样, 静态调度就具有较好的柔性, 就会在一定程度上减少再调度的次数, 从而有利于生产的稳定进行。本文研究了面向约束的调度稳定性问题, 提出了调度稳定度的概念。

《2 约束的分类和约束的隶属度》

2 约束的分类和约束的隶属度

一般情况下, 生产调度中的约束表达式有如下三种形式

《图1》

其中:I_i为约束的指标集, b_i为常数项。式 (1a) 和式 (1b) 表示对产品、原料、设备和工序的约束, 式 (1c) 表示生产过程结构和工艺的约束, 它是相对稳定的, 因此等式约束式 (1c) 将不再研究。

约束有硬约束和软约束之分, 硬约束是必须满足的, 无松弛余地, 而软约束是有松弛余地的, 有时有些软、硬约束又是互向对方转化的。例如, 工序中的紧前约束是硬约束, 这对一个特定产品而言, 永远是硬约束;预测产品产量或产品完成期的约束是软约束, 而有些产品的合同期可以是硬约束 (必须在某一日期交货) , 也可以是软约束 (尽量在某个时间内交货, 提前或拖后都要受一定的惩罚) 。区别对待硬约束和软约束, 有利于减轻调度负荷。

定义2.1 硬约束和软约束约束表达式的右边常量项没有松弛余地, 且比较符号必须成立的约束为硬约束, 否则为软约束。

硬约束和软约束的表达式:

硬约束 $g_{i} (x) \geq \tilde{b}, i \in Ι_{i}$ $g_{i} (x) \geq \tilde{b}, i \in Ι_{i}$ , (2a)

软约束 $g_{i} (x) \leq \tilde{b}, i \in Ι_{i}$ $g_{i} (x) \leq \tilde{b}, i \in Ι_{i}$ , (2b)

其中, $\tilde{b}$ $\tilde{b}$ _i为有一定松弛裕度的常数项, 表示资源的可变性。

一个约束是否成立或该约束隶属于成立的程度是决策者非常关心的事情, 为此, 定义了约束的隶属度^[7]以表达某约束隶属于成立的程度。

定义2.2 约束的隶属度硬约束和软约束的隶属度定义为式 (1) 和式 (2) 中b_i和 $\tilde{b}$ $\tilde{b}$ _i的隶属度。

硬约束式 (1a) 和式 (1b) 的隶属函数见图1a和图1b。其中, g_imax和g_imin分别为由决策者确定g_i (x) 的最大估计值和最小估计值。硬约束式 (1a) 和式 (1b) 的隶属函数表达式分别见式 (3a) 和式 (3b) 。

《图2》

软约束式 (2a) 和式 (2b) 的隶属函数见图2a和图2b。其中, a_i和c_i分别为由决策者确定的b_i的最小和最大边界值。软约束式 (2a) 和式 (2b) 的隶属函数的表达式分别见式 (4a) 和式 (4b) :

《图3》

《图4》

图1 硬约束的隶属函数

Fig.1 Membership functions of hard constrains

《图5》

图2 软约束的隶属函数

Fig.2 Membership functions of soft constrains

约束的隶属度表示了在现有资源 (b_i) 的约束下, 允许约束条件向不利方向变化的程度。约束条件的左边取值 (g_i (x) 的取值) 距离边界值 (a_i或c_i) 越远, 实际运行中由参数变化或决策变量的变化引起的约束违背的可能性就越小。

命题2.1 对于约束式 (1) 和式 (2) , 约束的隶属度 (μ (g_i (x) ) (0≤μ (g_i (x) ≤1) 越大, 调度越稳定, 当μ (g_i (x) ) =0 时, 调度方案不再可行。

定理2.1 对于约束式 (2a) , 资源b_i的估计值a_i越小, 则调度越稳定。

证明:由式 (4a) 可知, 在b_i一定的情况下, a_i越小μ (g_i (x) ) 越大, 再由命题2.1得证。

定理2.2 对于约束式 (2b) , 资源b_i的估计值x_i越大, 则调度越稳定。

证明:由式 (4b) 可知, 在b_i一定的情况下, c_i越大μ (g_i (x) ) 越大, 再由命题2.1得证。

《3 生产调度的稳定度》

3 生产调度的稳定度

约束条件的隶属度虽然能表示约束违背的可能性, 但并没有表示约束的重要程度。无论是硬约束还是软约束, 总归有些是重要的有些是次要的。例如, 作为软约束的能源消耗约束就比产量约束更重要。所以, 在进行约束分析时不但要考虑约束的隶属度而且要考虑各约束的重要程度, 这样选择的调度方案才具有较高的满意程度。

定义3.1 约束满意度设λ_i为由决策者定义的约束函数g_i (x) 的优先级, 当约束为硬约束时, 式 (1a) 和式 (1b) 所对应的满意度分别定义为

《图6》

当s (g_i (x) ) ≥1时, 令s (g_i (x) ) =1。

当约束为软约束时, 式 (2a) 和式 (2b) 对应的满意度分别定义为

《图7》

其中λ_i∈[0, 1], 优先级别越高, 满意度越小, 这体现了决策者对约束的重视程度。

以上定义的是一个约束条件的满意度, 为了衡量一个调度的稳定性, 在所有约束满意度的基础上定义了调度稳定度的概念。

定义3.2 调度的稳定度设一个调度方案的各约束的满意度为s (g_i (x) ) , i∈I_i, 则调度的稳定度定义为

《图8》

命题3.1 调度稳定度越大, 约束违背的可能性越小, 调度就越稳定。

定理3.1 设有h个候选调度方案, 第j个候选方案的单一目标值 (多目标可处理为单目标) 为f_j, 其调度稳定度为SC_j, γ和 (1-γ) (γ∈[0, 1]) 分别为决策者对目标和约束的偏好系数。若目标值的最大和最小值分别为f_max和f_min, 候选方案的稳定度的最大和最小值分别为SC_max 和SC_min, 则对最大化目标最大稳定度的调度方案S为

《图9》

对最小化目标最大稳定度的调度方案S为

《图10》

其中J_j={1, 2, …, h}, S∈{1, 2, …h}。

证明:

1) 最大化目标对各候选调度S_j的目标值, 定义隶属函数:

《图11》

对各候选调度S_j的稳定度, 也定义隶属函数:

《图12》

这是一个多目标决策问题, 为此, 采用加权系数法处理, 有

《图13》

则在所有候选调度j中, 最大稳定度的调度方案为

《图14》

若SC_max=SC_min, 则在所有候选调度j中, 最大稳定度的调度方案为

《图15》

若f_max=f_min, 则在所有候选调度j中, 最大稳定度的调度方案为

《图16》

若f_max=f_min, SC_max=SC_min, 则所选调度j为唯一的调度候选S。以上综合可得式 (8) 。

2) 最小化目标对各候选调度S_j的目标值, 定义隶属函数:

《图17》

同理可得式 (9) 。

《4 仿真案例》

4 仿真案例

这里给出了一个简单的生产调度的案例, 以便能够说明约束的满意度、调度稳定度的计算和优先级的选择对最大稳定度调度方案的影响。

有一化工厂接到一个定单:要求生产两种产品P1和P2, 每种至少生产1 t, 多者不限;P1的预定交货期为15天, 最多拖延2天, 而P2的交货期为12天, 不能拖延。已知:生产1 t P1可获纯利2万元, 生产1 t P2可获纯利3万元;生产1 t P1需2 t原料M1, 2 t原料M2, 生产1 t P2需1 t原料M1, 2 t原料M2;生产1 t P1和P2分别需要4天;现有原料M1共10 t, M2共8 t, M1通过外协最多可购进3 t, 但不保险, M2在产品的交货期内已不可能再购入;决策者对原料M1和M2的重视程度分别为0.9和0.7, 根据生产设备的可靠性, 对产品P1和P2的交货期的重视程度分别为0.5和0.3。试确定一调度方案:当决策者对利润的重视程度分别为0.1、0.3、0.5、0.7和0.9时, 如何安排P1和P2的生产使获得的利润最大。 (假设不存在设备竞争、存储、人力等问题, 且产品产量为整数) 。

解:设P1和P2的产量为x₁和x₂, 这一调度问题可归结为如下数学模型:

《图18》

这里约束式 (10b) 和式 (10d) 为软约束, 式 (10c) 、 (10e) 和式 (10f) 为硬约束, 不考虑约束式 (10f) 的满意问题。约束式 (10b) ～ (10e) 的优先级依次为0.9, 0.7, 0.5和0.3, 为简明起见, x₁和x₂取整数。

根据软约束和硬约束的定义, 依据调度案例可得到各约束的如下参数:

约束式 (10b) :b₁=10, g_1min=4, c₁=13;

约束式 (10c) :b₂=8, g_2min=3;

约束式 (10d) :b₃=15, g_3min=4, c₃=17;

约束式 (10e) :b₄=12, g_4min=4。

g_imin (i=1, 2, 3, 4) 的取值是根据x的最小取值由各自的约束函数计算而得。表1给出了三个候选调度方案的各项指标。

表1 候选调度的各项指标

Table 1 Indexes of scheduling solutions to be selected

《图19》

表2给出了不同约束偏好值下的具有最大稳定度的调度方案 (阴影部分) 。由表2可知, 调度方案的最大稳定度和决策者的偏好有很大关系。

表2 不同目标偏好值下调度方案的最大稳定度

Table 2 The largest stability of scheduling solutionsunder different preferences of the object

《图20》

另外, 由表1可知, 约束式 (10b) 的满意度最低。因此, 在生产进行过程中, 应密切监视这个约束中各参数或决策变量的变化。

《5 结论》

5 结论

以往的调度优化, 其注意力大都集中在如何最大限度地满足各性能指标, 而忽略了各约束的满意分析, 尤其是一些含有不确定因素约束的满意分析。有时调度方案确定后, 某些约束已达到它的临界点, 不允许其参数项或变量有波动, 否则剩余调度将不再可行。

基于调度稳定度的稳定性分析, 在进行调度方案选择时充分考虑了约束违背的可能性问题, 并就约束的满意程度和调度目标之间根据决策者的意愿进行综合, 使得被选调度不但稳定性好, 而且也具有较好的目标值, 适于实际生产调度的应用。另外, 可利用约束的满意度分析, 监控约束满意度较小的约束条件中的决策变量或参数, 尽早消除约束违背的因素, 提高生产的稳定性。

展示更多