随机环境中的生产作业计划问题!
朱道立"武 芳"龚国华
#复旦大学管理科学系"上海 $%%&’’(
摘要)生产系统中通常会涉及各种不确定因素"如不确定的顾客定单*不确定的生产作业时间
等+在当今时间竞争非常激烈的时代中"生产型企业如何把握生产系统中的这些不定因素变得
尤为关键+本文研究在不确定的作业时间*工序间延迟时间等情况下的生产作业计划问题"利
用 ,-./0123模型把这类随机生产计划问题归纳为一个多阶段随机决策问题+进而"采用
40510/520/松弛和 ,-./0123分解的方法求解这样一个大型的决策问题+最后"就一个实例建立
模型*进行计算和分析"以说明本文提出的随机生产计划方法的特点和有效性+
关键词),-./0123640510/520/松弛6动态规划6,-./0123分解6最优策略
中图分类号)7$8’ 文献标识码)9 文章编号):%%8;<=%8#$%%:(%>;%%>%;%=
? 引 言
生产系统中存在有许多不确定因素)如原材
料到达时刻的变动6工件作业时间的变动6最终产
品交货期的变动6工件加工优先权的变动等+传统
的作业排序问题主要针对确定环境和条件下的生
产模型"安排作业的活动*资源使用或配置设施的
时间表6一些因素的不确定性经过处理后视作确
定因素或干脆忽略不计+而在 <%年代的今天"在
重视交货期*质量*客户服务和信息协调的竞争时
代中"这些不确定因素再也不能被忽略了+这些因
素直接影响着工厂中各类生产作业计划的编排"
而这些作业计划活动驱动着企业的工作流*现金
流"最终影响企业的生产效率*经济效益及企业的
未来发展等+比如"在对现有工件的加工作业计划
中如果不考虑今后顾客定单*工件到达时间等因
素的不确定性"那么新来的非常紧急的定单*滞后
到达的工件可能会中断现有工件的作业计划"从
而使现有工件的已承诺交货期无法兑现"造成延
迟性的损失"并使企业现金流周期增长+
传统的确定型生产作业计划问题一般分
@A:*@A$*@AB等类型"基本解决方法有优先调度
规则*甘特图*线性规划*动态规划*C广度优先D
枚举法等E’F>G+而当考虑这些随机因素时"因为其
本身的不确定性的特点及不同随机因素间的相互
作用"使研究工作相当困难+目前研究这类问题常
用的方法有随机调度*随机动态规划等E$G+
随机调度主要着重于对某一台机器或一般的
排序网络系统的排序理论结果的研究"在这种方
法中"一般都假设变量有特定的分布+这种方法直
观上很清楚"但是应用效果并不太好"尤其是对于
那些非线性问题+
随机动态规划是数学规划的一个分支"对于
经济管理中的资源分配问题*设备更新问题以及
上面提到的确定型生产作业计划等"它都是一种
有效的方法+文E$G利用随机动态规划方法处理
随机生产作业计划问题+首先"利用 40510/520/
松弛把问题分解成为若干子问题"然后利用随机
动态规划求解相应的子问题"使用次梯度方法对
40510/520/乘子进行修正+
H-./0123分析方法是近年来兴起的一种新型
数学建模方法"又称C假想方案D分析法或C构想
第 &卷第 >期
$%%:年 :%月
管 理 科 学 学 报
IJKLM94J7N9M9OPNPMQHRSPMRPHSMRTSM9
U3V+&M3+>
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
J-X+"$%%:
! 收稿日期)$%%%;%8;$&6修订日期)$%%:;%&;:8+
基金项目)国家自然科学基金资助项目#8<=8%:%Y(+
作者简介)朱道立#:<&>;("男"上海人"教授"博士生导师+
法!"它是一种基于条件假设的规划决策模型#当
某些问题机理不清"缺少数据"又不能作实验来获
得数据时"人们只能在已有经验和某些研究的基
础上"对于将来可能发生的情况给出逻辑上合理
的设想和描述"然后用已有的方法构造模型#在实
践中"人们经常需要预期某一公司所面临的未来
环境和运营管理中的种种不确定因素等"$%&’()*+
分析方法提供了一种有效的决策手段"用于战略
计划,$-)(-&.*%/0(’’*’.1#在此应用$%&’()*+分析
方法"对随机环境下生产作业计划问题进行研究#
2 基于 $%&’()*+的随机生产作业
计划问题
2#2 确定型生产作业计划
假设同一时刻每台机器只能加工一个工件3
同一时刻每个工件只能在一台机器上加工3各项
作业时间与工件顺序无关"且包括准备时间和加
工时间3各工件在同一机床上的轮换加工无时间
间隔3所有机器类型均不相同"且互相独立无关3
每个工件在任一机器类型上只连续加工一次#
2#2#2 有关的参数和变量定义
4 55 整个作业计划的最大排序时刻
6 55任一作业计划时刻"678"9":"4;8
< 55 参与工件加工的机器类型总数
= 55 参与工件加工的任一机器的类型"=7
8"9":"<
>6= 55 6时刻可用的机器类型 =的加工能力
,即在时刻6时可使用的=类型机器的
数目1
? 55 待加工工件总数
@ 55 任一工件"@7 8"9":"?
A@ 55 工件 @完成作业所需的系列操作工序
总数
B 55 对工件 @的任一工序"B7 8"9":"A@
<@B 55一组可供工件@的B工序选择的适当的
机器类型
=@B 55 适于工件 @的 B工序的某一类型机器"
即 =@BC <@B
D@,B155 工件 @的 B工序的开工时刻
D@,E155 待加工工件的到达时刻
F@,A@155 工件 @的交货期
G@ 55 工件 @的延期惩罚权重"表示工件 @延
期交货的惩罚函数的惩罚因子"与顾
客对相应的定单交货期要求的轻重缓
急有关
H@ 55 工件 @的超前惩罚权重"表示工件 @提
前交货的惩罚函数的惩罚因子"与工
件相应的库存费用有关
I@=,B155工件@的B工序在某一类的=型机器上
加工的作业时间
J@,B1 55 工件 @的 B工序完工时刻
K@,B1 55 工件@在B工序和BL8工序间的延迟
时间"J@,B1L K@,B1即为第 BL 8道工
序的就绪时刻
上述参数如 4M<M>6=M?是给定的系统常数3
而工件 @的 A@MD@,E1MF@,A@1MI@=,B1MG@,B1MH@M
K@,B1等是和工件 @M工序 BM机器类型 =的等有关
的常数3
系统的决策变量是工件 @的 B工序开工时刻
D@,B1以及工序所占用的机器类型 =@B#
工件@的B工序的完工时刻J@,B1是一个中间
变量#
2#2#N 运营的约束条件
,O1工件到达时刻的限制
只有待加工工件@到达后"对@的第一步加工
工序才能开始3即
D@,E1P D@,81"@7 8":"? ,81
,Q1操作过程的限制
只有第 B道工序完成"并经过工序间的延迟
时间之后"第 BL 8道工序才能开始3即
J@,B1L K@,B1P D@,BL 81"@7 8":"? ,91
B7 8":"A@; 8
,R1作业时间的需求
工序的完成时刻应等于工件 @第 B道工序的
开始时刻加上相应的作业时间" 即
J@,B17 D@,B1L I@=,B1"@7 8":"?3
B7 8":"A@3=C <@B ,S1
,T1机床加工能力限制
在时刻 6分配给机床类型 =的加工任务的数
量应少于或等于>6="其中>6=表示在6时刻可用
的机器类型 =的加工能力#
59U5 管 理 科 学 学 报 9EE8年 8E
VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
月
!
"
!
#
$"%&’#() *%&+%, -+.+/+%0 .1
&2 3"# ’4(
其中 $"%&’#(, .+如果 5"’#() %) 6"’#(+且 &,
&"#2 3"#1否则 $"%&’#(, -7
87879 生产计划的目标函数
评价生产作业计划优劣的一般标准有:
;7尽可能地满足顾客的交货期1
<7极小化流程时间’作业在工序中所耗费的
时间(1
=7极小化在制品库存1
>7极小化设备和工人的闲置时间等7
传统的作业计划模型通常以标准<为目标函
数的内容7而在市场至上?服务至上和顾客至上的
理念盛行的今天+尽力满足顾客的交货期 ’标准
;(已经成为许多企业最为重视的目标7尽管这样
可能会使流程时间增长?在制品库存加大+和其它
的标准有矛盾+但这一目标函数是和企业的长期
经营目标?企业的长远发展和最终利益相符合的1
同时+这也与准时化生产 @AB的管理方法和思想
是根本一致的7而且在满足某些条件时’如使用
同一设备加工两种以上工件时+工件间的转换准
备时间与完成加工的顺序无关+且目标函数为总
延期时间最小时(+可以证明:满足顾客的交货期
准则与极小化流程时间准则是等价的7
选取目标 ;+即以最小化工件完工期的提前
或延期相应的惩罚项作为目标函数7因此+确定型
生产作业计划模型可表达为如下的优化问题:
CDE
5"’#(+&"#
!
F
",.
’G"HI"J K"LI"( ’M(
其中 H", CNOP-+6"’Q"(0 R"’Q"(S
L", CNOP-+R"’Q"(0 6"’Q"(S
满足约束条件’.(T’4(7
87U 随机型生产作业计划
生产环境中+存在许多不确定的随机因素+如
不确定的待加工工件到达时间?作业时间?工序间
延迟时间等1在今天的 VDCWXYNZW[\]C W^VDVD]E的
时代中+正确考虑和处理这些随机因素+成为企业
制定生产作业计划的关键7
假设参数+如工件 "的 5"’-(?R"’Q"(?_"&’#(?
G"’#(?K"?‘"’#(等在随机环境中不能事先确定1
它们是符合某些给定的离散分布的独立随机变
量7其它各变量的定义类似于上述确定型问题7
在不确定情况下建模时+关键的问题是如何
描述随机因素和参数以及定义在随机环境中的决
策7Z\WENaD]分析方法提供了一种描述多阶段随
机优化问题的简单有效的工具7
87U78 Z\WENaD]方法和多时段随机决策问题
在 Z\WENaD]方法里+把多时段随机决策问题
的整个过程事件发展中的各种可能途径定义为相
应的 Z\WENaD]7它们相应地用一个特定的关键随
机因素的发展来表示+而这种随机因素用一个随
机变量b,’b.+/+bH(来表示7b具有有限个实现
b.+/+bc+并相应有概率 .^+/+^c7则相应于 b的
某个实现的 Z\WENaD]为
d’bc(, ’d.’bc(+/+dH’bc((
其中d_’bc(+_,.+/+H是一系列的随机参数+代
表了多时段过程中事件发展的各种可能性途径7
往往用 Z\WENaD]树来描述这个事件的动态发展过
程’见图 .(7
图 . 4个时段的 Z\WENaD]VaWW+共有 e个 Z\WENaD]
在多时段随机决策问题中+希望得到一个最
优策略’]^VDCNfZVaNVWgh(+即每个时段+在某个特
定关键条件下如何进行最优的决策7最优策略使
决策者对某个指标的期望值达到最大或最小7
为了处理方便+先对每个 Z\WENaD]矢量
i’bc(+定义相应的决策变量
j’bc(, ’j.’bc(+/+jH’bc((+k, .+/+c7
但 是+ 这 些 决 策 变 量 必 须 满 足 所 谓 的
E]EXNEVD\D^NVDlDVh条件
TmMT第 M期 朱道立等:
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
随机环境中的生产作业计划问题
!"#$%&’!"#$(&)如果*+#$%&’*+#$(&)+’,)
-)".
这个条件指出了具有到第 "阶段的同样历史
的两个 /0123456)应该具有同样的决策.换句话
说)决策只决定于过去)而不是将来.图 7说明了
2628329505:395;59<条件.
图 7 2628329505:395;59<约束
注=水平线相连的变量是等同的)
指出了相应的 2628329505:395;59<约束
一个基于 /0123456方法的随机多级决策问题
的典型模型可描述为
>52?:@A@#!#$@&& #B&
C"#$@&!"D,#$@&E F"!"#$@&’ G"#$@& #H&
!"#$@&I J" #K&
!"#$%&’ !"#$(&
如果
*+#$%&’ *+#$(&)+’ ,)-)"L #M&
"’ ,)-)NL@’ ,)-)O.
其中约束#H&表示相应于各个 /0123456时段动态
平衡关系)约束#K&表示为各时段决策应满足的
约束.而约束#M&则是所谓的2628329505:395;59<约
束.必须指出的是约束#H&和#K&对于 /0123456都
是可分离的)而 2628329505:395;59<对 @是偶合的.
随着时段数 N的增大)随机决策问题是一个大型
的优化问题.在此采用 P3Q432Q532松弛和对偶方法
处理来求解这个问题)这就是 /0123456分解方法.
随机生产计划问题的 /0123456模型
,&/0123456状态参数
确定型的生产作业计划模型中的 GT#U&V
AT#WT&V"TX#Y&VZT#Y&V[T#Y&V\T#Y&等在随机生产作
业计划问题中都变成了随机参数或变量.
首先)将对这些随机因素进行分析)在此基础
上给出本文讨论的 /0123456状态参数.
对每一个 T’ ,)-)])记 OT为其 /0123456集
合)即
OT’ ,^)-)OTU_
‘ 模型的决策从第一工序开工时刻GT@#,&开
始)故决策时随机的待加工工件 T的到达时刻
GT#U&是已知信息L因此)虽然 GT@#U&在实际中具
有随机性)但对于本模型而言)考虑 GT@#U&的随机
性对决策没有意义L故这里假设GT@#U&’GT#U&)即
GT@#U&是已知常数.
‘ZT@#Y&表示每条 /0123456对应的工件 T的
延期惩罚权重)而实际上 ZT@#Y&一般只与顾客对
相应的定单和新增定单交货期要求的轻重缓急有
关)而与每条 /0123456的状态和状态转移无关.所
以在决策过程中)对所有的 @
ZT@#Y&’ ZT#Y&
‘交货期AT@#WT&也与每条/0123456的状态和
状态转移无关)对所有的 @也取
AT@#WT&’ AT#WT&
综合上述讨论)考虑 /0123456状态为
*TY#$O&’ #"T@X#Y&)[T@#Y&&)Y’ ,)-)WT
7&随机决策变量
在随机环境的生产作业计划问题里的随机决
策是GT@#Y&和XT@Y.而在实际加工中)通常在加工前
编制的加工工艺说明书中就确定了每一工序对应
的机器类型 XT@Y.或通过其它表格形式等确定 XTYL
因此)为简化起见)只研究随机决策变量 GT@#Y&.
a&约束条件
在 /0123456环境里)首先得到动态平衡的各
时段限制约束的 /0123456形式
\T@#Y&E [T@#Y&b GT@#YE ,&)T’ ,)-)]L
Y’ ,)7)-)WTD ,L@I OTL
\T@#Y&’ GT@#Y&E "T@X#Y&)T’ ,)-)]L
Y’ ,)7)-)WTD ,LXI FTYL@I OTL
GT@#U&b GT@#,&)T’ ,)-)]L@I OT
如上分析)必须要加上 2628329505:395;59<约束
cdec 管 理 科 学 学 报 7UU,年 ,U
fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
月
!"#$%&’ !"($%&)如果 *"+$,#&’ *+$,(&)-
+’ .)/)%0"’ .)/)10%’ .)2)/)3"4
因为随机因素和加工工序数目的增长将导致
随机事件的数目呈指数型的增长)所以很难将所
有的随机事件都考虑在机床加工能力的约束中4
将在期望值意义上满足机床加工能力的约束5
6
1
"’.
6
7"8
#’.
9"#$6
3"
%’.
:";<#$%&&= >;<)
;’ 8).)/)?@ .0<A B"%
其中 :";<#$%&’ .)如果!"#$%&=;=C"#$%&)且<’
<"%A B"%0否则 :";<#$%&’ 84
D&期望目标函数
在EFGHIJKL随机环境里)工件"在3"工序完成
时刻也是随机的4因此)随机决策模型中目标函数
应是期望总延迟和提前惩罚最小)即
6
1
"’.
$M"6
7"8
#’.
9"#N2"#O P"6
7"8
#’.
9"#Q2"#&
其中 N"#’ RIST8)C"#$3"&@ U"#$3"&V0
Q"#’ RIST8)U"#$3"&@ C"#$3"&VW
综合上述讨论)得到多阶段生产作业计划的随机
决策模型5
RKH
!"#
6
1
"’.
$M"6
7"8
#’.
9"#N2"#O P"6
7"8
#’.
9"#Q2"#& $.8&
C"#$%&O X"#$%&= !"#$%O .&)"’ .)/)10
%’ .)/)3"@ .0#A 7" $..&
C"#$%&’ !"#$%&= Y"#<$%&)"’ .)/)10 $.2&
%’ .)/)3"@ .0<A B"%0#A 7"
!"#$8&= !"#$.&)"’ .)/)10#A 7" $.Z&
6
1
"’.
6
718
#’.
9"#$6
3"
%’.
:";<#$%&&= >;<) $.D&
;’ 8).)/)?@ .0<A B"%
!"#$%&’ !"($%&)如果 *"+$,#&’ *"+$,(&)+’ .)/)
%0%’ .)/)3"0"’ .)/)14 $.[&
其中 N"#’ RIST8)C"#$3"&@ U"$3"&V0
Q"#’ RIST8)U"$3"&@ C"#$3"&V
且 :";<#$%&’ .)如果!"#$%&=;=C"#$%&)且<’
<"%A B"%0否则 :";<#$%&’ 84
\ 基于 EFGHIJKL的随机生产作
业计划问题求解
\4] I^_JIH_KIH松弛和 EFGHIJKL分解方法
在随机生产计划模型中)加工能力约束条件
和 EFGHIJKL的HLH‘IHaKFK9IaKbKac约束对"和#是不
可分离的)而其它的约束和目标约束对"和#是可
分离的4
可以用记号 d"#)"’ .)/)10#A7"表示能满
足约束$..&e$.Z&的可行决策集合4由于 #的数
目可能较大)因而随机生产计划是一个大型的离
散规 划 问 题4下 面 将 用 I^_JIH_KIH松 弛 和
EFGHIJKL分解方法来解决问题4
记 !"#’ $!"#$.&)/)!"#$3"&)HLH‘IHaKFK9IaKbKac
约束可用等式6
7"8
#’.
f"#!"#’ 8来表示)其中 f"#是一
个相应的矩阵)"’ .)/)10#’ .)/)7"84
对 于 HLH‘IHaKFK9IaKbKac和 能 力 约 束 的
I^_JIH_KIH松弛是对于给定的对偶乘子g和h)构
成 I^_JIH_KIH子问题4其决策变量为 !"#)目标函
数为 i$g)h&4
j$g)h&’ RKH
!"#Ad"#
6
1
"’.
k"6
7"8
#’.
9"#N2"#O P"6
7"8
#’.
9"#Q2"#O g"6
7"8
#’.
f"#!T V"# O6
;<
h;< 6
1
"’.
6
7"8
#’.
9"#6
3"
%’.
:";<#$%&@ >l mn o;< ’
RKH6
1
"’.
6
7"8
#’.
p"#$!"#)g)h&)!"#A dn o"#
p"#$!"#)g)h&’ 9"#$k"N2"#O P"Q2"#&O g"f"#!"#O 9"#6
3"
%’.
6
C"#$%&
!"#$%&
h;<"
e[[e第 [期 朱道立等5
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
随机环境中的生产作业计划问题
如果交货期 U"$3"&是随机变量)取有限值 U"#U$3"&的概率为 9U)U’ .)/)r0则目标函数为
6
1
"’.
$M"6
7"8
#’.
s"#6
r
U’.
9UN"#U2O P"6
7"8
#’.
9"#6
r
U’.
9UQ"#U2&
其中 N"#U’ RIST8)C"#$3"&@ U"#U$3"&V0Q"#U’ RIST8)U"#U$3"&@ C"#$3"&V
其中 !是"
#
$%&
’$维()是 *+,维的矢量-
而 ./01/203/2对偶问题
456% 7/8
9!():
;9!(): 9&<:
文=>?给出了如下弱对偶结果@
命题 A ./01/203/2对偶的最优值 456是原
问题9&B:C9&D:的一个下界-如果对某个9!():(
./01/203/2松弛的相应解 E$F($% &(G(#HFI J$
是可行的话(那么它一定是原问题的解(而9!():
是对偶问题的解-
不难看出 ./01/203/2对偶是不可微凹的规
划问题(可以用次梯度方法=K?或内点方法C分析
中心方法=L?来求解-注意到
;9!():%"
#
$%&
"
J$B
F%&
;$F9!():(其中
;$F9!():% 732M5$F9E$F(!():(E$FI N$FO9&>:
所以./01/203/2松弛可分解为"
#
$%&
J$B个独立的子
问题-而每个子问题是一个规模不大的确定性的
调度问题(其决策变量是E$F-对于次梯度方法或内
点方法 C 分析中心方法(在每次迭代中要求函数
值和次梯度的计算-根据对偶函数的凹性(;的次
梯度是
P;%"
#
$%&
"
J$B
F%&
P;$F9!():
而 P;$F9!():% QR2S P5$F9E$F(!():@E$F是9&>:M O的解 (
其中 QR2SM+O表示凸组合-
因此 "
J$B
F%&
T$FEU V$F $( "
#
$%&
"
J$B
F%&
W$F"
’$
X%&
Y$*,F9X:Z [U V*, *,
构成了 ;的一个次梯度(其中 E$F($% &(G(#HF%
&(G(J$B是子问题9&>:的解-
\-\ 求解 ./01/203/2子问题的动态规划方法
./01/203/2子 问 题 确 定 性 优 化 问 题
732M5$F9E$F(!():E$FI N$FO-
在子问题中(所有参数都是确定性的(可用动
态规划来求解-在最后一道工序里(有广义费用
]$’$F9E$F9’$::% W$F^ $_
‘
$Fa !$T$F9’$:E$F9’$:a
"
b$F9’$:
*%E$F9’$:
)*,$’$
相应的递推公式为
]$XF9E$F9X::% 732
E$F9Xa&:
=c$d‘$Fe$a !$T$F9X:E$F9X:a
"
b$F9X:
*%E$F9X:
)*,$Xa ]$9Xa&:F9E$F9Xa &::?%
c$d‘$Fe$a !$T$F9X:E$F9X:a "
b$F9X:
*%E$F9X:
)*,$Xa
732
E$F9Xa&:
]$9Xa&:F9E$F9Xa &::
其中e$中一个整数变量(如果第$工件的X工序是
第一工序(则 e$等于 &(否则等于 B-
最后(子问题的最优值是在第一工序得到(而
子问题的解即相应的最优开工时间(则由动态规
划的正向过程而得到-动态规划的具体计算过程
可参照文=&&?-
\-f 对偶问题的求解方法
对偶问题的求解可用次梯度=K?或用内点方
法 C 分析中心方法=L?(所要求的函数及次梯度的
信息是由子问题的解所提供-次梯度方法比较容
易实现(但收敛速度较慢H采取某些改进措施可帮
助提高速度-相比之下(分析中心方法计算速度较
快(但是程序实现较为复杂-
\-g 可行调度的实现
正如文=‘(&‘?指出的那样(在./01/203/2松
弛问题里(即使9!():是最优的对偶解(子问题的
解不一定满足能力约束和 2R2h/2i3Q3W/i3S3ij约
束-而一些特殊的试探方法可被用来求得满足这
些约束的可行调度(它们就是所要求的好的可行
调度-
文=&B?的k3lilQmnopk320mnp13li3Ql可用来求
得满足能力约束的可行调度-而在文=&‘?中(作
者 所 提 出 的 q1/2QmhqRp2o 方 法 可 处 理
2R2h/2i3Q3W/i3S3ij约束-要指出的是(上述r最优s
调度是根据随机事件发生的规律进行预先处理而
得到的-一旦随机事件发生后(这个信息可立即被
利用进行重新调度(这也是 lQn2/13R方法求解最
优策略9RWi37/kli1/in0j:的一大优点-
\-t 计算过程
最后(给出求解随机生产作业计划问题的计
算过程@
第 u步 问题初始化H
第 A步 子问题求解(即 7325$F9E$F(!v()v:H
第 \步 对偶乘子调整(即求9!va&()va&:H
第 f步 如得到最优对偶乘子9!w()w:(转
第 x步H否则转第 &步H
C<DC 管 理 科 学 学 报 ‘BB&年 &B
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
月
第 !步 实现可行调度"过程结束#
$ 实例分析
$#% 问题的 &’()*+,-描述
这里"给出一个简单的例子"具体地说明本文
所叙述的模型和方法#
设有一个工件 ."工序 /共有 0道"即 03
工件的延期权重为 5"提前权重为
7#83
待加工工件到达时刻9.:;7<273该工件的交
货期 =.;1.<2 83
有两类机床类型 >./2 ?"分别为 @./2 5"车
床3@./2 ?"铣床3
工序 5和 0在车床 5上加工"工序 ?在铣床 ?
上加工3
问题的最大排序时刻 A2 B"则 C2 7"5"?"
D"B3
随机因素为工件加工时刻 E.:@;/<"设 E.:@;5<F
E.:@;?<FE.:@;0<有相同的分布"即
E.:@;/<2
5"G2 7#8H?"G2 7#8
则相应的 &’()*+,-总数为 I2 ?02 B3
设工序间没有暂停时间"即 J5:;/<2 73
相应的 &’()*+,-K+((和 )-)L*)K,’,G*K,M,KN约
束分别见图 5和图 ?#
对每个 .O P":.O IP"相应的子问题为
Q,); V59.:T W
0
/25
W
X./
C29./
Y5C@
其中 S.:2 Q*Z[7"X.:;1.<\ =.;1.<]
U.:^ 2 Q*Z[7"=.;1.<\ X.:;1.<]
9.:;7<2 7_ 9.:;5<
X.:;/<T J.:;/<_ 9.:;/T 5<"/2 5"?
X.:;/<2 9.:;/<T E.:@;/<"/2 5"?"0
$#‘ 问题的求解与分析
上述算法用 a-+K+*)编制了模拟程序"对实
例规模的问题进行优化排序"结果如图 0所示#
图 0 例题 &’()*+,-优化排序示意图
即第 5工序最佳开工时刻为 9;5<2 7时刻#
如果第5工序的加工时间为E.:5;5<25"则第
?工序的开工时刻为 9;?<2 53 ;*<
如果第5工序的加工时间为E.:5;5<2?"则第
?工序的开工时刻为 9;?<2 0时刻# ;b<
如果第?工序的开工时刻为9;?<25"且第?
工序的加工时间为E.:?;?<25"则第0工序的开工
时刻为 9;0<2 ?3 ;’<
如果第?工序的开工时刻为9;?<25"且第?
工序的加工时间为E.:?;?<2?"则第0工序的开工
时刻为 9;0<2 c时刻# ;d<
如果第?工序的开工时刻为9;?<20"且第?
工序的加工时间为E.:?;?<25"则第0工序的开工
时刻为 9;0<2 c3 ;(<
如果第?工序的开工时刻为9;?<20"且第?
工序的加工时间为E.:?;?<2?"则第0工序的开工
时刻为 9;0<2 8时刻# ;e<
相应的甘特图 f*)KK’g*+K如图 c所示"其中
小括号内参数为;."/<"中括号内参数为[E.:5;5<"
E.:?;?<"E.:5;0<]
hi8h第 8期 朱道立等j
kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
随机环境中的生产作业计划问题
图 ! 工件 "加工排序甘特图
通过多次改变参数#如延期权重$%提前权重&%交
货期 ’(’)*+和有关概率等#分析发现无论参数的
改变怎样有利于提前期的惩罚#第一工序的开工
时刻,(-).+最优解一般都为,(-).+/ .0至多会有
,(-).+/.或(的情况0虽然,(-).+/.大体不变#
但工件的完工时刻变化很大#1(-)*+/2#3#4#5都
可能出现6这和日常生产实践中的经验是相符合
的7一般为了更好地应变环境条件的变化#工序的
开工宜早不宜迟#应尽量早开工#这样中间就可以
有较宽松的排序调节余地#自由度较大6
而相比缺货的惩罚而言#工序间的工件堆积
现象)即提前完工的惩罚+是次要的6改变函数中
的参数时发现7改变延期权重 $的效果最明显#目
标函数的最小值变化最大0改变交货期 ’(’)*+和
有关概率的效果次之0而改变提前权重 &一般只
是较大程度地影响了子问题的目标函数的取值#
对最终结果影响微乎其微6
参 考 文 献7
8(9 :;<=>?@A#B>>CDE#@F6GHIJ=>FJK>FI L>M
;<>NIO?PKOQ=PFH?R8@96SOTOFUVP;H?J;;WJTHJX#
(Y5Y#4)*+7(.3Z(((
8[9 \P<]V#B<J? >^?R6_>UJ‘H?RP?QJF=OH?aH?L>MZ
;<>N;Q<JUP‘H?R8B96DH;F=b?=JF?O=H>?O‘B>?KJFJ?QJ
>?cNJFO=H>?;d ePO?=H=HTJ_O?ORJIJ?=#(YY46
!!Y4
8*9 VJFFaf \#]J?‘J;CaW#gJ‘‘IO??GA6BFH=HQO‘
FO=H>;Q<JUP‘H?R7Ua?OIHQUPJZUO=JNF>QJUPFJ;P?Z
UJFUJIO?UP?QJF=OH?=a8@96bbA GFO?;OQ=H>?;#
(Y5!#(3)(+75(Z5Y
8!9 _>>Ua]A6h=FO=JRHQIO?PKOQ=PFH?R7Ua?OIHQ?JX
UHFJQ=H>?;K>F=<J(YY.;8^ 96S>IJX>>U#b\7
WHQ<OFU 6^bFXH?#(YY.
829 B>?XOaWf#_OiXJ‘‘f \#_H‘‘JF\f6G<J>Fa
>K;Q<JUP‘H?R8^ 96WJOUH?R#_:7:UUH;>?ZfJ;Z
‘Ja#(Y34
839 B<O;JWV#:jPH‘O?>k@6宋国防等译6生产与运
作管理8_96北京7机械工业出版社#(YYY
849 f>‘;Ja\:#kJI<OP;JFl\6b?=JFRJFO?UQ>IMHZ
?O=>FHO‘>N=HIHmO=H>?8B96kJXn>FC7fH‘JaZb?=JFZ
;QHJ?QJ#(Y55
859 VJF=;JCO;^]6B>?;=FOH?JU>N=HIHmO=H>?O?U\OZ
RFO?RHO?IP‘=HN‘HJFIJ=<>U;8^ 96kJXn>FC7:QOZ
UJIHQ#(Y5[
8Y9 l>KKH?@\#SOPFHJ:#gHO‘@]6^ JQ>IN>;H=H>?O?U
?>?ZUHKKJFJ?=HOM‘J>N=HIHmO=H>?XH=<NF>LJQ=HTJO‘R>Z
FH=<I8@96_O?ORJIJ?=hQHJ?QJ#(YY[#*57[5!Z*.[
8(.9 \P<]#S>H=I= 6^hQ<JUP‘H?R>KIO?PKOQ=PFH?R
;a;=JI;P;H?R=<J\ORFO?RHO?FJ‘OiO=H>?=JQ<Z
?HjPJ8@96bAAA#GFO?;6W>M>=6:P=>IO=6#
(YY*#Y7(.33Z(.4Y
8((9 VJF=;JCO;^ ]6^ a?OIHQUJQ>IN>;H=H>?H?;=>Q<O;Z
=HQH?=JRJFNF>RFOIIH?R#Ua?OIHQNF>RFOIIH?R
O?U>N=HIO‘Q>?=F>‘8@96:=<J?OhQHJ?=HKHQ#VJ‘Z
I>?=#_:#(YY3
8([9 BOF>JBB#hQ<P‘=mW6 P^O‘UJQ>IN>;H=H>?H?;=>Q<O;=HQH?=JRJFNF>RFOIIH?R8@96cNJFO=H>?WJ;JOFQ<#(YYY#[!7
*4Z!2
opqrsptrusvwxyz{|z{r}pus~r}zuv{!z"p{#v{}
$%&’()Z*"#+&,(-.#/01//2)Z32(
4524 管 理 科 学 学 报 [..(年 (.
5555555555555555555555555555555555555555555555555555555555555555555
月
!"#"$%&%#’()*%#)%+%,"-’&%#’./01*#%11()233435607"#8#*9%-1*’:.(2"#$2"*;<<=>>.?2*#"
@ABCDEFCG H2*1,",%-7*1)011%1’2%I3J123,1)2%704*#$0#7%-’2%)*-)0&1’"#)%1351’3)2"1’*),-3)%11K
*#$’*&%.0#)%-’"*#7%4":%7’*&%J%’L%%#’L33,%-"’*3#1.*#70)%1’2%,-3J4%&*#’3"1’3)2"1’*)&04’*K
,2-"1%7%)*1*3#J:01*#$1)%#"-*3&37%4*#$"#70’*4*M%’2%&%’23735N"$-"#$*"#-%4"O"’*3#.1)%#"-*3
7%)3&,31*’*3#’31349%’2%4"-$%K1)"4%,-3J4%&P6*#"44:.3#’2%J"1*135&37%4*#$.)"4)04"’*#$"#7"#K
"4:M*#$35"#%O"&,4%.’2%-%104’123L1’2"’’2%&%’237*1%55*)*%#’53-1’3)2"1’*)I3J123,1)2%704*#$P
QRSTUDVBG 1)%#"-*3WN"$-"#$*"#-%4"O"’*3#W7:#"&*)1)2%704*#$W1)%#"-*37%)3&,31*’*3#W3,’*&"4
1’-"’%$:
XYZX第 Z期 朱道立等G
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[
随机环境中的生产作业计划问题
