《1 引言》
1 引言
在一个调度方案确定以前, 人们总是希望了解这个方案能否顺利执行或者说它的抗干扰能力有多大。这主要是由于生产过程中存在着许多不确定因素, 例如加工时间的变化
一个调度方案的优劣有许多方面可比较, 如利润、生产的稳定性、设备利用率、最低消耗等, 这些方面都可在调度的优化模型中体现出来。但就调度本身的稳定性而言, 其性能指标无法体现, 为此Enns
生产调度中存在着大量的约束条件, 它是否可行完全取决于所有约束条件是否都满足。为了能适应生产环境的动态性, 在进行静态调度设计时, 应充分估计生产过程的变化对约束造成的影响, 尽量使过程中的变化不会对原有静态调度造成大的改变, 即可通过部分软约束的松弛吸收小的变化 (如原料拖延供应、加工时间变化等) 。这样, 静态调度就具有较好的柔性, 就会在一定程度上减少再调度的次数, 从而有利于生产的稳定进行。本文研究了面向约束的调度稳定性问题, 提出了调度稳定度的概念。
《2 约束的分类和约束的隶属度》
2 约束的分类和约束的隶属度
一般情况下, 生产调度中的约束表达式有如下三种形式
《图1》
其中:Ii为约束的指标集, bi为常数项。式 (1a) 和式 (1b) 表示对产品、原料、设备和工序的约束, 式 (1c) 表示生产过程结构和工艺的约束, 它是相对稳定的, 因此等式约束式 (1c) 将不再研究。
约束有硬约束和软约束之分, 硬约束是必须满足的, 无松弛余地, 而软约束是有松弛余地的, 有时有些软、硬约束又是互向对方转化的。例如, 工序中的紧前约束是硬约束, 这对一个特定产品而言, 永远是硬约束;预测产品产量或产品完成期的约束是软约束, 而有些产品的合同期可以是硬约束 (必须在某一日期交货) , 也可以是软约束 (尽量在某个时间内交货, 提前或拖后都要受一定的惩罚) 。区别对待硬约束和软约束, 有利于减轻调度负荷。
定义2.1 硬约束和软约束 约束表达式的右边常量项没有松弛余地, 且比较符号必须成立的约束为硬约束, 否则为软约束。
硬约束和软约束的表达式:
硬约束
软约束
其中,
一个约束是否成立或该约束隶属于成立的程度是决策者非常关心的事情, 为此, 定义了约束的隶属度
定义2.2 约束的隶属度 硬约束和软约束的隶属度定义为式 (1) 和式 (2) 中bi和
硬约束式 (1a) 和式 (1b) 的隶属函数见图1a和图1b。其中, gimax和gimin分别为由决策者确定gi (x) 的最大估计值和最小估计值。硬约束式 (1a) 和式 (1b) 的隶属函数表达式分别见式 (3a) 和式 (3b) 。
《图2》
软约束式 (2a) 和式 (2b) 的隶属函数见图2a和图2b。其中, ai和ci分别为由决策者确定的bi的最小和最大边界值。软约束式 (2a) 和式 (2b) 的隶属函数的表达式分别见式 (4a) 和式 (4b) :
《图3》
约束的隶属度表示了在现有资源 (bi) 的约束下, 允许约束条件向不利方向变化的程度。约束条件的左边取值 (gi (x) 的取值) 距离边界值 (ai或ci) 越远, 实际运行中由参数变化或决策变量的变化引起的约束违背的可能性就越小。
命题2.1 对于约束式 (1) 和式 (2) , 约束的隶属度 (μ (gi (x) ) (0≤μ (gi (x) ≤1) 越大, 调度越稳定, 当μ (gi (x) ) =0 时, 调度方案不再可行。
定理2.1 对于约束式 (2a) , 资源bi的估计值ai越小, 则调度越稳定。
证明:由式 (4a) 可知, 在bi一定的情况下, ai越小μ (gi (x) ) 越大, 再由命题2.1得证。
定理2.2 对于约束式 (2b) , 资源bi的估计值xi越大, 则调度越稳定。
证明:由式 (4b) 可知, 在bi一定的情况下, ci越大μ (gi (x) ) 越大, 再由命题2.1得证。
《3 生产调度的稳定度》
3 生产调度的稳定度
约束条件的隶属度虽然能表示约束违背的可能性, 但并没有表示约束的重要程度。无论是硬约束还是软约束, 总归有些是重要的有些是次要的。例如, 作为软约束的能源消耗约束就比产量约束更重要。所以, 在进行约束分析时不但要考虑约束的隶属度而且要考虑各约束的重要程度, 这样选择的调度方案才具有较高的满意程度。
定义3.1 约束满意度 设λi为由决策者定义的约束函数gi (x) 的优先级, 当约束为硬约束时, 式 (1a) 和式 (1b) 所对应的满意度分别定义为
《图6》
当s (gi (x) ) ≥1时, 令s (gi (x) ) =1。
当约束为软约束时, 式 (2a) 和式 (2b) 对应的满意度分别定义为
《图7》
其中λi∈[0, 1], 优先级别越高, 满意度越小, 这体现了决策者对约束的重视程度。
以上定义的是一个约束条件的满意度, 为了衡量一个调度的稳定性, 在所有约束满意度的基础上定义了调度稳定度的概念。
定义3.2 调度的稳定度 设一个调度方案的各约束的满意度为s (gi (x) ) , i∈Ii, 则调度的稳定度定义为
《图8》
命题3.1 调度稳定度越大, 约束违背的可能性越小, 调度就越稳定。
定理3.1 设有h个候选调度方案, 第j个候选方案的单一目标值 (多目标可处理为单目标) 为fj, 其调度稳定度为SCj, γ和 (1-γ) (γ∈[0, 1]) 分别为决策者对目标和约束的偏好系数。若目标值的最大和最小值分别为fmax和fmin, 候选方案的稳定度的最大和最小值分别为SCmax 和SCmin, 则对最大化目标最大稳定度的调度方案S为
《图9》
对最小化目标最大稳定度的调度方案S为
《图10》
其中Jj={1, 2, …, h}, S∈{1, 2, …h}。
证明:
1) 最大化目标 对各候选调度Sj的目标值, 定义隶属函数:
《图11》
对各候选调度Sj的稳定度, 也定义隶属函数:
《图12》
这是一个多目标决策问题, 为此, 采用加权系数法处理, 有
《图13》
则在所有候选调度j中, 最大稳定度的调度方案为
《图14》
若SCmax=SCmin, 则在所有候选调度j中, 最大稳定度的调度方案为
《图15》
若fmax=fmin, 则在所有候选调度j中, 最大稳定度的调度方案为
《图16》
若fmax=fmin, SCmax=SCmin, 则所选调度j为唯一的调度候选S。以上综合可得式 (8) 。
2) 最小化目标 对各候选调度Sj的目标值, 定义隶属函数:
《图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的产量为x1和x2, 这一调度问题可归结为如下数学模型:
《图18》
这里约束式 (10b) 和式 (10d) 为软约束, 式 (10c) 、 (10e) 和式 (10f) 为硬约束, 不考虑约束式 (10f) 的满意问题。约束式 (10b) ~ (10e) 的优先级依次为0.9, 0.7, 0.5和0.3, 为简明起见, x1和x2取整数。
根据软约束和硬约束的定义, 依据调度案例可得到各约束的如下参数:
约束式 (10b) :b1=10, g1min=4, c1=13;
约束式 (10c) :b2=8, g2min=3;
约束式 (10d) :b3=15, g3min=4, c3=17;
约束式 (10e) :b4=12, g4min=4。
gimin (i=1, 2, 3, 4) 的取值是根据x的最小取值由各自的约束函数计算而得。表1给出了三个候选调度方案的各项指标。
表2给出了不同约束偏好值下的具有最大稳定度的调度方案 (阴影部分) 。由表2可知, 调度方案的最大稳定度和决策者的偏好有很大关系。
Table 2 The largest stability of scheduling solutionsunder different preferences of the object
《图20》
另外, 由表1可知, 约束式 (10b) 的满意度最低。因此, 在生产进行过程中, 应密切监视这个约束中各参数或决策变量的变化。
《5 结论》
5 结论
以往的调度优化, 其注意力大都集中在如何最大限度地满足各性能指标, 而忽略了各约束的满意分析, 尤其是一些含有不确定因素约束的满意分析。有时调度方案确定后, 某些约束已达到它的临界点, 不允许其参数项或变量有波动, 否则剩余调度将不再可行。
基于调度稳定度的稳定性分析, 在进行调度方案选择时充分考虑了约束违背的可能性问题, 并就约束的满意程度和调度目标之间根据决策者的意愿进行综合, 使得被选调度不但稳定性好, 而且也具有较好的目标值, 适于实际生产调度的应用。另外, 可利用约束的满意度分析, 监控约束满意度较小的约束条件中的决策变量或参数, 尽早消除约束违背的因素, 提高生产的稳定性。