（计算机软件与理论专业论文）港口集装箱装卸设备联合调度问题的算法研究.pdf

港口集装箱装卸设备联合调度问题 的算法研究 专业：计算机软件与理论 硕士生：黎俊瑜 指导教师：郭嵩山 摘要 一般来说，港口的集装箱调度过程都需要多种设备的共同参与，密切配合， 才能带来较高的装卸效率。因此就产生了一个在港口集装箱物流过程中具有重要 实际意义的问题：港口集装箱装卸设备联合调度问题( i n t e g r a t e ds c h e d u l i n g p r o b l e mo f t e r m i n a lc o n t a i n e rh a n d l i n ge q u i p m e n t ) 。但是目前大部分研究都是针 对单种设备的独立调度问题进行优化，而在联合调度方面的研究还相当少。 本文针对集装箱装卸设备的联合调度问题做了相关研究，首先对该问题在各 种特殊情况下的计算复杂性进行了分析，并针对处理时间均为单位时间的情况给 出了多项式算法，同时利用遗传算法这一现代优化技术，给出了求解一般问题的 启发式算法，并基于关键路径和右平移调度方案对算法做了进一步改进。根据作 者结合计算机仿真模型所做的实验分析，这一启发式算法能够在相当短的时间内 得到与最优解比较接近的近似解。 关键字：集装箱物流，联合调度，遗传算法，关键路径，右平移调度方案 r e s e a r c ho ni n t e g r a t e ds c h e d u h n gp r o b l e mo f t e r m i n a lc o n t a i n e rh a n d l i n ge q u i p m e n t m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：j u n y ul i s u p e r v is o r ：s o n g s h a ng u o a b s t r a c t g e n e r a l l ys p e a k i n g ，d i f f e r e n tk i n d so fh a n d l i n ge q u i p m e n ta r er e q u i r e dt ow o r k c l o s e l yw i t he a c ho t h e rt op r o m o t et h ee f f i c i e n c yo f t h el o a d i n g u n l o a d i n gp r o c e s sa ta c o n t a i n e rt e r m i n a l t h a t sw h yt h ei n t e g r a t e ds c h e d u l i n gp r o b l e mo ft e r m i n a l c o n t a i n e rh a n d l i n ge q u i p m e n tc o m e st ot h er e s e a r c hf i e l do fc o n t a i n e rl o g i s t i c s b u t a c c o r d i n gt ot h ea u t h o r sk n o w l e d g e ，t h er e s e a r c h e sa b o u tc o n t a i n e rl o g i s t i c sm a i n l y f o c u so nt h eo p t i m i z a t i o np r o b l e mo fas i n g l et y p eo fe q u i p m e n t ，a n dt h e r ea r eo n l y f e wp u b l i s h e dr e s u l t so nt h ei n t e g r a t e ds c h e d u l i n gp r o b l e m i nt h i sp a p e r , t h ea u t h o rc o n c e n t r a t e so ni n t e g r a t e do p t i m i z a t i o no fd i f f e r e n tk i n d s o fe q u i p m e n t f i r s tt h em o d e la n dc o m p l e x i t ya r o u n dt h i sp r o b l e ma n do t h e rr e l a t e d o n e sw i l lh ed i s c u s s e d ，a n dap o l y n o m i a lt i m ea l g o r i t h mw i l lh eg i v e no u tt os o l v et h e p r o b l e mw h e na l lt h ee q u i p m e n tp r o c e s s i n gt i m ei su n i tt i m e t h e nf o rt h eg e n e r a l p r o b l e m , t h ea u t h o rf i r s tp r o p o s e sah e u r i s t i ca l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m , a n dt h e nm a k e sf u r t h e ri m p r o v e m e n tw i t ht h eh e l po fs o c a l l e d c r i t i c a lp a t ha n d r i g h t - s h i f t e ds c h e d u l e a c c o r d i n gt oe x p e r i m e n tr e s u l t sb a s e do ns i m u l a t i o nm o d e l ， t h i sa l g o r i t h mi sg o o de n o u g ht op r o d u c en e a r - o p t i m a ls o l u t i o n si nar e a s o n a b l et i m e k e y w o r d s ：c o n t a i n e rl o g i s t i c s ，i n t e g r a t e ds c h e d u l i n g ，g e n e t i ca l g o r i t h m , c r i t i c a lp a t h ， r i g h t - s h i f t e ds c h e d u l e 1 1 引言 在集装箱物流领域，港口集装箱装卸设备联合调度问题( i n t e g r a t e ds c h e d u l i n g p r o b l e mo fc o n t a i n e rh a n d l i n ge q u i p m e n t ) 是一个具有广泛的实际应用背景的问 题。 一般来说，集装箱在港口的装卸，需要经过多个工序，每个工序都需要由不 同的设备来完成。以集装箱从港口的仓库搬出直到在码头装运上船为例，首先必 须由仓库跨车a s c ( a u t o m a t e ds t a c kc r a n e ) 从仓库中把集装箱搬出并交给自动运 输车a g v ( a u t o m a t e dg u i d e dv e h i c l e ) ，再由a g v 运到船舶停靠处的货物装卸点 交给龙门吊车q c ( q u a yc r a n e ) ，然后由q c 将货物吊装上船。至于集装箱从船上 卸载到港口仓库的过程则刚好相反。因此要提高整个港口的装卸效率，必须考虑 这些不同类型的设备的联合调度问题，以尽量使这些设备彼此之间充分配合，减 少因为彼此之间相互等待而造成的时间浪费。 人们已经对港口集装箱调度的相关问题进行了相当深入的研究，但是从目前 已有的文献资料来看，大部分的研究都只是集中在某种单独类型的设备的调度上 面，如a g v 的调度【l 】等，而综合考虑多种设备的联合调度的研究还相当少。 本论文将针对多种集装箱装卸设备的联合调度问题来加以研究，考虑到问题 的时间复杂性( 文献 2 】已经证明了这个问题是n p h a r d 的) 和实用性( 花费大量的 计算时间来得到最优解的做法不符合实际调度的时效性需要) 方面的因素，本文 的目标不是求解问题的最优解，而是考虑通过遗传算法等现代优化技术来得到比 较好的启发式算法，在合理的计算时间使得算法的解尽可能接近最优解。 第1 章概述 从2 0 世纪6 0 年代开始被应用以来，集装箱作为一种标准化的运输方式很快 普及到世界各地的港口。几十年来随着全球贸易的迅猛发展，集装箱运输也已经 逐渐成为全球货物运输的主要方式。据估计现在全世界6 0 以上的船运货物都是 通过集装箱来进行运输的，在某些经济发达国家这一比率更是高达1 0 0 【3 】。 快速增长的集装箱运输业极大地增加了货物在各港口间的流通量，从而也对 港口的货物装卸效率提出更高的要求。一方面港口的建设需要投入大量的资金， 集装箱的装卸所用的设备价格相当昂贵，因此在设备数目上面不可避免地受到限 制，如何更有效地利用这些设备，是港口经营者不容忽视的问题；另一方面是现 代船舶的货物运输能力始终在不断增长，到目前为止一艘大型船舶的装载货物重 量最高已经可以达到8 0 0 0 1 0 0 0 0 t e u ( t w e n t yf o o te q u i v a l e n tu n i t ，集装箱的容量 单位) 。船舶容量的增加，必然给港口的货物吞吐带来更大的压力。第三方面是 不同的港口之间存在着剧烈的竞争，特别是在某些地区同时存在多个世界级的大 型港口，例如欧洲的鹿特丹，阿姆斯特丹，汉堡，和亚洲的香港，新加坡等地， 竞争尤为激烈。这就促使港口要尽可能提高货物吞吐效率，降低费用，以吸引 更多的船运公司选择本港口。 因此，通过对港口集装箱装卸设备的调度计划进行优化，提高装卸效率，一 方面可以缩短船舶在港口的停靠时间，减少停靠所带来的巨额开支( 大约1 0 0 0 美 元小时尸，从而对船运公司产生更大的吸引力；另一方面也可以增加港i ：1 在相 同时间内的货物吞吐量，从而为港口带来更多的利润。另外，如果将集装箱装卸 设备的调度优化算法集成到港口仿真模型中，对港口的运营情况进行计算机仿 真，则还可以在港口的布局设计等方面为港口的设计者和决策者提供有价值的参 考信息。 由于集装箱调度的重要实际意义，人们对集装箱调度过程的相关问题进行了 大量的研究。总的来说研究可以分为两个方向，一是对调度过程中整体或者部分 的决策问题( d e c i s i o np r o b l e r n ) 进行研究，二是根据决策问题的研究成果，结合特 定港口的实际情况，建立仿真模型对港口运作情况进行模拟和分析。 完整的港口的集装箱物流过程，包括船舶停靠，集装箱的装船卸船，集装箱 从船舶到码头仓库的运输，集装箱在仓库的排放，以及陆路交通工具对于集装箱 的转运。整个过程每一个步骤都具有其研究价值，因此在港口的集装箱物流领域， 包含了众多的决策问题以及相关研究。有多篇综述性的文章 3 a , 5 】都根据港口集 装箱物流的流程对相关的决策问题进行了详细的分类，并且还对每一类的决策问 题都介绍了相关的研究文献。另外文献 5 】还首次将这些决策问题按照战略性 ( s t r a t e g i c ) ，战术性0 a c t m a l ) ，和操作性( o p e r a t i o n a l ) - - - 个层次来加以划分，以说 明不同的决策问题对于港口运营的影响程度。 在对于具体决策问题的研究方面，大部分的研究都集中在对于集装箱物流流 程的某个阶段，或者说对于某种调度设备单独进行考虑，然后分析在要达到一定 效率要求的前提下如何使设备数量尽可能少，以及在确定设备数量的情况下如何 进行调度以使得效率达到最高。采用的方法包括建立混合整数规划模型，转化为 a t s p 问题( a s y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m ，非对称旅行商问题) ，束搜索 ( b e a m s e a r c l l ) 和网络流算法等传统方法以及遗传算法等现代优化技术。针对a s c 及类似的跨车( s t r a d d l ec a r r i e r ) 调度问题进行研究的论文有【6 和 7 】等，而论文 8 】 和 9 等则是考虑a g v 的调度问题，至于在q c 调度这一方面，比较有影响的论 文则包括【l o 】和【1 1 】。另外值得一提的是文献 1 通过抽象的方式将不同的设备加 以统一，然后提出了一个比较一般化的集装箱装卸设备调度问题框架，可用于求 解不同类型的单种设备调度问题，具有较好的通用性。 在多种装卸设备的联合调度问题方面，关于决策优化问题的研究成果相当 少。m e e r s m a n s 和w a l g m a n s 在文献 2 】中首先是采用分支定界( b r a n c h a n db o u n d ) 的方法进行求解，然后再用启发式的束搜索( b e a ms e a r c h ) 方法来加以改进。在 m e e r s m a n s 的另一篇文章【1 2 】中，则通过实验将b e a ms e a r c h 方法和若干分配规则 进行了比较，得到了与文献【2 】类似的结果。在该作者的博士论文【1 3 】中涵盖了前 面两篇文章中的研究成果。 尽管考虑整个港口的决策优化问题的研究还比较少，但是利用仿真模型对港 口运作情况进行分析的文献则相对较多。如d u i n k e r k e n ，o t t j e s 1 4 】结合鹿特丹港的 实际情况建立仿真模型来分析a s c 、a g v 、q c 等设备的数目和操作速度对码头 装卸效率的影响， 而s h a b a y e k ，y e u n g 1 5 】贝0 通过仿真模型对香港葵涌货柜码头的 运作情况进行预测，并将预测结果与实际数据进行对比；h a r h m 衄【1 6 】则提出一 个能够生成比较符合港口实际运作特点的数据的方法，可以用来作为其它仿真模 型的数据来源，也可以用于验证决策优化算法的有效性。 本论文主要研究港口集装箱装卸过程中的多种设备联合调度问题，在结构上 可以分为六部分。第一部分是对问题的概述和介绍目前已知的研究情况，第二部 分则给出具体的问题描述和相应的数学模型；第三部分是对问题的复杂性进行分 析，并且对特殊情况下的问题求解；第四部分是采用遗传算法来对一般情况下的 问题进行求解，并给出两个基于关键路径的改进算法；第五部分则是通过结合仿 真模型的实验对算法效果进行比较和分析。第六部分则是对本文的总结。 2 1 港口的布局 第2 章问题描述 v e s m l 蚕 ll 胗一咖 夕 。：露叵霎 。露孑口、j，疆 qu a y c m m 。 ，j 。口 目删删 螂婚1 1 a g v a r e a 目 。 。扩 口 r - -l j 7 -r - - k r r - _ 。_ 。- 。_ _ h f = 一 。_ 。_ 【_ _ _ 。_ 。_ 一 l _ 一 _ _ _ i - 一 _ _ = =l _ 一= - _ - 一 - 。一= _ _ l 一_ _ _ _ _ 隧 - 。_ _ _ _ _ _ _ 一 _ _ 一 鲤 滋 i 囹 s l：k “ 8 庙r i l h s i 口e ac 殛 甄 燮 蕊 圈_ 匦 蕊i 鲤 爱 避 圈 = = = _ _ 一 = = 圈 _ _ - 。一 f - - 。_ = =- _ _ - _ _ _ = = =_ _ 图2 - 1 鹿特丹港货柜码头布局示意图 本论文将根据鹿特丹港的情况来进行研究，上图就是鹿特丹港口的货柜码头 布局示意图脚，整个码头可以分为三个区域，在图中由上至下依次为用于停泊船 只的船坞区，用于自动运输车在码头和仓库间来回的运输区，和用于在港口暂存 集装箱的仓库区。此外一般来说在仓库区的另一侧还有用于转换陆路运输工具的 转运区，但是因为这不属于本论文的研究范围，因此在此忽略。 如上图所示，货柜码头所使用的装卸设备主要有三种，龙门吊车( q u a yc r a n e ， q c ) ，自动运输车( a u t o m a t i cg u i d e d v e h i c l e ，a g v ) ，和仓库跨车( a u t o m a t i cs t a c k c r a n e ，a s c ) ，恰好分别对应码头的三个区域。龙门吊车的作用主要是与停泊的 船只连接，将集装箱吊装上船或者从船上吊出。而自动运输车的作用就是负责集 装箱在码头和仓库之间的运输。从图中可以看到，a g v 是沿着一个环形的路线 在码头和仓库之间来回，当然不同的港口布局下a g v 的经过路线会有所不同。 仓库区根据存放货物的种类和性质等划分为很多长条形的仓库，每个仓库都分配 有一台专门的仓库跨车，用于集装箱在该仓库的排放取出。根据文献 1 4 1 所提供 的数据，一个典型的货柜码头拥有7 台q c ，3 2 台a s c 和5 0 台a g v ，为一艘 船进行装卸的过程一般用到4 台q c ，2 7 台a s c 和4 0 台a g v 。 2 2 研究对象和问题假设 1 ) 为了降低问题的复杂度，本论文的研究对象是一艘货船的集装箱装载过程， 包括调出仓库，从仓库运到码头装卸点，和吊装上船三个步骤。 仅仅考虑装船过程而不考虑卸货过程是因为一般来说集装箱在船上的排放 位置是事先已经确定的，这就使得不同的集装箱之间可能存在装船的先后次序约 束，并且装船过程必须严格遵循这些约束。而相对来说集装箱卸船的过程和装船 的过程相当类似，不同之处就是没有这种先后次序上的约束，因而相对简单一些。 事实上本文所提出的算法也同样可以应用于卸船的过程。另外前面所提到的论文 【2 ，1 2 】等也是基于类似的假定。 2 1 本论文的研究目标是优化集装箱装卸的设备调度算法，使得所有集装箱的装 船过程所用的总时间尽可能短。 用排序调度问题的术语来说，就是要使得整个过程的时间表长c m a x 最小。 3 ) 所有集装箱在尺寸上完全相同，均为1 个t e u ，并且每种设备同一时间只能 处理一个集装箱，同一集装箱在每个步骤也只能被一个设备所处理，不允许抢先 剥夺( p r e e m p t i o n ) 。 在实际运输中集装箱按重量可能存在1 t e u ，2 t e u ，4 t e u 等不同尺寸，而 且某些港口的调度设备如a g v 可以同时装载1 个2 t e u 或者2 个1 t e u 的集装 箱，但是考虑到最普遍的情况( 如荷兰鹿特丹港) 仍然是以1 t e u 的集装箱为主， 同时1 个a g v 每次只能处理1 个集装箱，因此这样的假设仍然是合理的。 4 1 忽略设备之间可能出现的冲突和故障等不确定因素。 由于a g v 需要在仓库和码头之间来回运输货物，所以彼此之间可能出现冲 突，特别是如果较多a g v 集中在同一仓库或者码头同一吊车附近的时候，冲突 的可能性会有所增加。另外设备也显然都具有一定的故障可能性，但是因为这些 因素出现的可能和带来的影响均难以确定，故在本论文的研究中将加以忽略。 5 ) 集装箱依次在每种设备上进行处理各所需的时间均是固定的，也就是处理时 间只与设备类型有关，而与具体进行处理的设备无关。 这个假设也是很合理的，因为在集装箱尺寸相同的情况下，忽略在装载过程 中因为某些不确定因素如设备故障，冲突等，那么同一个集装箱对于同种类型的 不同设备来说毫无差别，所以处理时间可以认为是相同的。这一假设带来的直接 影响就是我们可以认为所有的自动运输车a g v 是无差别的。 6 ) 每个集装箱所对应的a s c 和q c 都是事先确定的，同一q c 上面所有集装箱 的处理顺序也是事先确定的，与具体的设备调度方案无关。 集装箱在船上的排放计戈l j ( s t o w a g ep l a n ) 是根据集装箱中货物的种类等因素 事先确定的，因此吊装上船的过程必须按照一定的先后次序。同样每个集装箱在 仓库中的存放位置也是预知的，所以其所对应的a s c 也是固定的。 7 ) 相邻工序的设备之间有可能出现相互阻塞的情况。 由于相邻工序之间不存在可以暂存集装箱的缓冲区，因此对于某个集装箱来 说，只有当上一个工序的设备完成处理，而且下一个工序的设备已经准备就绪的 情况下，才能从上一个工序转移到下一个工序，否则就会出现阻塞的情况。 首先如果某个集装箱已经由设备i 完成了第k 个工序的处理，而第k + 1 个工 序的对应设备i 还没有准备就绪，那么设备i 将会被阻塞，不能立即继续去处理 下一个集装箱，而是必须等到设备i 就绪并接收当前集装箱之后，才能接着处理 其它的集装箱。例如假设某a s c 在时刻2 完成了当前集装箱的处理，而对应的 a g v 在时刻3 才到来，那么该a s c 在 2 ，3 】这段时间内将处于被阻塞的状态。 另一种可能出现的阻塞情况是下一个工序的对应设备i 已经到达，而上一个 工序的设备j 还未完成处理，那么设备i 需要等待设备i ，同样处于被阻塞的状态。 2 3 名词术语和相关定义 j o b = j o b ! ，j o b 2 ，j o b n ，表示要完成的任务集合，其中每个集装箱看作一 个待完成的任务，n 是所有任务的数目； a s c = a s c l ，a s c 2 ，a s c n a s c ) ，表示仓库跨车a s c 的集合，其中n a s c 是a s c 设备的数目； a g v ； a g v l ，a g v 2 ，a g v a g v 】，表示自动运输车a g v 的集合，其中 n a g v 是a g v 设备的数目； q c = q c l ，q c 2 ，。，q c n q c ) ，表示码头龙门吊车q c 的集合，其中n q c 是 q c 设备的数目； p r e c a s c ( j ) 表示在分配给j o b j 的a s c 的任务处理序列中排在j o b j 前面的任务； p r e c a g v 0 ) 表示在分配给j o b j 的a g v 任务处理序列中排在j o b j 前面的任务； p r e c q c ( j ) 表示在分配给j o b j 的q c 的任务处理序列中排在j o b j 前面的任务； p n s c ( j ) 表示j o b j 在a s c 上的处理所需时间； s a s c 0 ) 表示j o bj 在a s c 上的开始处理时间： t a s c ( j ) 表示j o b j 在a s c 上的结束处理时间； p a g v 0 ) 表示j o b j 在a g v 上的处理所需时间； s o v ( j ) 表示j o b j 在a g v 上的开始处理时间； t a o v ( i ) 表示j o b j 在a g v 上的结束处理时间； v o c o ) 表示j o b j 在q c 上的处理所需时间； s q c ( j ) 表示j o b j 在q c 上的开始处理时间； t q c ( j ) 表示j o b j 在q c 上的结束处理时间； 2 4 问题描述和数学模型 就装船过程来说，假设有n 个集装箱j o b l ，j o t u ，j o b 。需要装船，每个集 装箱i 需要依次经过3 种装卸设备a s c ，a g v 和q c 的处理，每种处理设备的 数目都是事先确定的，而且根据前面的问题假设，每个集装箱所对应的a s c 和 q c 都是己知的，而且分配给同一个q c 的集装箱之间存在完成次序上的先后关 系约束，因此集装箱装卸设备联合调度问题的目标就是要确定一个满足所有约束 条件的设备调度方案，使得完成整个装船过程的时间最短。 具体来说，每个集装箱i 对应于不同的装卸设备a s c ，a g v ，q c 都分别有 一个处理所需时间p a s c ( i ) ，p a g v ( i ) ，p q c ( i ) ，一个开始处理时间s a s c ( i ) ，s a o v ( i ) ， s q c ( i ) ，和一个处理完成时间t a s c ( i ) ，t a o v ( i ) ，t o c ( i ) ，其中处理所需时间是已知 的，而开始处理时间和处理完成时间则是调度方案所要确定的内容，它们之间必 须满足定的约束条件： ( 1 ) 对于每个j o bi 来说，必须依次经过a s c ，a g v 和q c 三个阶段的处理， 前一阶段的结束即为下一阶段的开始，加上相邻阶段的设备可能发生约束，因此 必须满足s a s c ( i ) + p a s c ( i ) = t a s c ( i ) = s a o v ( i ) ，s a o v ( i ) + p a g v ( i ) = t a o v ( i ) = s o c ( d 和s o c o ) + p o c ( i ) = t q c ( i ) ； ( 2 ) 对于每个a s c 来说，假设当前要完成的j o b 为j ，上一个完成的j o b 为i = p r e c a s c ( j ) ，那么任务i 的完成时间即为任务j 的开始时间，即s a s c 0 ) = t a s c ( i ) ； ( 3 ) 对于每个a g v 来说，假设当前要完成的j o b 为j ，上一个完成的j o b 为 i = p r c c a s c o ) ，那么根据阻塞约束，该a g v 必须在完成任务i ，并且等到任务 在a s c 上完成之后才能开始处理任务j ，所以s a g v ( j ) = m a x ( t a o v ( i ) ， s a s c ( j ) + p a s c ( j ) ) ； ( 4 ) 对于每个q c 来说，假设当前要完成的j o b 为j ，上一个完成的j o b 为i _ p r e c a s c ( j ) ，那么类似地根据阻塞约束，该q c 必须在完成任务i ，并且等到任务 j 在a g v 上完成之后才能开始处理任务j ，所以s q c ( j ) = m a x ( t o c ( i ) ， s a o v ( j ) + p a g v 0 ) ) ： 那么问题的目标就是在满足这些约束条件的前提下，确定所有任务的开始时 间和完成时间，从而使得最后一个完成的j o b 被q c 处理完成的时间t q c o ) 尽可 能小，即 m i nc m a x = m i n ( m a x ( t o c ( i ) ) ) s t 1 = 3 时则是n p - h a r d 问题【l ”。 事实上对于目标问题，本文作者发现如果假设所有任务在不同的处理设备上 的处理时间都是单位时间，并且忽略任务之间的完成时间先后次序约束，则可以 通过构造网络流模型而得到多项式时间的算法。本章3 3 节将给出这一算法的细 节。 3 2 解的表示与解空间规模分析 如果采用分支定界等求最优解的精确算法，那么最坏情况下有可能要遍历问 题的整个解空间，即使采用遗传算法、禁忌搜索等启发式技术，也有必要对解空 间规模和结构等进行分析，从而尽可能利用解空间的特点，提高算法效率。下面 就对设备联合调度问题的解空间规模进行分析。 因为解空间的规模与解的表示方式密切相关，所以我们首先来考虑问题的 解，也就是一个调度方案的组成部分。根据2 4 节建立的数学模型，显然一个调 度方案就是要确定每个i o b 分别在a s c ，a g v ，q c 上的开始时间 s a s c ( f ) ，e 。( f ) ，品。( f ) ( 每个阶段的结束时间均可以根据开始时间而确定) ，所以调 度方案可以用n 元组( 一，码，疗。) 来表示，其中每个元素互又是一个3 元组 ( s a s c ( i ) ，s a 。，( f ) ，品。( f ) ) 。由于这种表示方式与时问值直接相关，计算得到的解空 间的规模也与时间相关，显然过于巨大，不利于进行求解。 事实上，我们只需要知道每个任务与设备之间的对应关系，以及每个设备处 理任务的先后次序，就可以确定每个任务在不同工序上的开始时间，从而唯一地 确定调度方案。于是每个任务i 就对应一个6 元组( a s c 编号i a s c ( i ) ，a s c 上完成 序号“s c ( i ) ，a g v 编号i a g v ( i ) ，a g v 上完成序号j a g v ( i ) ，q c 编号i o c ( 0 ，q c 上完 成序号j o c ( i ) ) 。其中根据题目条件a s c 编号，q c 编号和q c 上完成序号都是已 知的，因此调度方案仍可以表示为n 元组( 巧，7 ：，) ，其中每个元素巧都是一 个3 元组( j a s c ( i ) ，i a g v ( i ) ，j a g v ( i ) ) 注意到所有a s c 和所有a g v 都是总共要完成 n 个任务，因此在这种表示方式下解空问规模可以用( n ! ) 2 来做粗略估计。这一规 模尽管与时间无关，但是显然仍是相当庞大，这是因为其中包含了大量的非可行 解，重复解等无用的部分。 弓| 理i 1 2 1 ：考虑一个最优的诵发杰案假设r ? 表示最优方案中a s cs 处理其薇有 任务的次亭郡么必然存在一个最优的a g v 任务分配考案兀( 郎所有任务在a g v 上开始执行鳆先后次亭 。使褥对f 任意韵s a s cj 均存耳：是冗的子亭确， 证明：见文献【2 】，第8 页。 基于上述引理，我们只需要确定所有任务在a g v 上开始执行的先后次序， 就可以确定每个a s c 上的任务执行次序。因此调度方案又可以表示为n 元组 ，= ( j o b i l ，j o h n ，j o b , ) ，其中( j o b , , ，j o b , 2 ，d 6 m ) 是j o b l ，j o h 2 ，j o b n 的一 个排列。在这种解表示下，解空间的规模为n ! ，比起前面的解表示方法已经有了 较大的进步。事实上，m e e r s m a n s ，w a l g m a n s 2 】使用分支定界和束搜索算法来求 解联合调度问题的过程正是基于这种排列式的解表示方式。在本文第4 章中提出 的遗传算法也同样基于这种解编码方式。 3 3 处理时间为单位时间的情况下的网络流算法 如果忽略任务在完成时间上的先后次序约束，那么如果将船和仓库，a s c 和 q c 的角色颠倒( 将船看作仓库，仓库看作船，a s c 看作o c ，o c 看作a s c ) ，显 然问题就相当于从船上卸载集装箱到码头仓库的过程。如果不作任何假设，那么 该问题仍然也是n p h a r d 问题，但是如果再假设所有任务在不同类型的设备上 处理时间都是单位时间，那么就可以建立网络流模型，得到求解问题的多项式算 法。 事实上，在忽略任务优先关系约束的情况下，相当于每个任务都被事先指定 一个初始位置( 仓库中) 和目标位置( 船上) ，而每个设备则相当于一个中转点，并 且每个任务都必须从起始位置出发，依次通过3 种类型的中转点到达目标位置。 目标就是使得整个过程的总时间最短，同时必须满足任一时刻每个中转点至多被 一个任务所占据的约束。 3 3 1 任务的目标位置不确定的情况 在每个任务指定目标位置的情况下，问题仍比较复杂，不便于说明网络流模 型的构图规则和算法细节。为此我们首先考虑任务的目标位置不确定的情况，即 每个任务可以由任意的o c 进行处理，同时每个o c 处理的任务数是固定的。 显然每个设备在不同时刻的状态会有所不同，因此我们必须用二元组( 设备， 时间) 来表示状态，在进行构图的时候，每个状态分别对应图中的一个顶点，并 用顶点之间的有向边来表示任务在设备和时间上的转移关系，这样构造产生的图 我们可以称为设备一时间图。 下面是给定时间表长t l e n 的情况下，设备一时间图g ( e ) 的构图规则r 1 ： f 1 ) 首先考虑顶点集v 的组成： f 1 a ) 增加一个源点s 和一个汇点t ，分别作为网络流的起点和终点； ( 1 ”对于每个任务i ，增加一个顶点v ， ( 1 c ) 对于任意一个设备i ( i 可以是a s c 、a g v 或者q c ) ，和任意一个时刻 t ( 0 = t = t l e n ，且t 是整数) ，显然它们组成的二元组( i ，t ) 可以表示一个状态， 对这个状态相应地增加一个顶点v i t a ( 2 ) 其次考虑边集e ： ( 2 a ) 对于任意任务j ，在源点s 和任务顶点v j 之间增加一条有向边 ； f 2 b ) 对于任意的任务i 和它所对应的a s ci ，以及任意的时刻t ( 1 _ t _ t l e n ) ， 在任务顶点v j 和a s c 顶点v 订之间增加一条有向边 ， 表示任务i 可以在t - 1 时刻在a s ci 上开始处理，在t 时刻处于完成状态； ( 2 c ) 对于任意的a s ci 和任意的a g vj ，以及任意的时刻t ( 1 - t r l e n ) ， 在a s c 顶点v i ，t 和a g v 顶点v j , t + l 之间增加一条有向边 ，表示某任 务在t 时刻从a s c i 传递给a g v j ，并在t + i 时刻完成a g v 上的处理工作； ( 2 d ) 对于任意的a g vi 和任意的o cj ，以及任意的时刻t ( 1 = t t l e n ) ， 在a g v 顶点v i t 和o c 顶点v j t + l 之间增加一条有向边 ，表示某任务 在t 时刻从a g v i 传递给a s c ，并在t + 1 时刻完成q c 上的处理工作； ( 2 e ) 对于任意的q ci ，以及任意的时刻t ( 1 = t = t l e n ) ，在q c 顶点v i t 和汇点t 之间增加一条有向边 ，表示某任务在t 时刻已由q c i 吊装上船； ( 2 0 对于任意设备i 和时刻t ( 1 = t = t l e n ) ，在顶点v i ，t 和v i t + i 之间增加 一条有向边 ，表示设备i 上已经完成某任务的处理，但因为需要等 待下一工序的设备就绪而在时间段 t ，t + 1 处于阻塞状态； 假设j o b = j o b l ，j o b 2 ) ，a s c 2 a s c i ，a s c 2 ) ，a g v = ( a o v i ) ，q c = q c i ) ， 其中j o b , 对应a s c l ，j o h 2 对应a s c 2 ，那么在时间表长t l e n = 4 的情况下，按 照上面的构图规则得到的设备一时问图如下面图3 - 1 所示。由于图的大小关系， 图中顶点的代号未能一一标出。其中a s c 列的8 个顶点由上至下依次是 ( a s c l ，1 ) ，( a s c l ，2 ) ，( a s c i ，3 ) ，( a s c i ，4 ) 和( a s c i ，1 ) ，( a s c i ，2 ) ，( a s c i ，3 ) ，( a s c l ，4 ) ， 而a g v 列的4 个顶点则由上至下依次是( a g v i , 1 ) ，( a o v l , 2 ) ，( a g v b 3 ) ， ( a g v , ，4 ) ，至于q c 列的4 个顶点则由上至下分别为( q c l ，1 ) ，( q c l ，2 ) ，( q c l , 3 ) ， ( q c l ，4 ) 。图中粗线边分别表示两个任务j o b l ，j o h 2 的处理路径。 源点任务 a s ca g v q c 汇点 图3 - 1 按照构图规则所得的设各时间图示例 从上面的例子我们可以看出，在给定时间表长t l e n 的情况下，由于每个任 务在任意设备上的处理时间都是l ，那么每个任务从开始到完成的过程可以看作 是在设备一时间图上从源点到汇点的一条路径，而且由于设备任一时刻至多只能 处理一个任务，所以不同任务所对应的路径上面除了源点s 和汇点t 之外不能有 其它的交点，因此单位处理时间的设备联合调度问题就相当于在设备一时间图中 寻找从源点到汇点的n 条点不交路径的问题，如果图中存在至少n 条点不交路径， 那么显然所有任务可以在不多于t l e n 的时间内完成，即最优的时问表长 c m a x t l e n 。 为了便于描述，我们将图中除源点和汇点之外的其它所有顶点称为中间顶 点。那么按照网络流理论，路径不能在中间顶点处相交，就是说除每个中间顶点 至多只能被使用一次，也即是每个中间顶点的容量是1 。利用图论中的拆点变换 技术，将每个中间顶点i 分拆成两个顶点i l ，i 2 将以顶点i 为终点的边改为以i i 为 终点，而将从i 出发的边改为从i 2 出发，并且增加一条容量为i 的有向边 ， 那么顶点的容量限制就可以转化为边的容量限制，同时点不交的路径问题也相应 地转化为边不交的路径的问题。然后根据网络流理论中著名的m e n g e r 定理，图 中两点间边不交的路径的最大数目等于从源点到汇点的网络流的最大值。故而到 这里原问题已经转化为图论中的最大流( m a x f l o w ) 问题。 因此结合二分法( b i n a r ys e a r c h ) $ 1 最大流算法，我们可以得到求解问题的多 项式算法，具体流程如下： 单位处理时间，且任务目标位置不确定的二分+ 网络流算法： ( 1 1 计算时间表长c m a x 的一个上界t m a x ； ( 2 ) 令x = 1 ，y = t m a x ； ( 3 ) 判断x 是否 一n ，是则令y = t l e n ，否则令x = t l e n + i ，转( 3 ) ； ( 6 1 y 的值即为最优的时间表长c m a x ，结束； 3 3 2 任务的目标位置事先指定的情况 在前面3 3 1 节中，我们已经解决了任务目标位置不固定的情况，下面将把 任务的目标位置也加以考虑。显然3 _ 3 1 节中设备一时间图的构图规则r 1 所存 在