（计算机软件与理论专业论文）使用束搜索解决港口集装箱装卸设备联合调度问题.pdf

使用束搜索解决港口集装箱装卸设备联合 调度问题 专业：计算机软件与理论 硕士生：林祺颖 指导教师：郭嵩山 摘要 本论文针对港口集装箱装卸设备联合调度问题，充分考虑多设备联合调度， 结合前人研究该问题所使用到的分支定界和遗传算法，利用可扩展性更强的束搜 索算法进行探讨，从而得出可扩展性强的适合工业使用的算法框架。 本文结合荷兰鹿特丹港口设备设置，讨论了束搜索算法，即限制每层结点的 广度优先搜索算法在该问题的应用。在使用束搜索中，为了方便束的插入和利用， 使用插入和删除效率都高效的数据结构雄；在扩展结点时，使用最简单的单 个任务作为束搜索的层，并通过参数设置控制每一个领域生成时单个结点的子结 点的入束数目，从而防止整柬均为单个结点的子结点的局部退化现象；在束搜索 的关键一评价结点费用时，抛弃了原有复杂的函数估算，而使用较为简单的贪 心策略来得到局部最优解，从而作为该结点的估价费用。最后在普通的束搜索中， 为了得到更优的解，加入了利用概率选择出堆及针对该问题所使用的技巧。 文章最后分析结果部分，首先纵向比较该束搜索中所使用到的参数对整体结 果的影响，然后横向讨论了三种算法各自的特点，并总结本文所使用的束搜索的 相对其余两种算法优点。最后得出该束搜索可扩展性优秀的结论，因此适用于工 业生产应用。 关键词：集装箱联合调度，束搜索，筛选，局部最优，费用 u s i n g b e a ms e a r c ht os o l v e 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 ft 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 ：q i y i n gl i n s u p e r v i s o r ：s o n g s h a ng u o a b s t r a c t t h i sp a p e rf o c u s e so nf i n d i n g 托e x t e n d a b l ef r a m e w o r kf o ri n t e g r a t e ds c h e d u l i n g o f t e r m i n a lc o n t a i n e rh a n d l i n g 州p m a 止b a s e do i lp r e v i o u sr e s e a r c hw h i c hb a s e do n b r a n c ha n db o u n da l g o r i t h ma n d 霉e n e d ca l g o r i t h m ，i td e e p l yd i s c u s s e st h eb e a m s e a r c ha l g o r i t h mw h i c hh a ss t r o n g 懿t a n d e da b i l i t ya n di sq u i t ef i tf o rd e v e l o p i n g i n d m t r i a lu t h i sp a p e ri sb a s e do nt h eo q u l p m o n ts t r u c t u r eo fr o t t e r d a m , d i s c u s s e st h e a p p l i c a t i o no f b e a ms e a r c ha l g o r i t h m - o n ek i n do f b r e a d t h f i r s ts e a r c ht h a tl i m i t e dt h e e x t a n tw i d eo fe a c hn o d e f u r t h e r m o r e , t h eh e a ps u u c t u r ei su s e dt of a c i l i t a t et h e o p e r a t i o no f i n s e r ta n dd e l e t e t op r e v e n tt h ed e g e n e r a t i o nt h a tn o d e so f o n eb e a m a r e a l lf r o mo n es i n g l en o d e , i tr a i s e sac o n t r o l l a b l ep a r a m e t e rt ol i m i tt h en u m b e ro f e a c h n o d e sc h i l d r e ni n s e r t e d e s t i m a t i n gt h ec o s to fp a r t i a ls o l u t i o ni st h eh a r d e s tp a r to f b e a ms e a r c h i n s t e a do f u s i n gc o m p l e xf u n c t i o n s ，t w og r e e d ya l g o r i t h m sa f oc h o s e nt o s o l v et h i sp r o b l e m f i n a l l yc h a s i n gf o rb e t t o rs o l u t i o n , ap r o b a b i l i t yw a yt oe x p a n d n o d ei si n v o l v e d i nt h el a s t p a r to fp a p e r , t h ei n f l u e n c e o ft h es e a r c h p a r a m e t e r s a n dt h e c h a r a c t e r i s t i c so ft h r e ea l g o r i t h m sa r oc o m p a r e d t h en e wb e a ms e a r c ha p p r o a c hf o r i n t e g r a t e ds c h e d u l eo ft e r m i n a lc o r i t a i n e fh a n d l i n ge q u i p m e n ts h o w st h a tt h i sn e w s e a r c hm e t h o d o l o g yh a sp o w e r f u le x t e n d e da b i l i t yf o r d e v e l o p i n g i n d u s t r i a l a p p l i c a t i o n s ， k e y w o r d s ：c o n t a i n e ri n t e g r a t e ds c h e d u l i n g , b e a ms e a r c h , s e l e c t ，l o c a lo p t i m a l ，c o s t 1 1 1 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：幸末 聋幸乏 日期：加7 年汨华e t 引言 在现代港口运作中，能否适应大吞吐量成为港口优异的标准而在港口运作 中，对集装箱进行调度是其中最关键部分。由于港口对集装箱进行调度要经过各 种不同设备，因此，当要解决港口集装箱装卸设备联合调度问题时，我们应该统 一考虑涉及到的所有设备，从而使他们能够协调运作。因此该问题具有广泛的实 际应用背景。 一般来说，在港口进行集装箱调度时，需要经过不同的工序，不同的工序需 要使用不同的设备。考虑一个集装箱从仓库运送到货船这个过程中，首先由仓库 跨车a s c ( a u t o m a t c 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 y c r a n e ) ，然后由q c 将货物吊装上船。而相对的，集装箱由货 船运到仓库则工序相反。这使集装箱调度不应该单纯的只考虑某种设备，而需要 考虑这三种设备的联合调度问题，使这三种设备达到最优化运作，互相配合，减 少因彼此的等待而浪费的时间。 人们对集装箱调度问题有了非常深入的研究，对各种设备的调度都有一套很 优秀的算法，如a g v 的调度【l 】等。但是由于绝大部分都是仅仅考虑单一种设备， 因此我们需要寻求一种综合考虑多种设备的算法。 本论文将结合鹿特丹港港口设备设计，综合考虑所有设备的特点，提出该问 题的一个简单的数学模型。而考虑该问题的复杂性( 文献【2 】已经证明了这个问 题是n p h a r d 的) ，并且在易用性上进行考虑( 文献【2 1 提出了一种极其复杂的分 支定界的方法，并且使用该方法的界提出相应的柬搜索) ，结合考虑黎俊瑜硕士 毕业论文【3 】中使用遗传算法得出的商效但也是缺乏易用性的方法，提出一种基 于束搜索相对高效但使用简单，同时具有很强的可扩展性的方法。 第1 章简介 人类踏入工业社会以来，轮船作为最便宜的运输手段，一直占据着极其重要 的地位。而轮船运输所使用的集装箱作为近代社会运输发展的重要标准化单位， 以极其迅猛的速度推广到世界每一个港口。在现在贸易发展中，集装箱成为了现 代运输的主要手段。据统计，现在全世界6 0 0 以上的船运货物都是通过集装箱来 进行运输的，在某些经济发达国家这一比率更是高达1 0 0 【4 】。 由于现代港口的不断发展，虽然轮船的规模也在不断的增加，但对于港口而 言，提高其吞吐量所带来的效益远远高于轮船规模的增加。而提高港口的吞吐量 的办法无疑于减少集装箱在港口的停留时间，争取在同区的竞争中胜出。 通过对港口集装箱装卸设备联合调度问题的研究，就可以减少集装箱在港口 的停留时间，不但能够吸引船运公司在该港口停泊，同时也提高港口的吞吐量， 减少运营成本，从而获取更大的利益。同时，对该问题进行仿真研究，即可对港 口运营情况得到更进一步的了解，从而达到优化港口资源配置及港口设备布局结 构，为港口设计者和决策者提供更多有价值的依据。 本论文在前人研究的基础上，提出使用可扩展性强的束搜索方法，结合文献 【z e e 提出的问题难度分析，比较文献【2 】中所使用的复杂的分支定界及使用该分 支定界的束搜索，加入对黎俊瑜师兄所使用的经过精心设计的遗传算法【3 】的比 较，得出在效率相当的情况的，解出来的最优结果也相当( 基本在2 内) ，从而 得出本论文在扩展性上具有更好的适应性，因此更能应用到实际的港口的设备联 合调度中去。 本论文分为七部分，结构如下： 第一章对问题进行概述，提出研究该问题的意义。 第二章对问题进行描述，建立相应的数学模型，同时也对该领域的研究状况 进行综述。 第三章针对原有的问题及方法进行分析，分别对文献 2 】中的方法和黎俊瑜师 兄使用的遗传算法【3 】进行一定的介绍，并且分析其优缺点。 第四章和第五章为本论文的重点。第四章提出一种可扩展性更强的束搜索方 法，分别研究束搜索中所遇到的各种问题，然后提出该方法所使用到的两种贪心， 从而解决束搜索中最困难的部分一费用估算。 第五章讨论在上述原始的束搜索框架上，加入更多的优化，使问题的复杂性 降低，同时程序运行效率及解的质量得到提高 第六章首先对该束搜索算法所涉及到的各种参数及优化进行纵向比较，然后 分析三种不同的方法( 本论文方法，文献【2 】及文献【3 】) 的结果进行横向比较和 分析并最终得出可在时间相当的情况下，可得到与前人论文相当的结果，而在 算法设计上具有更强的可扩展性，因此本论文算法更优秀的结论。 第七章是总结，并介绍该方法的不足之处和可改进之处。 第2 章问题概述 2 1 研究对象和闯题假设 2 1 1 港口布局 本文基于荷兰鹿特丹港的港口设置进行讨论，该港港口布局可用下图表示 ( 图2 1 ) ： 图2 - 1 荷兰屁特丹港口布局l 墨| ( 2 】 由图可见，该港口可分为三部分，集装箱从仓库运送到轮船上分别需要经过： 仓库跨车( a u t o m a t i cs t a c kc r a n e ，a s o ，自动运输车( a u t o m a t i cg u i d e dv e h i c l e ， a g v ) ，龙门吊车( q u a yc r a n e ，q c ) 。这三种设备又分别对应港口的三部分。集 装箱首先从仓库运出，由a s c 沿着固定的轨道( 一般来说是直线) 运到a g v 的交货点，然后出a g v 沿着一条环形道运到q c 下面，然后由q c ( 一种并排 4 的，具有“大爪子”的器械) 把集装箱呻i | 【”到船上在文献【2 】中，他假设了所有的 a g v 都会经过所谓的“奇点”，在图上即为右上角的 c o m n l o l lp o i n t ，因为都经 过了该点，所以才让a g v 在调度算法中认为都是一样的。 而在文献 5 】所提供的数据，一个典型的货柜码头拥有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 1 2 研究对象 本论文所研究的就是考虑一艘货船的所有集装箱从仓库经过a s c ，a g v ， q c 三种设备后，顺利装载上船的总时间。而论文的研究目标就是通过一系列的 调度( 该在何时使用何种设备) ，使整个装载上船的过程时间最短，也即从第一 个集装箱离开仓库到最后一个集装箱上船的时间跨度最短，也可以描述为对每个 集装箱，其到达船只时间( 包括开始的等候时间) 的最大值最小。 与此相反，把货物从船上运到仓库的过程即为上述过程的逆过程，因此总时 间也是一样的( 卸船要比装船稍微简单，下面内容会给出解释) 。 2 1 3 问题假设 问题假设与文献【3 1 类似，如下： 1 假设装船过程与卸船过程时间一样。由于集装箱具有相异性，因此集装 箱上船是有一定的顺序的，并且也有其对应的位置。例如水果跟衣服的处理方式 明显的不一样，运送水果的集装箱相对来说要放在干燥阴凉的位置，而放衣服的 集装箱则没有这个限制。但是卸船就没有这种限制，因为集装箱已经固定位置了， 只要把它们卸下来即可。因此，卸船要比装船相对的简单。事实上，本文所提出 的算法也同样可以应用于卸船的过程。论文【2 ，3 ，6 】等也是基于类似的假定。 2 所有集装箱都是一样大小的，即单位大小( 在行业标准中，叫做l 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 。并且每种设备只能处理一个集 装箱，同一个集装箱同一时间只能由一个设备运输，并且在处理过程中不能中断， 即不允许抢先剥夺( p r e e m p t i o n ) 。 在实际应用中，多单位的集装箱也是存在的( 如l t e u ，2 t e u ，4 t e u 等 不同尺寸) ，但是由于绝大部分都是1 t e u 的，而我们所研究的鹿特丹港仍然是 以i t e u 的集装箱为主，因此假设都是i t e u 也是合理的 3 忽略设备之间的冲突和故障。由于设备的多元性，因此，设备难免出现 冲突，例如q c 设备运作时，由于港1 2 1 基本都是单轨道的，因此q c 之间是不可 能跨越的，所以有一定的冲突可能性。又例如a g v ，汽车运输路线在交接地方 非常容易出现碰撞( 冲突) 。除了冲突以外，由于设备都有使用寿命，因此在使 用中都会有故障情况出现。但是这些冲突和故障的存在都有相当的不确定性，因 此本论文不予考虑。 4 集装箱在同一种设备处理的时问都是一样的，不存在设备个体不同而使 处理时间不同的情况。这样的假设也是合理的，因为集装箱的统一性( 1 t e u ) ， 又忽略了设备之间的冲突和故障，所以集装箱对设备是一致的，不一致的是不同 类型的设备( a s c ，q c ，a g v 这三种设备之间) 的处理时问。 5 每个集装箱所对应的a s c 和q c 的处理设备是事先知道的。同一q c 上 所有集装箱的处理顺序也是事先确定的，与具体的设备调度方案无关 这样的假设会使问题的空间复杂性简单化( 由原来的3 组全排列的问题简化 成更少的排列问题，同时，也使搜索的时间复杂度降低) ，但是程序实现方面就 复杂了( 单纯的3 组全排列费用问题变成需要计算更多情况的费用) 。而这样的 假设是必要的，确定a s c 处理设备原因是仓库存放集装箱的位置是已知的，因 此肯定可知道a s c 处理的集装箱资料。而由于集装箱装船位置是已知的，因此 q c 编号和q c 服务顺序也是固定。显然，只有这样的假设才符合港口的设置。 6 相邻工序的设备之间有可能出现相互阻塞的情况。即同一集装箱的前一 设备处理完毕才能到后面设备处理，不同集装箱的同一设备也只能先处理调度之 前的集装箱。 这样的假设是源于集装箱及设备的相对独立性。即设备只能同时处理一个集 装箱，而集装箱的处理也只能按部就班的按照顺序服务，不可能有像a g v 把集 装箱运到一半，即可由q c 把集装箱运上船的情况。 对应的例子有：假设某a s c 在时刻2 完成了当荫集装箱的处理，而对应的 a g v 在时刻3 才到来，那么该a s c 在【2 ，3 】这段时间内将处于被阻塞的状态。 另外一种阻塞情况就是集装箱2 在时刻2 经a s c 已经准备好，但a g v 在时刻3 才能把在集装箱2 之前调度的集装箱l 处理完，则集装箱2 必须等候到时刻3 才能处理，同时，服务集装箱2 的a s c 也要等待到3 才可释放 2 2 名词术语和相关定义 j o b = j o b t ，j o b z 一，j o b ，表示要完成的集装箱集合，其中每个集装箱看作 一个待完成的任务，n 是所有集装箱的数目； a s c = a s c l ，a s q ，a s s c ，表示仓库跨车a s c 的集合，其中n a s c 是a s c 设备的数目； a g v = a g v i ，a g v 2 ，a g v n 6 w ，表示自动运输车a g v 的集合，其中 n a g v 是a g v 设备的数日； q c = q c l ，q q ，q c 哟c ，表示码头龙门吊车q c 的集合，其中n q c 是 q c 设备的数目； p r e c m c ( j ) 表示在分配给j o bj 的a s c 的任务处理序列中排在j o bj 前面的任 务； p r c c 6 w ( j ) 表示在分配给j o b j 的a g v 任务处理序列中排在j o b j 前面的任务； p r 。c q c ( j ) 表示在分配给j o b j 的q c 的任务处理序列中排在j o b j 前面的任务； 1 k c ( j ) 表示j o b j 在a s c 上的处理所需时间； s s c 4 j ) 表示j o b j 在a s c 上的开始处理时间： e s c 4 j ) 表示j o b j 在a s c 上的结束处理时间； i a s c 0 ) 表示j o b j 指定的a s c 编号； t g v ( j ) 表示j o b j 在a g v 上的处理所需时间； s o v ( j ) 表示j o b j 在a g v 上的开始处理时间； e a g v ( j ) 表示j o b j 在a g v 上的结束处理时间： t q c 0 ) a - 表示j o b j 在q c 上的处理所需时间： s o c 0 ) 表示j o b j 在q c 上的开始处理时间： e q c ( j ) 表示j o b j 在q c 上的结束处理时间； i q c 0 ) 表示j o b j 指定的q c 编号； j q c ( j ) 表示j o b j 指定的q c 顺序号； 显然，我们已知t a s c 0 ) ，t a 6 v0 ) ，t q c ( j ) ，i a s c 0 ) ，i q c ( j ) ，j q c 0 ) 。 7 2 3 问题描述和数学模型 单纯考虑装船过程，现有n 个集装箱，分别为j o b l ，j o b 2 ，j o b 需要装 船，而每个集装箱i 都需要依次经过3 种装卸设备a s c ，a g v 和q c 的处理 这三种设备的数目都是确定的，而且根据问题假设，每个集装箱所对应的a s c 和q c 的编号都是已知的，分配给同一个q c 的集装箱之间的顺序也是已知的， 即q c 服务存在先后约束，因此集装箱装卸设备联合调度问题的目标就是要确定 一个满足所有约束条件的设备调度方案，使得完成整个装船过程的时间最短。 对于每个集装箱i ，所对应于装卸设备a s c ，a g v ，q c 都有一个处理所需 时间t a s c ( i ) ，t a g v 0 ) ，t 0 c ( i ) ，而调度算法就是求出每种设备的开始处理时间 s s 砸) ，s o v ( i ) ，s q c ( i ) 和处理完成时间( 包括阻塞时间) e a s c ( i ) ，e a o v ( i ) ，e q c ( i ) ， 这三者之间必须满足一定的约束条件： ( 1 ) 有关j o bi 的限制：显然每个集装箱i 须依次经过a s c ，a g v 和q c 三 个设备的处理，前阶段的结束才能到下一阶段的开始，而相邻阶段的设备可能 发生阻塞，但应该尽量不让集装箱和对应设备同时空转，这样才能使时间最短， 因此必须满足： s m c ( i ) + t a s c ( i ) - e a s c ( i ) = s a g v ( i ) ， s o m i ) + t g v ( i ) - e a g v ( i ) = s “i ) ， s o c ( i ) + t 0 e ( i ) = e q c ( i ) ； ( 式2 1 ) ( 式2 2 ) ( 式2 3 ) ( 2 ) 有关a s c 的限制：显然是对于每个a s c ，前一个安排的任务尚未完成， 则下一个任务就不能开始。描述如下；假设a s c 当前要完成的j o b 为j ，上一个 完成的j o b 则为i - l r e e a s c ( j ) ，那么j o bi 的完成时间即为j o b j 的开始时闯，即： s s c ( j ) = e m c ( i ) ： ( 式2 - 4 ) ( 3 ) 有关a g v 的限制：同a s c ，存在前后两个任务的限制，并且需要a s c 处理完毕才可让a g v 进行处理，因此需考虑两者的最大值。假设当前要完成的 j o b 为j ，上一个完成的j o b 为i - p r e c a o v 0 ) ，根据阻塞约束，该a g v 必须在完 成任务i ，并且等到任务j 在a s c 上完成之后才能开始处理任务j ，所以： s o v 0 ) = m a x ( e a g v ( i ) ，s s c ( j ) + t a s c ( j ) ) ； ( 式2 - 5 ) ( 4 ) 有关q c 的限制：同a g v ，亦有两个限制。假设当i ；i 要完成的j o b 为j ， 上一个完成的j o b 为i = p r e c o c 0 ) ，则该q c 必须在完成任务i ，并且等到任务j 在a g v 上完成之后才能开始处理任务j ，所以： s q c o 户m a x ( e 0 c ( i ) , s g v ( i ) _ 叮 g v ( j ) ) ； ( 式2 - 6 ) 该问题调度算法就是在满足上述所有约束条件的前提下，寻找适当的任务的 开始时间和完成时间，从丽使得所有的j o b 被q c 处理完成的时间的最大值e q c ( i ) 尽可能小，即 r a i nc m a x = m 叫m 缸( e q c ( i ) ) ) s t 1 = 3 时则是n p h a r d 问题 1 9 】。 而在师兄黎俊瑜的毕业论文 3 】中，他把处理时间假设为单位时间，则可以通 过构造网络流模型而得到多项式时间的算法。但是，由于这在实际应用中是不可 能实现的，因此作用不大。 综合上述，可见原问题极难找到一个较好的多项式算法，因此只能寻求一种 近似算法。在传统算法上，可用的有分支定界算法，a 算法等，而现代优化算法 中，比较适合使用的是禁忌搜索，束搜索，遗传算法等。 3 2 解的表示与解空间规模分析1 3 l 如果单纯考虑三种设备调度，即不考虑其众多的限制条件，则可对应于三个 全排列，即a s c 服务序列，a g v 服务序列和q c 服务序列；当加入了这些限制 条件以后，这些服务序列就存在一定的关联，因此这三个全捧列就有一定的限制。 因此就会使排列的空间难度降低。 当采用广度优先搜索等可求最优解的精确算法时，在最坏情况下有可能要遍 历问题的整个解空间，即使采用遗传算法、禁忌搜索等启发式技术，也有必要对 解空间规模和结构等进行分析，从而尽可能利用解空间的特点，提高算法效率 下面就对设备联合调度问题的解空间规模进行分析。 因为解空间的规模与解的表示方式密切相关，根据2 3 节建立的数学模型， 一个调度方案就是要确定每个j o b 分别在a s c ，a g v ，q c 上的开始时间 s k ( 稂只。，( f ) ，o ) ( 每个阶段的结束时间均可以根据开始时间而确定) ，所以调 度方案可以用n 元组( 排列) ( j r l ，以) 来表示，其中每个元素乃又是一个3 元组( 芦。( f ) ，只。，。( f ) ) ，即可理解为三个全排列。 事实上，只需要知道每个任务与设备之间的对应关系，以及每个设备处理任 务的先后次序，就可以确定每个任务在不同工序上的开始时间，从而唯一地确定 调度方案。于是每个任务i 就对应一个6 元组( a s c 编号i a s c ( i ) ，a s c 上完成 序号j a s c ( i ) ，a g v 编号i a g v ( i ) ，a g v 上完成序号j a g v ( i ) ，q c 编号i q c ( i ) ， q c 上完成序号j q c ( i ) ) a 其中根据题目条件，a s c 编号( i a s c 0 ) ) ，q c 编号( i q c ( m 和q c 上完成序号( j q c ( i ) ) 都是已知的，因此调度方案仍可以表示为n 元组 瓴，吒，瓦) ，其中每个元素珥都是一个3 元组( j a s c ( i ) ，i a o v ( i ) ，j a g v ( i ) ) 注意 到所有a s c 和所有a g v 都是总共要完成n 个任务，因此在这种表示方式下解 空间规模可以用( n ! ) 2 来做粗略估计。这一规模尽管与时间无关，但是显然仍是相 当庞大，这是因为其中包含了大量的非可行解，重复解等无用的部分 定理p ：考惑一个最优的调麦方案。假设耳? 表示最优方案中a s cs 处理其所有 任务的次亭郡么必然存在一个最优的a 【w 任务分配方案冗( 即所有任务窿a g v 土开始技褥的先后次南镘德穗子任意的s e a s c 均确冗s 是霭豹子亭露。 证明：见文献【2 】，第8 页。 基于上述引理，我们只需要确定所有任务在a g v 上开始执行的先后次序， 就可以确定每个a s c 上的任务执行次序因此调度方案又可以表示为n 元组 石= ( 弘西i ，j o b , z ，j o k ) ，其中( 弘6 j i ，j o h 2 ，弘6 钿) 是j o b ，l o b 2 ，l o b 的一 个排列。在这种解表示下，解空间的规模为n ! ，比起前面的解表示方法已经有了 较大的进步。事实上，m e e r s m a n s ，w a l g m a n s 2 使用分支定界和束搜索算法来求 解联合调度问题的过程，以及黎俊瑜师兄求解的过程 3 l i e 是基于这种排列式的 解表示方式。本文求解过程也是基于这一个定理，也即只需一个全排列即可对该 问题求出最优解( 或者较优解) 。 3 3 分支定界和相关的束搜索 在文献 2 】中，该文第一次提出该联合调度问题，定义该问题的数学描述，并 且对该问题的复杂性为n p h a r d 给出严格的证明。然后再次讨论该问题可以单 纯用一个n 的全排列即可表示一个最优解。可以说，该文章为集装箱的联合调度 问题奠定了最基本的理论依据，也为问题的简化和实现提供了最有意义的说明。 该文章不仅仅是一篇提供该问题的算法基础，也是一篇求较优解算法的优秀 文章。在提供了算法复杂性和实现性依据以后，文章即介绍了使用b r a n c ha n d b o u n d 算法，即使用分支定界算法来实现。该分支定界算法可归纳如下： 1 搜索方向。搜索使用深度搜索。在搜索中，前面层次( 即当前待扩展结 点) 为一n 排列的部分，而在扩展中加入尚未扩展的排列的一个数，然后对增加 后的部分解进行估算，求出其界。 2 搜索策略。进行多次搜索。首先设立一容忍因子( 文献 2 】是2 5 ) ，然 后如果估算的下界在容忍范围内( 即l + 容忍因子) ，则继续搜索，超过以后则不 搜。然后不断降低容忍因子，直到容忍因子为0 为止。 3 高质量的估算函数。论文一共提出了三种不同的估算函数。这三种估算 函数都是估算下界。由于这些估算酯数充分考虑了该题目的特点，因此这些估算 函数都是非常出色的，由后面的实验结果知，解与函数值已经相差无几了。最大 差距也仅在2 之内。说明这些函数可改进的范围已经相当狭窄了。但是，这3 个函数是相当难设计的，可以说，需要非常“聪明”的工程师花费大量的时间才能 写出来，如果问题稍微改变，则整个算法都要重新设计，因此可扩展性很差 论文在提供了分支定界算法以后。介绍了基于该分支定界的柬搜索方法束 搜索是基于估算的限制搜索广度的广度优先搜索，因此，束搜索的关键在于其估 算函数。论文使用上面提到的3 个高质量的估价函数，因此，该文的束搜索也是 相当高效且解的质量是相当高的由其所定义的束宽( 即每层保留的结点数，论 文建议用4 ，仅仅保留4 个结点的搜索在优化算法里面可以说是难以置信的) 就 可知道，该算法的设计也是相当困难的 3 4 遗传算法 师兄黎俊瑜在他的硕士毕业论文【3 】中，对该问题从另外一个角度进行了分析 并提出相应的算法。该论文是建立在该问题可用一个全排列来表示的基础上进行 研究。使用现代最流行的算法遗传算法进行解决。根据遗传算法的特点，该 论文的算法框架如下： 1 初始解的生成。分别提出了2 种不同初始解的产生方法。第一种是随机 生成。第二种是基于启发式产生算法，该算法充分分析题目特点，把随机生成的 杂乱的解优化成具有一定规律性的初始解。 2 适应函数( 即估价函数) ，由于遗传算法的一个结点即为一个解，自然就 会把一个解的实际费用作为其适应函数。 3 交配，变异，修复因子。这些与传统算法没有区别，不在这里介绍 由这些最基本的框架即可得出一个非常传统的遗传算法，但是，由于这样的 遗传算法没有针对性，因此与最优解的距离均有7 - - 1 0 的距离。 然后论文提出了基于关键路径的改进算法。他所使用的解图模型借鉴自文献 2 0 1 ，得出一个在一个排列中所对应的解图，然后根据解图即可得出在这个排列 中所有的关键点，对应问题中的是那个任务j o b 在那个设备处理时是具有影响到 解的大小作用的。因此，要改进问题的解就为改进关键路径点，由此引伸出两种 不同的改进方法：第一种是随机改进，即对关键路径上的某点与不在路径上的某 点随机交换。第二种是基于右平移调度方案( r i g h t s h i f t e ds c h e d u l e ) 的贪心改进算 法，把关键路径右移的结果就是使是在解序列上被安排的位置也会向后移动，从 4 而可以使得关键路径上的任务被安捧地比较靠前，从而达到改进关键路径，进而 改进解的质量的目的 经过这些改进以后，当使用最好方法时，与文献【2 】求出最优解的差距约在 1 - 3 内。但是，该遗传算法有两个致命的弱点，第一就是参数的控制当交配 算子、变异算子不同。结果的影响是很大的，在论文【3 】的实验中，该结果约在 5 内第二就是原算法所使用到的关键路径，基于右平移的贪心，都是需要很 高的算法基础的，也即该论文的实现难度较高同时，问题改变以后，关键路径 等都需要重新设计，可扩展性差。 第4 章扩展性强的束搜索算法 本章在介绍传统的束搜索算法的基础上( 节4 1 ) ，提出由本论文所建立的可 扩展性强的束搜索算法( 节4 2 - 4 6 ) ，从而解决集装箱装卸设备联合调度问题 4 1 束搜索简介 现代生活、生产都会遇到许多n p h a r d 问题。虽然现在还没有完全把n - p c 和n t h a r d 问题的复杂度定性，但是基本都认为都不可能存在多项式可解的算 法。过去为了解决n p h a r d 问题，都是使用时间复杂度极高的深度优先搜索、 广度优先搜索，以及引申出来的分支定界、a 算法等，这些算法都是为了寻求 最优解为目的的。但是时间复杂度极高，基本都不可接受。 近年提出来的智能启发式算法，像神经网络，禁忌搜索，遗传算法，模拟退 火，蚁群算法等，都是对问题求近似解，因此从效率上都比传统算法要优，而在 实际应用中，不必非要求一个最优解，需要的是一个可行的，相对优秀的结果即 可。因此这类智能算法得到很大的应用。 本文所使用到的束搜索也是智能算法的一种，可以归纳到禁忌搜索或者局部 搜索一类范畴里。他的基本框架是广度优先搜索，通过一层一层的不断扩展，直 到得到问题的解为止。他与广度搜索不同处在于，广度搜索是不限制结点生成数 的，而束搜索是限制生成数的，通过一系列的估算，计算每个结点的费用( 耗散) ， 然后只保留所需要的一部分结点，被保存的那部分结点我们称为一束结点 ( b e a m ) ，而整棵搜索树就像一束结点( 而不是树形) ，因此得名束搜索( b e a m s e a r c h ) 。 4 1 1 柬搜索的基本思想 束搜索是基于广度优先搜索的。因此需要把搜索过程分成一些阶段( 层) ， 计算出每个阶段的点的费用，只保留最有价值的前b w 个点( b w 是可变，但变 化幅度很小) ，然后仅对这b w 个点进行扩展，类似的继续下去( 这里，我们把 这样的方法简写成t o p b w ) 。 1 6 束搜索最早是被应用在语音识别系统中【2 l 】o w 和m o r t o n 首先研究了束搜 索的性能和表现，并且在安捧调度问题上与其他启发式方法进行了比较，他们还 使用束搜索去解决s i n g l em a c h i n ee a r l y t a r d yp r o b l e m 和f l o ws h o pw e i g h t e d t a r d i n e s sp r o b l e m 并获得了不错的解 2 2 1 。n a i r 等人也把柬搜索应用在产品线设计 问题上 2 3 1 。 因为束是要经常增加、删除、修改，而且都是对前b w 个结点进行处理，因 此常用的数据结构都是堆，堆的增加、删除、修改的复杂度都为o ( 1 0 9 b w ) ，是 一种非常高效的数据结构。 下面是一个束宽( b w ) 等于2 的示意图( 图禾1 ) ： 解解 图禾l 束宽为2 的示意图 4 1 2 束搜索的名词说明 束搜索必须实现下列6 个方面： 1 层。即对于束搜索的扩展过程中，必须把问题的求解过程分解成一层层 的扩展过程，因此必须定义束搜索中每一层是如何划分的。 2 结点。柬搜索中结点可以分成下列几类： 曲已经扩展的结点这就是前面搜索中已经扩展完的结点原则上是 不必保留的。 ”待扩展的结点。这些结点都在当前层，并且已经经过估算，是需要 扩展的。 曲新建立结点这些结点都在下一层上这通过对这些结点评价，即 可按序找出前面b w 结点按照传统束搜索，剩下来的结点都可抛 弃。 3 领域操作符。即如何生成下一层结点。显然，尽量少的生成下一层结点 就可相对的减少了估价函数( 通常都是复杂，效率不高的) 的利用，就可提高柬 搜索的速度但减少生成的结点数可能会把更优的解抛弃掉 4 束宽。即每层需要保留多少个结点。束宽越大，能得到最优解的概率越 大，因此得出来的解也是更优，但是，束宽大了，就增加了运行时间，因此，束 宽要选择合理的大小。 5 结点的费用估算。因为结点是只有解的一部分，所以需要对结点尚未生 成的部分进行估算，一个强大的估算函数就可让整个束搜索算法有质的飞跃。但 是，这个函数是非常难寻找的( 谁可预料将来呢) ，而整个束搜索最困难的就是 这点。 6 结点的挑选。即搜索束需要保存的是什么结点。显然，传统算法使用的 是t o p b w 算法，即经过费用估算以后取前面b w 个作为下一层扩展结点。但是， 由于估算函数本身就是建立在不确定因素之上，因此最优解不一定就在这b w 个 点之中，但是除了b w 个结点之外的结点是相当多的，这些点如何选择，也是 束搜索讨论的问题之一。 显然，由于费用的不可精确求得，他是建立在估算之上的，因此束搜索是不 能保证得到的解是最优的。也即束搜索也是一种求近似解的方法。本论文针对上 述6 点，对联合调度问题进行探讨。 4 2 束搜索层的定义 由文献【2 】可知，原问题可对应于一个全排列。因此搜索的目标就是搜索一个 最优的全捧列 对于一个全排列万= ( j o b i , ，y o b , 2 ，弘如) ，显然一个束搜索的中间过程即可 对应于一个全排列的前k 1 个数。当需要扩展时，就为从k 1 个数增加到l 【2 个数 而这样的过程即为一层。 考虑l 【2 和k l 的差值，可以选择l 或者更大的数。对于大于1 的情况，由于 由k l 产生的结点数将会以指数级增加( 复杂度为任务数的指数级) ，这些结点不 仅仅要估算其费用，还要处理入束操作，t o p b w 操作，复杂度极高。因此本论 文只考虑每次只扩展一个任务的情况，即一层即对应于扩展一个任务 4 3 柬搜索的领域操作 束搜索中领域操作包括结点的生成。由于束的宽度相对可生成的结点的数目 是很小的，因此只希望生成可能入束的，对那些不可能入束的，或者重复的结点 应该避免生成。 4 3 1 产生下一状态 由上面分析可知，本论文定义一层的结点即为一个全排列的前部分，即第k 层对于全排列的前k 个任务。对于每一层的扩展，就为由k 个数增加一个数，成 为全排列中的前k + 1 个数。 4 3 2 可扩展结点的限制 对于第k 层的某个结点，根据上面层的定义及结点生成的方法，则需要生成 n - k 个子结点，这对于束宽( 在实验中，n - k 可达1 0 0 0 ，而束宽只有2 0 ) 来说是 很大的。为了减少这些子结点生成，本论文先固定一个结点扩展顺序( 这在下面 将会有所定义) ，然后只选取前面的若干个结点。至于数目是多少，可以以一个 9 参数的形式固定，本论文中所使用到的参数为f w 4 3 3 对结点入束的限制 束搜索可能出现的一种情况是，到达某一层以后，整个束的结点都是由一个 或者少量几个结点生成，也即解的退化。这种现象我们是不希望出现的，因为这 只能达到小范围的局部最优，问题的求解当然希望尽量的全局最优，因此应该避 免这种情况发生。 本论文采用的也是参数控制的办法。也即，限制某个结点生成的子结点入束 的数目。在本论文中该参数以m p 表示。当生成了f w 个子结点后，即对这f w 个子结点排序，只选取前面的m p 个进行入束。这个过程实际操作可以只保留当 前费用最优的m p 个结点( 本题是费用最小的m p 个结点) ，一旦生成一个子结 点即对这m p 个结点比较，如果都比他们大，则该新生成的结点抛弃，如果比任 意一个小，则抛弃前面m p 个结点的费用最大的结点。由此，可以再简化为仅仅 比较这m p 个结点的最大费用，比最大费用的结点小则替换最大费用的结点( 最 大费用结点需要重新寻找) ，比最大费用大则抛弃新生成的结点。 这里或许可以考虑保存费用最大的两个结点，因为替换最大费用的结点以 后，最大费用的寻找可以改为与第二大费用结点的比较。这看起来好像可行，事 实上是不行的。因为一旦这个第二大费用结点变成最大费用后，则需与第三大费 用结点比较来取得第二大费用结点，那就要加入考虑最大的三个费用结点了。由 此下去，也就只能比较全部结点。所以保存费用最大的两个结点是不可取的。最 大费用的结点替换以后，必须重新寻找现在m p 个结点的费用最大结点。 4 4 结点费用的评价 束搜索最关键部分即为结点的评价。通常来说，结点的估价函数可表示为 f = - g + h 。f 为估价函数值，g 为历史结点费用，h 为预计费用。对于本调度问题， 因为可以用一n 的全排列表示，假设当i i 结点在第k 层时，g 即为| j k 个任务的 费用，而h 即为尚未扩展的n - k 个任务的费用的估算。 显然，g 是非常容易求的，而且可以精确求解( 历史总是可以评价的) 。而h 却不可能得出精确费用( 将来总是不可测的) ，因此h 成为整个束搜索的关键h 越接近真实费用，则束搜索越精确但是，h 越精确也会导致程序复杂性