（应用数学专业论文）物流活动中的调度方法.pdf

ab s tra c t a b s t r a c t t h i s p a p e r e s t a b l i s h e s a l i n e a r p ro g r a m m i n g m o d e l f o r t h e l i q u i d lo g i s t i c s d i s t r i b u t i o n t r a n s p o r t a n d o r d e r t r a n s p o r t p r o b l e m 勿 t h e m e a n s o f t h e p r o j e c t n e t w o r k t e c h n o l o g y . t h i s m o d e l c a n n o t o n l y s a t i 吻 t h e n e e d o f t h e p r o d u c t i v e e n t e r p r i s e , b u t al s o r e d u c e t h e l o g i s t i c s c o s t o f t h e t h i r d p a rt l o g i s t i c s e n t e r p r i s e . mo r e o v e r , i n t h i s p a p e r w e al s o g i v e a n o p t i m a l o n - l i n e c o n t ro l m e t h o d , w h i c h c a n d e al w i t h th e l i q u i d l o g i s t ic s d i s t r i b u t i o n p ro c e s s a n d s t o r a g e p r o c e s s w it h t h e fl o w - s h o p s c h e d u l i n g t h e o r y . k e y w o r d s : ma t h e m a t i c al p r o g r a m m i n g ; m o d e l s ; s c h e d u l i n g ; p r o j e c t n e t w o r k s ; l o g i s t i c s a c t i v it i e s 南开大学学位论文版权使用授权书 本人完全了 解南开大学关于收集、 保存、使用学位论文的规定， 同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版 本;学校有权保存学位论文的印刷本和电子版，并采用影印、 缩印、 扫描、 数字化或其它手段保存论文; 学校有权提供目 录检索以及提供 本学位论文全文或者部分的阅览服务; 学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电 子版; 在不以 赢利为目的的前 提下，学校可以 适当复制论文的部分或全部内容用于学术活动。 学 位 论 文 作 者 签 名 : 4 l 斌 年1 1 月 才日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名:学位论文作者签名: 也多 乞 解密时间:年月日 各密级的最长保密年限及书写格式规定如下: 内部 5 年 ( 最长5 年，可少于5 年) 秘密*1 0 年 ( 最长1 0 年， 可少于1 0 年) 机密2 0 年 ( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明: 所呈交的学位论文， 是本人在导师指导下，进行研究工作 所取得的成果。除文中己 经注明引用的内 容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内 容。 对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已 在文中以明 确方式标明。 本学 位论文原创性声明的法律责任由本人承担。 学 位 论 文 作 者 签 名 : -l - 4 0 ) .年.1 1 月才日 第一章引言 第一章引言 现代物流的理念和运作对众多物流企业产生了深远的影响，如何将物流， 信息流和资金流进行全面的整合与有效的控制，从而提升企业的竞争能力，实 现产品供应链的价值和运作的最优化，是第三方物流企业面临的重要任务. 本 文通过某第三方物流企业的信息管理系统的分析与规划， 从中 提出了该企业运 作的四阶段优化控制方法，这对于第三方物流企业的信息化建设具有一定的实 用价值. 我们所讨论的 物流公司 主要是进行散装液体物流，为环渤海地区的一些企 业提供相应的产品.这些液体一般属于危险品 ( 如化学品等) ，而且对温度有严 格要求，并且在保存和运输时间上均有一定限制.为了保证准时，安全，有效 的优质物流服务和贸易咨询服务，该公司在己 有的商品信息平台的基础上，准 备构建高效，优化的电子商务信息管理系统.本文所研究的内容是该信息管理 系统中的决策控制策略与优化方法. 该公司的主要物流业务流程可以划分为四个阶段:阶段1 是订货运输，阶 段i i 是入库加工，阶段i i i 是配送加工，阶段n是配送运输.阶段i 的结束时间 是阶段1 1 的 开始时间， 产品的 仓库储存时间， 根据常规可以 视为一 个常数c ， 于 是阶段i i 的结束时间加上c 是阶段i ii 的开始时间， 而阶段n 的开始时间是阶段 m的结束时间. 时间的控制来自于客户 ( 生产企业) 的需求计划的综合处理. 如 何有效的控制各个阶段的开始时间与结束时间，是保证准时 ( 最早时间) 供货， 降低库存成本( 库存周期) ， 以及尽早收取供货款和延迟支付订货款( 最迟订货) 的重要问题. 由于阶段1 和n均属于运输控制问题，因而在第二章运用 a o n网络技术来 探论.阶段1 1 和阶段1 1 1 是加工处理时间最小化问题， 在第四章运用 f l o w - s h o p 调度论方法加以论述. 第二 章 配送运输与订货运输的 优化模型 第二章 配送运输与订货运输的优化模型 综合全部客户的需求信息，向客户提供准时 ( 最早时间)的，安全的送达 服务， 这样不仅满足了客户的 需求而且可以 尽早收到客户 支付的货款.向 供货 商订货的时间是由 阶段n的开始时间( 由最早完成时间确定的) ， 再根据阶段i i i , i i 和储存时间c ， 从而得到阶段i i 的开始时间， 该时间作为阶段i 的工期， 在阶 段i 采用最迟完成时间调度，目的是降低库存周期，延迟支付订货款，从而降 低物流成本. 由于经营产品的特殊性，因而生产场所的分布和供应商的供货 地点等都与 通常的运输问题大不相同.因 此，运用 a o n( 工程)网络技术【 1 建立配送运输 的最早时间调度模型和订货运输的最迟时间调度模型. 在物流系统中，由于技术过程的要求和实际问题的要求，因而可以假定活 动在处理中 不可中断， 它的处 理时间 是己 知的. 设活动i ( i = 1 , 2 , . 二 ， n ) 的持续时间 为只 z io， p o =p h+ * = 0 虚活动 0和n+ 1 依次表示物流系统的开始和结束活动， ， 设s , 为i 的 开 始 时间， 其中 i 二 1 ,2 ,一 ， n , s , = 。 ， 凡+ ， = d , a 为整个系统给定的周期 ( 工期) . 活动i , j 间的 优先关系可以 采用s s ( s t a r t - t o - s t a r t ) 方式来定义 s , 一 s , _ d m m , ( 2 . 1 ) 其 中 楞 。 z io 称 为 j 相 对 与 i 的 最 小 时 差 ， 式 ( 2 . 1 ) 表 示 j 不 能 在 i 开 始 锣 个单 位时间 之前处理; 若楞 = a，则式( 2 . 1 ) 表示 一个先后约束; 若 0 d 尸 _ s , , ( i , j ) e e s , - 0 , i 。 犷 s o =0 3 ( 2 . 6) minsj. 第二章配送运输与订货运输的优化模型 定 理1 线 性 规 划 模 型( 2 . 6 ) 必 有 整 数 最 优 解s = ( s a , s 1 . s n . 1 ) ， 其 中 s , 几 , i = 0 ,1 ， 二 n+ 1 . 证明 将l p 模型 ( 2 . 6 )中的约束条件记为a s - s， 于是一 a s - e s n , : 一 定 成 立. 于 是 可以 定 义 isn . 1= f a - ie s m . l 若给出最大工程周期， 否赃 最 迟调度l s e s ; 满足lsn . 1 - l s , ? sv i e v , v s 。 s , . 下面不加证明地给出工程中存在时间可行调度与 a o n网络特征的一个结论 习 定理2工程存在时间可行调度的充分必要条件是相应的a o n网 络不含有 正长度回路. 由 于在实际工程中总存在时间可行调度，因而根据定理 2，可以 假定如下 讨论的a o n 网络不含有正长度回路， 这样就保证了时间约束条件( 2 . 5 ) 成立. 为 了 建 立 最 迟 调 度 模 型 ， 需 要 对a o n 网 络g 加 以 扩 充 ， 增 加 一 条 反 向 弧 ( n + 1 ,0 ) 1 赋 予 权凡 . 1,o ， 一 j ， 从 而 得 到 的 网 络 g 称 为 时 间 调 度 网 络 ， 于 是 有 最 大 时 差 d 7 . , = d . 时 间 调 度 网 络 g 的 弧 集 为 e = e u r n 十 1,0 ) . 因 此 订 货 运 输 模 型和配送运输模型依次建立如下: 况 翻艺，:0 ax m s , 一 s , : s , ，( i , j ) e e ， ( 2 . 7 ) s o = 0 ; 第二章配送运输与订货运输的优化模型 s 洲艺1=0 n m s , 一 s , _ s j ，一( i, i ) e e , ( 2 . 8) s o = 0 . 模型( 7 ) 和( 8 ) 的约束条件s , _ q ( i e v ) 会自 动满足的. ，. . .i lsn s 1 )是 模 型 ( 2 . 7 )的 最 优 解 显然，最迟调度 : 最 早 调 度 - i fsn s l ) 是 模型( 2 . 8 ) 的 最 优解. 由 于时 间调 度网 络g + 不 含有正 ls，城 ls0，es0， 一一一- ls邵 长度回路，因而模型( 2 . 7 ) 和( 2 . 8 ) 的最优解也是网络中节点0 至节点 n + 1的最 长路径.因此，为了求出e s l s , ( b pi e v ) ，均可以运用修正标号算法 (l a b e l - c o r r e c t i n g a l g o r i t h m ) ， 相 应 的 计 算 时 间 复 杂 性 为 o (iv ie 卜 “ ， 在 计 算e s , ( v i e v ) 时， 从e s , = 0 开始 逐一计算( 前向 方 式 ) ; 在 计算l s , ( v i c - 均时， 从l s 。开始逐一计算( 后向 方式) . 第三章 f l o w - s h o p 调 度问题 第三章 i o w - s h o p 调度问题 根据生产上的需求和化学液体的安全需要，因而在配送运输之前需要进行 配送加工，在订货运输之后，需要进行入库的加工处理，这两个阶段的加工处 理 类 似 于 fl o w - s h o p 量 换 问 题 的 模 式 ， 该 问 题 的 记 法 5 为 f i p r m . ic _ 因 此 ， 我们运用fl o w - s h o p 调 度论 方法，分析和求解这两个阶段的加工时间最小问 题. 设l, r 1 2， 二 ， i. 为 作 业， m m 2 ,.i m . 为 设 备( 机 器) ， 其中i k ( k = 1 ,2 , . . .n ) 依 次 在m m 2 , .i m . 上 加 工 处 理，2k 在 m ， 上 的 加 工 时 间 为p ,. , u = 1 么 二 川 设 。 = i, 几 一 人 ， 设 备 顺 序 为m 从.， . m . ， 可以 构 造一 个网 络味， 其 中 作 业 在 从上 的 工 序 对 应 于 节 点 ( ik . .1 ) ， 相 应 工 序 的 加 工 时 间 为 p , ., ， 节 点 (2k . 1 ) 通 向 节 点 (2k j 川和 ( k . 1 + 1 ) 有 弧 连 接 ， 其 权 均 为 p ., .i 引 入 一 个 发 点 (io 1) 和 一 个 收 点 (2. a . m ) ， 其 中 ( 0 1) 通 向 ( , .1 ) 的 权 为 p , , = 0 , (i. m ) 通 向 (0 - i m ) 的 权 为 p ,. , 网 络 流 风 ( 图3 . 1 ) 中 ， 从 起点 ( 1 ,i ) 至 节 点(-,m ) 的 各 条 路 径中 ， 最 长 的 加 权路 径( 关 键路径) 的 长 度即为口 = 2 1 2 2 二情况下的 完 成时间m( m ) ， 关 于 完 成 时间m( m ) 的 计算有如下结论. 定 理 3设 c (r 一 s , 。 一 v ) 为 节 点 ( l ) 到 (s v ) 的 关 键 路 径 的 长 度( 工 序 i,， 至 i , . )，即 序 列 i i - 1 1 . . . i . 在 城 m . . v . . m ， 上 的 总 流 经 时 间 ， 则 c ( r 一 s , 。 一 v ) 的 表达式如下: 3. 了、 ，任illj 声 代 c (.一。 一 。、二 、 .， k=u 二 k=w5l w, . p ,_.， 十 i k = w . . x 1 二 . 卜吐 c ( 7 一 s , u 一 y ) - m ax 护 自. 几刁 “人 今补招小1 .刻共p x, ， 十 户p , , . i +. .- 乙p , . - i + 乙p xx, 卜 l. = . 二 、 - n + = . - x ( 3 2) 第三章 f l o w - s h o p 调度问题 4 4 4i _ 1 i . m ,一 1,1 ) -+ ( n ,l ) 妙 杏 _ 杏 杏杏 m , ( 1 ,2 ( 2 ,2 ) - - (3 ,2 ) - * . . . - (n 一 1 ,2 - - (n ,2 杏杏杏杏杏 m , ( 1 ,3 ) (2 ,2 ) - ), (3 ,2 卜. . . - ) -( n 一 1 ,2 卜(n ,2 ) 杏杏毒杏杏 介.* 嵘丫 i p q 1z .m - 1) - (3 .m - ih. . . 。 一 ， 一 。， 。 杏杏杏 呱 仅 m 曰2 , m 曰3 , m 卜. . . - ( n - 1, m 曰m m ) 图 3 . 1 网 络g d 图 分 析考 虑 吼的 子 网 络 图( 图3 .2 ) ， 记 为 g ( n , 刁， 其 中 n 为 节 点 伪 ， 劝 的 集 合 ， (r _ q 5 s , u 5 k :5 v ) ， 设 ，9 ， 为 ( q , k ) 的 最 早 的 开 始 时 间 (r s g s s , u s k _ v ) , 如， 一 。 ， 于 是 c (r 一 s , 。 一 v ) = t , . + f ,. ， 因 此 ， 要 证 明( 3 . 1 ) 式 ， 只 要 证 明 下式即可 飞!月 声 p.， ，艺为 + 声 p，.- is,一 、 knax _ 。 ly- pr,t + 屋 p%.,k + .+k =o k=. kaw_ 一 p , , . ( 3 . 3 ) 下面通过双重数学归纳法，分四步来证明 ( 3 .3 )式，前两步先对 r _ a _ s ,u _ # _ v 证 明 。 ， ， ， 满 足( 3 .3 ) 式 ， 后 两 步 假 设 对 任 意 的 (a , /3 ) ( 3 .3 ) 式成立， 并由 这个 假设 得出t . . l.a . 。 也成立. 第三章 f l o w - s h o p 调度问 题 (r ， u ) * i (r , u + l ) * 毒 (r + l ,u ) ” 毒 仓 + 1 ,u + 1 )” i - + ( s , . ) 41 。( s , u + 1) 毒 (1 . v ) - - 31 - ) 毒 。 (s . v ) i 凡， 图3 . 2吼的 子网 络图 证 明第 一 步由 于 . l,. = 1 . + p . = p , . ， 根 据( 3 .3 ) 式 的 形 式 t r + 1 ,: 二m a x u =w, =u p i u + ， 、 ，。 ! 一 ， 、 ，.，: 一 ， 、 ，。 ， 因 而 ， 对 于 ，+ .，( 3 .3 ) 式 成 立 . ( 相当 于 a = l ) 假 设( 3 .3 ) 式 对 于 q ( r q ， ) 成 立， 即 t q . = m a x ，=乓= 气d乡 件凡一 1二.认 ， 十 p . + + 入 ， 一 与 p ,. ， ( , = u) 妇艺i= 一一 于 是 有 (q , u 卜 17 - 十 ,u ) , tq.1， 二 ，qr + p o， 一 l r p 41 , 即式 ( 3 . 3 ) 因 此 ， 1 q . . 满 足( 3 .3 ) 式 . . 第 二 步由 于 t, 1 = t , ， 十 几 ， = p ,， 而 且 1. = t , ,. . 1 ， 所以 此 时( 3 .3 ) 式 的右端为 ， m a x 1 p s r + p ,. 1 一 p , y .1 = p ,. 第 三章 f lo w - s h o p 调 度问 题 因 而 ， 对 于 t , , , ( 3 .3 ) 式 成 立 . ( 相 当 于,6 = 1 ) . 假 设( 3 .3 ) 式 对 于 t.1 u j v ) 成 立 ， 即 、 = 二 巨一 p = p4k,k=.一 j,s- i一r) 于是有， t +一 l,， 十 p .l = 艺 ， 、 ， ， k二. 即式 ( 3 . 3 ) . 因此， 均成立f 第三步 t 1 + ， 满 足( 3 .3 ) 式 . 由 归 纳 法 可 知 ， 对 任 意 的 j ( u j - v ) ( 3 .3 ) 式 假 设 对 于t + 1,， 和 .1 + 1 ( 3 .3 ) 式 均 成 立， 即 r q + l ,i = m ax u _ r , s w s s w 句 全 p l,， 十 里 、 :， 十 .，. 十 r4 k=. k = w , 女 二 、2 r1 十艺 p ,a ,l 含 = 、 一 r , ，.j 沐 几 i . ., + 1 = n】 月x . 气 气 h s . 、. . 匀+ l巨 * 奥 :、 二 1 ps .k + lr p ,h,k + .+ p, k + .k=. k=w, k=w,i n k-w, 一 代,1 + 1 ， 将 上 面 ， q + 1.1 和 ， 。 + ， 的 表 达 式 代 入际 1,1 + 中 ， 有 ,q+l,l+l = m a x 沁.l 十 p p l.l lq.n 。 十 +，1 ( 3 . 4 ) ， ，.蕊二口十.ij 、几!少 了 、.，.产 弓艺脚 r.月j、. 了!月卫卫.、 二 二r nax . 5 w , 一 w o s 1 凡. .1 + l nax “、一 匀十 . p 声 +p , ， ，+ ， 、艺衍 !、.， 子了.吸、 另外，( 3 . 3 )式还可以写为 1 a 1-1 =m ax . . 尹 . ， _ 声 . 甲 少 +l l r p ,. 一 十 l r 凡 ， 十 一 ，* 孟二.i=w l r 凡 _ + l r 二 “ ， 盛 = 二 一 p，.,p l . 川 ，月1.j 凡 第三章 f l o w - s h o p 调 度问 题 比 较( 3 .4 ) 和 ( 3 . 3 ) ， 由 于前式是从. s . , ( 3 . 3 ) 、s i 与. s w , t s 、 : ， ， : 中 选 最 大， 后式是从， 气 ， 、 : 二 ， 。 s j + l 中 选择 最大， 包 含了 前 式的 两 种， 因 而 ( 3 . 3 ) 的 值 不 小 于 ( 3 .4 ) 的 值 另 一 方 面 ( 3 .4 ) 式 的 值 是 在w q _ j j + 1 时 达 到 ， 则 ( 3 .4 ) 的 第 一 个 最 大 值 是 这 样 的 情 况 ; 再 有 即 否 则 ( 3 .3 ) 式 值 在 w 9 = j + 1 时 达 到 最 大 值 时， ( 3 .4 ) 式的 第 二 个 最大 值是， w , ， ， ， s . 、s j 十 1 这种 情况. 于 是无论 ( ” ) 在w q _ j j + 1 时 或w q = j + 1 时 达 到 最 大 值， 相 应 的( 3 .4 ) 式 也 达 到 相同的值，因此两式的值相等. 第 四 步对 于 t q .j ， 先 令 j = u , 则 根 据 第 一 步 可 知 ， 1 q . , q = r , r + l , . . . , s _ l 时( 3 .3 ) 式 均 成 立 ， 另 外由 第 二 步 有t, : 成 立 ， 以 及 t , . 1 ， 根 据 第 三 步 有1 , . i. + ) 成 立 ， 再 由 1 - 2， 可 知 1,+ z, + : 成 立 ， 如 此 等 等 ， 有 t q , + 1 (r _ q !5 s ) 满 足( 3 .3 ) 式 . 令 j = u + 1 ， 可 知 t q , + , (r 5 q :5 s ) 满 足( 3 3 ) 式 ， 以 及 tr, + z 成 立 ， 按 照 上 面 的方法可以 推出t q , + z ( r _ q :5 s ) 满足( 3 .3 ) 式. 利用数学归纳法可得 t q , (r 0 , i = 1 ,2 ,., n ; j = 1 , 2 ,., m ) ， 问 题 的 最 优 序 列 不 变 ， 而 且 制 造 时 间 由 原 来 的 m (- o ) 变 为 a m ( m o ) + ( n + 。 一 1 ) 6 . 证 明 设 a i 为 f i p r 7 n u ic 问 题 的 一 个 最 优 序 列 ， 则 按 序 列 。 = 112 . .1 和 顺 序 m i , m 2 , . , m . 的 制 造 时 间 为m ( w * ) , 相 应 的 网 络 记 为 气二于 是 存 在 一 条 从发点 到收 点的 路 径p ( x , , x ; ， 二 ， 心、 ) 使 得( 1 !5 对 石 .， . 心一 n ) m( 必 . ) 二 且 勺 1 几丫 1 2 1 x l “x 一 _ 1 p o+ 艺p ,2 + 十艺 只 一 ， +艺p , r =r _ , 矛 =x . _ 1 = i p ,j + 全 p ,.2 ， + 艺 p ， ， r = 1 r = r ; i - 二 一 ( 4 . 1 ) 而 且 有m ( m ) 0 , b ? 0 , = 1 ,2 ，二 ， n ; j = 1 ,2 ,., m ) , 得 到 的 网 络记 为 g 。 二根 据 定 理3 有 m( 口 . ) = .。1m ax ， 全 a (p ,.i + ， ) + 全 a (p , .z + b ) + .+a ( p ,， 一 ， + b ) + 艺a ( p , + b ) 第四章配送加t与入库加工调度 二 . m ax 。 . 、“ : - _ _ , - l p , , + x , - a b 十 一 + a 艺几 ， +( 卜 卜枯_ 1 、 一:一 )-abi 几艺问 = a -m 伽 ) + ( n + m 一 ，) a b . -leseseses月j 声. p， = a . m a x i s r , s i , s 卜. : 5 .1 p , ,i + 十 i 1 = 1 1 -, 十 a b - ( x , 一 1 + 1 十 x 2 - x i + 1 十 十 n 一 x . _ , + 1 ) ( 4 . 2 ) 因此， 利用式( 4 . 1 ) 和( 4 . 2 ) 可知，b w 。 0 ( 1 , 2 , .， ., n ) ， 都有 m( m ) = a . m ( m ) + ( n + m 一 1 ) a b - a . m ( m ) + ( n + m 一 1 ) a 6 = m ( rv ) . 证毕. 定理5 设 序 列= ti i q . 可是顺序为m mz , . ., m . 下的 最 优序列， 则逆 序 列m , = 稿. 可是 顺 序为m , m_. . , m : 下的 最优序 列， 而且m( w) = m ( w . ) - 证明设m( rti ) 是最优序列g ) 二 ( j 2 . .7 在顺序m i m 2 , . ., m. 下的 制造时 间 ， 相 应 的 网 络 记 为 乌 由 于 m ( to 0 ) 满 足 式( 9 ) ， 因 而 存 在 一 条 从 发 点 到 收 点 的 路径p ( x ; , x z , . . , x . - , ) 使得( 1 x , - x ; 5 . . 5 x . - , 5 n ) 毛艺峋 十 即 今自间 m( w 0 ) = m ax i 5 i , 5 z s s . , _ , p ,z 十 + l r p i + l . p . l = r _ , 1 = i _ , 一 至 p , t + i = t 1 = = , 几 :2 十 ，二 十 艺 p o i ( 4 . 3 ) 在 网 络 g 。 上 ， 将 其 所 有 的 弧 全 部 反 向 ， 而 且 对 发 点 ( n + l , m ) 到 ( n , m ) 的 弧 ， 设 其 权 为。 ; ( 1 ,l ) 到 收 点 ( 0 ,1 ) 的 权 ， 设 为 p t,t ， 网 络 上 其 他 弧 的 权 均 不 变 . 这 样 得到的网 络记 为g , ， 这是序列为叭= 唁 _ ; .ji， 顺 序为m . m . - i , . . . , m: 的 工 序 网络.取一条从发点到收点且与式( 4 . 3 ) 相对应的路径p ( z ,- t . x , - z ， 一 ， x i ) , 1 _ m( w 0 ) . 于是推出与式( 1 2 ) 相矛盾. 证毕. 第五章b a b算法 第五章日 朋算法 由 于 f ip r m 川 c _是n p 一 难 伽- 3 ) 问 题 7 1 ， 因 而 当 系 统 处 于 离 线 时 ， 可 以 采用b a b算法求出最优序列w;当系统处于在线时，则根据定理4 ， 对配送加 工问题的工序时间作线性变换，而最优序列仍为口，从而可以实现在线配送加 工控制.同理，入库加工处理的工艺路线与配送加工的工艺路线基本上是反向 的，因而可以利用定理 5 ，对入库加工使用最优序列口的反向序列实现在线控 制. 因 此， 运用fl o w - s h o p 调 度论的 方法实 现了 配 送加工 和入 库加工 ( 处 理) 的 优化控制. 第一节活动新节点搜索方法: 第 一 步 设 所 有 可 行 序 列 对 应 于 截 树 的 根 节 点 j o ， 先 分 解j o 为认 有 n 个 节 点 ， 相 应 下 界 为l b , 认工 i = , - -, n . 第 二 步咧劝一 m in l b , ( j , ) ,_,; .r对 于 节 点 j ; 完 全 分 枝 为 (n 一 1) 个 节 点 ， 且 计 算 下 界l b , ( j , l i = 1 , - 二 ， n 一 1 . 第三步 在; 级上(r = 1 ， 一 ， n - 0 分 解的伪 - r + 1 ) 个 节点是来自 父节点 j ; - , l b , 以1 l 冲: ) - 其中l b (j ,-,) 一 ，1m in _2 l b , (j ,-, ) ，计算相 i = 1 , - . - , n - r + l然 后 对 不 再 做 完 全 分 枝 t一 1m in _ ， l b , (j , ) , 且 计 算 相应的 下 界l b , ( j , ) . 第四步 j - 7 ( i , . . .i ce - 2 i k ) i 设r = n 一 2 l b (j - z )对j - 2 完全分枝，由 j - 1 ( z . . .,n - z zt ) 来 计 算la i l ， 其中 较 小 者 记 为厂， 这 是一 个可 行 解， 是目 前 得到的 一 个 最 优解.f o 的 最小 上界， 第五步 在活动新节点搜索中，从当前看，若存在一个最近的尚未分枝的 节 点 j , ， 而 且l b ( j , ) - 厂( r = 1 ,2 , . . . , n - 1 ) ， 则 返回 到 第五章 b a b算法 第五步，否则执行第七步， 第 七 步 对 具 有 最 小 下 界 的节 点j , 完 全 分 枝， 即 分 枝出 ( n - r + l ) 个 节点 ( 第三步) ，而且计算相应的下界，然后转入第六步. 第二节标准下界 设1 1 , 1 2 , . . . ， t n 为要加工的工件，其中己 排好序的 前; 个工件 ( 序列长度) 记 为j , ， 其 余 的 记为又( 有n - ， 个工件) ， 则 有归 纳法 可证明 下 界公 式如下: l b ( j , ) =，民 (j ,)+ t 矿 月 l瘾 子 ; p ,t + 瞥 q - k . 1 其中 去 称 为 ; 一 前 子 列 ， q口 r ) 是 依 照j , 序 列 在 m 。 上 的 完 成 时 间 ， 又 是 ， 一 ; 个 工件构成的集合. 设 。 = 毛 碑 +l :， 礼 ， 则 有( 任 何 子 序 列 ， 一 ; 个 ) m ( - , ) ? l b (j , ， 在 分 枝 搜 索中 ， 可 以 用l b ( j , ) 来 确 定 是 否 删 去 该 分 枝( 即 是 否 有 必 要 继 续 分 枝 ). 定理 设， = i l , i z , 二 、 1 ， 则 f l o w s h o p问 题的制造时间 ( n x m) 为 m 位 ) = l b (j _ , . 第三节日 阴算法的程序实现 使用b a b算法求最优序列w的实现步骤如下:( i )b a b的分枝搜索方法 采用的是活动新节点搜索方法 6 , 踢一 、 :( i i )下界的计算公式采用标准下界 c l b 6 , p 2 1 2 -2 14 1 - 分枝定界法的程序实现过程中， 使用一个最小优先队列来记录活节点，队 列中 每个节点的 类型为m i n h e a p n o d e 。 每个节点包括如下区域: x : 从1 到n 的整数排列， 其中x 0 1 = 1 ; s : 一个整数， 使得从排列树的根节点到当前节点的路径定义了旅行路径的 前缀x o :s 1 ， 而剩余待访问的节点是x s + l : n - 1 j ; c c :旅行路径前缀，即解空间树中从根节点到当前节点的耗费; i c o s t :该节点子树中任意叶节点中的最小耗费; r c o s t :从项点x s : n - l 1 出 发的所有边的 最小 耗费 之和。 第五章b a b算法 当 类型为m i n h e a p n o d e ( t ) 的数据被转换成为类型t时， 其结果即为l c o s t 的值。 程序执行过程中首先生成一个容量为1 0 0 0 的最小堆， 用来表示活节点的最 小优先队列。活节点按其l c o s t 值从最小堆中取出。接下来，计算有向图中从每 个顶点出发的边中 耗费最小的边所具有的耗费m i n o u t 。 如果某些顶点没有出边， 则有向图中 没有旅行路径，搜索终止。如果所有的顶点都有出 边，则可以启动 最小耗费分枝定界搜索， 根的孩子作为第一个 e 一 节点，在此节点上， 所生成的 旅行路径前 缀只有一个顶点 1 ，因此 s - o , x 0 1 = 1 ,x l :n - 1 ) 是剩余的 顶点 ( 即顶点 2 ,3 ,. ,n ) 旅 行 路 径 前 缀1 的 开 销 为0 , 即 e c = o ， 并 且 ， ， 一 艺 几 . m in o u s t il , 在程序中， b e s t c给出了当前能找到的最少的 耗费值。初始时，由 于没有找到任 何旅行 路 径， 因 此b e s t c 的 值被设为n o e d g e . 下面是使用c 语言编写的程序源代码 t e t n p l a t e t a d j a c e n c y wd i g r a p h q : :b b t s p ( i n t v 1 ) 11 旅 行商问 题的 最 小 耗费 分枝定 界 算 法 11 定义一个最多可容纳1 0 0 0 个活节点的最小堆 mi n h e a p h ( 1 0 0 0 ) ; t mi n o u t = n e w t n + l ) ; 11 计算m i n o u t i l 二 离开顶点i 的最小耗费边的耗费 t m i n s u m = 0 ; / / 离开顶点i 的最小 耗费边的数目 f o r ( i n t i = 1 ; i =n ; i + + ) . t mi n = n o e d g e ; f o r ( in t j = 1 ; j = n ; j -) i f ( a i l j j ! = n o e d g e i f ( m i n =n o e d g e ) r e t u r n n o e d g e ; / / 此路不通 mi n o u t i l = mi n ; mi n s u m+ =mi n ; ) / 把e 一 节点初始化为树根 第五章b a b算法 mi n h e a p n o d e e . x f o r ( i =n e w i n t =0 ; i n ; i + 十 ) e ; n ; .=l e .x i +1 ; e . s e. a ; = 0 ; /局部旅行路径为x 1 : 0 其耗费为0 mi n s m n ; 0;= t b e s t c = n o e d g e ; / / 目 前 没 有找 到 旅行路 径 / 搜索排列树 w h i l e ( e .s n - 1 ) / / 不是叶子 i f ( e .s 一n - 2 ) / / 叶 子的 父节点 / / 通过添加两条边来完成旅行 /l 检查新的旅行路径是不是更好 i f ( a e .x n - 2 e .x n - 1 ! = n o e d g e ecc=悦s t c ; e . l c o s t 二b e s t c ; es 十 十 ; n . i n s e rt ( e ) ; e x e l s e 第五章 b a b算法 ( / / 产生孩子 f o r ( in t i = e .s + 1 ; i n ; i+ + ) i f ( a e .x e .s j j j e .x j i j l = n o e d g e ) 11 可行的 孩子， 限定了路径的耗费 t e e= e .c c + a e .x e .s e .x i ) ; t r c o s t =e. r c o s t 一 m i n o u t e .x e .s ; tb二cc i f (b “ b e s t c 十 代 。 丈 / / 下限 b e s t c 子树可能有更好的叶子 把根保存到最大堆中 /l mi n u e a p n o d e n ; n . x 二 n e w i n t 【 川; f o r - ( i n t j= 0 ; jn ; j +) n .x j = e .x j ; n . x e n . x i n. c c ns s + 1 = e .x i ; = e .x e . s + l ; 二c c ; n. l c o s t n. r c o s t +1 ; b ; r c o s t ; / / d e l e t e ri n s e r t ( n ) ; 结束可行的孩子 e .x ; / t ry c a t c h 悦s t c 对本节点的处理结束 谧 h . d e l e t e mi n ( e ) ; ) ( o u t o f b o u n d s ) / / 取下一个 谧 b r e a k ; ) / l e 一 节点 没有未处理的节点 一n o e d g e ) 第五章b a b算法 r e t u rn n o e d g e ; 1 1 / / 将最优路径复制到v l : n 肠 r ( i v i + l ( t r u e ) tn ; e . x i ; 没有旅行路径 中 i + + ) 0;= 释放最小堆中的所有