（交通信息工程及控制专业论文）分组调度算法在船闸调度中的应用研究.pdf

摘要 京杭运河是我国南北水运的重要枢纽，是国内船舶、货运流量最大的内河航 道。运河上的船闸具有提高航道尺度、改善水流条件、沟通水系联系等功能，同 时承担着对通行船舶的调度管理。近年来，随着货运量和营运船舶数量的不断增 加，京杭运河船闸的实际通过能力已经接近或超过设计通过能力，船闸待闸现象 愈来愈严重，严重的影响了京杭运河经济效蘸的发挥和沿线工农业发展的需要， 也降低了水运企业的经济效益和水运在综合运输体系中的竞争力。如何在现有船 闸条件下提高船闸服务的吞吐量和保证船舶过闸服务的公平性，具有一一定的实月j 价值。 本文对船闸运行管理和过闸船舶组织形式进行了详细的分析，在此基础上 尝试将网络服务中的分组调度算法应用到船闸调度当中。分析总结了各类分组调 度算法的优缺点，针对船闸自身的特点，设i 十了一种比例公平( p f ) 分组调度算 法，该算法的特点在于：在兼顾公平性的基础上，船闸尽量为服务速率大的队列 分组服务，以此来提高系统的吞吐量。在提也调度策略方案后，使用m a t l a b 语言 对算法进行了实现。最后本文进行了对比性系统仿真实验，通过直观的数据分析 表明：该算法在吞吐量与公平性之间达到了平衡，验证了本文提出的分组调度算 法的有效性。 关键词：船闸；分组调度；吞吐璧；公平性；p f 调度算法 t h er e a s e a r c ho na p p l i c a t i o no fp a c k e ts c h e d u l i n g a l g o r i t h mi n l o c ks c h e d u l i n g a b s t r a c t t h eg r a n dc a n a li sav e r yi m p o r t a n th i n g eo fi n l a n dw a t e r w a yt r a n s p o r t a t i o n ，i t s s h i pn u m b e ra n df r e i g h tt r a f f i c i st h eb i g g e s to n eo fn a v i g a b l ei n l a n dc h a n n e l s s h i p l o c ko nt h ec a n a lp l a y si m p o r t a n tr o l e si n r a i s i n gc h a n n e ls c a l e ，i m p r o v i n gc u r r e n t c o n d i t i o n ，c o n n e c t i n go t h e rw a t e rs y s t e m ；a l s os h i pl o c kt a k e sc h a r g eo fs c h e d u l i n g s h i p st op a s sl o c k i nr e c e n ty e a r s ，w i t ht h ei n c r e a s i n go ff r e i g h tt r a f f i ca n dt h en u m b e r o fs h i pi nw o r k ，a c t u a lt h r o u g hc a p a c i t yo ft h eg r a n dc a n a ll o c kh a sn e a r l yr e a c h e do r e x c e e d e dd e s i g n e dc a p a c i t yt h a tr e s u l t si ns e r i o u ss h i pd e l a yi ns h i pl o c k t h er e s e a r c h o nh o wt oi m p r o v et h et h r o u g h p u ta n de u s u r et h ef a i r n e s sh a ss o m ep r a c t i c a lv a l u e ， i nt h i st h e s i s ，s h i pl o c ko p e r a t i o nm a n a g e m e n ta n ds h i pa r r a n g e m e n th a v eb e e n s t u d i e ds y s t e m i c a l l y o nt h eb a s eo ft h i ss t u d y , p a c k e ts c h e d u l i n ga l g o r i t h mi nn e t w o r k s e r v i c ei sa p p l i e dt os h i pl o c ks c h e d u l i n g ，a l s oa n a l y z ea n ds u m m a r i z es e v e r a lk i n d so f p a c k e ts c h e d u l i n ga l g o r i t h m ，t h e nd e s i g nan e wa l g o r i t h mc a l l e dp r o p o r t i o n a lf a i r p a c k e ts c h e d u l i n ga l g o r i t h m ( p f ) w i t hc o n s i d e r a t i o no ft h ec h a r a c t e r i s t i c so fs h i pl o c k o nt h eb a s eo fe n s u r i n gr e l a t i v ef a i r n e s s ，i no r d e rt oi m p r o v et h r o u g h p u t ，s h i pl o c kt r i e s b e s t 蛔s e r v es h i pp a c k e tw i t hh i g hs e r v i c es p e e d 。a tl a s t ，t h i st h e s i si i s cm a t l a b s i m u l a t i o nt oc o m p a r et h i sa l g o r i t h mw i t ho t h e ra l g o r i t h m s ，t h er e s u l tp r o v e si t sv a l i d i t y k e yw o r d s ：s h i pl o c k ：p a c k e ts c h e d u l i n g ：t h r o u g h p u t ：f a i r n e s s ；p fs c h e d u l i n g a l g o r i t h m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究j 作所取得的成粜， 撰写成博士硕士学位论文 ：筮鳖遢壤簋逵查艘闷词廑生鲍虞旦殛筮! ：。除沦文 中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已往文 中以明确方式标明。本论文中不包含任何末加明确注明的其他个人或集体已经公 开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签氢氧：岛嚼加年3 月哆h 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 ：本学位论文属于：保密口 不保密口( 请在以上方框内打“”) 论文作 跌 第1 章绪论 1 1 本文研究背景 作为代表我国古代水利突出成就的京杭大运河，是世界上开凿最早、规模最 大的人工河道，长度和时间都是世界运河史上酋屈一一指的。京杭大运河全长1 7 8 2 公里，远在2 5 0 0 年前的春秋时代就已开挖，7 0 0 年前的元朝就已具有今天的规模 了。京杭运河北起北京，南至杭州横跨海河、黄河、淮河、长江、钱塘江k 夫 水系n 建国初期，京杭运河仪有山东、江苏和浙江境内6 6 0 多公里可常年通航。 从1 9 5 8 年起，国家交通部开始对京杭运河进行大规模治理，到目前为止，京杭运 河山东段( 济宁至徐州) 的航道等级达已到了三级，年通过能力提高到2 6 0 0 多万 吨：京杭运河苏北段( 以下简称苏北运河) 经过两次大规模的治理，目的大部分 航道为二级航道，2 0 0 2 年通过能力已超过一亿吨：京杭运河苏南段和浙江段建成 了四级航道，可通航5 0 0 吨级驳船队。在国民经济中，运河运输发挥着越来越前 要的作用。 其中，苏北运河是京杭运河全线通航能力最好的一段，在我国内河航运中仪 次于长江，也是贯穿江苏南北的唯一水上通道。它北自微山湖南口江苏徐州的蓠 家坝起，南至运河与长江交汇处的扬t 1 、i 邢江区六好口止，全长4 0 4 k m ，水头总落 差为3 1 _ 1 m 。经过一k 世纪五六十年代和八十年代两次大规模的整治，到2 0 0 1 年， 已依次建成了解台、刘山、皂河、宿迁、刘老涧、泅阳、淮阴、淮安、邵伯和施 桥十个梯级的现代化大型双线船闸( 见图1 1 ) ，货运量由1 9 5 7 年的9 2 万吨，增 加到1 9 7 9 年的1 7 0 0 万吨，随后又于1 9 9 4 年和2 0 0 1 年分别达到5 1 0 0 万吨和9 3 0 0 万吨l2 1 。 一般来说，船闸作为内河中具有提高航道尺度、改善水流条件、沟通水系联 系等功能的通航建筑物，己被广泛地应用于航道的治理。目前，我国已建有9 0 0 多座船闸，主要分布在京杭运河、长江水系、珠江水系等，有效地改善了航道条 件，促进了水运的发展。不过，由于船闸的上、一f 游存在水头差，船舶不能连续 通行，而需经过船舶进出、闸门启闭、闸室灌泄水等过程，将耗费一定的时间， 船闸的通过能力是有限的。大多数情况下，一条航道的运输能力往往取决于船闸 的通过能力。尽管船闸的数量不断地增加，尺度越来越大，通过能力4 i 断增人，但 是，通过运河的船舶数量和吨位也在迅速地发展，船闸的发展总跟不 ：运量的需 求，成为运河运输的“瓶颈”。 随着苏北运河的货运量不断增j 】口，船闸的通过能力已不能满足通航要求，船 舶待闸时间越来越长。据调查，皂河至淮安段的6 座船闸，在一股情况f 约有大 半年的时间待闸船舶量在4 0 0 艘天( 约合2 2 个船队天) 占：右，待闸时间约有2 3 天。根据施桥船闸和淮安船闸的运行资料统计表明，2 0 0 1 年施桥船闸船船的 年平均待闸时间为3 4 小时，2 0 0 2 年淮安船闸则达到了1 3 1 4 小日i j 。愈来愈，“ 重的船舶待闸现象不仅影响了京杭运河经济效益的发挥和沿线工农、m q ：产的需 要，也降低了水运企业的经济效益和水运在综合运输体系中的竞争力【3 j 。 本文旨在通过研究船闸运行过程中的调度算法，将网络服务中的分组调度算 法应用到船闸调度当中，通过分析各个算法对船闸吞吐量和公平性的影响设计 出一种适合船闸调度的算法，使船闸在通过能力定的情况f 保证各种船舶高效、 公平地通过船闸。 幽1 1 苏北运河航道图 1 2 研究现状 由于早期的船闸调度主要是人】：调度管理，我国在船闸 _ f 算机调度疗丽的研 究起步比较晚。进入九十年 e ，随着计算机的普遍应用，讨算机调度的优势显现 出来：首先，速度快，可以在几秒钟内迅速得到编排方案；其次，采用计算机编排 可以产生比较精确和相对最优的编排调度方案；另外，采用计算机编排产牛调度 方案基本消除了人的感情因素；而目，利用计算机可以根据其体要求迅速产_ 多 种可行方案供参考。基于以上优点，计算机船闸调度研究取得了很大的发展。 其中，华中理工大学的卢方勇等人对三峡工程永久船闸的过闸调度编排问题 进行了深入的研究，提出了一种改进的矩形件优化排样算法【4 j 。其优化调度编排算 法的思想是：首先按指定的权值选择函数确定出每个来船的过闸优先级，然后按 优先级别的高低，将来船排序( 在计算机b ；接着，从中挑选出大约能排满一个闸 室且具有较离优先级的船只，准备编排：先将整个闸室视为一一个大矩形，按照一 定的寻优规则，在矩形中每次尽可能地先排放面积( 船长与船宽的乘积) 较大的 船只，同时每次排放都会产生一些较小的矩形，然后，用还未编排的船鼠继续填 充这些小矩形，直到所有的船只排完或闸室摊满：如果闸室已排满，并且还有船 只未编完，则按优先级高低重新挑选船只进j 亍下个闸室的编排，如此继续，随 到所有船只摊完。这种算法可以最大限度的提高闰室面积利用率，提高了船闸的 吞吐量。但由于该算法每次都比较优先选择排放面积较大的船舶，闲此导致顽积 小的船舶可能长时间得不到服务。 刘云峰、齐欢设计了一一种船闸调度决策算法l s i ，建立了解决船闸n p 完全i o j 题 的数学模型，提出了一种启发式算法：将待排船只队列按权重进行排序得到待排 船只队列，再建立一个己选船只队列，然后把待排船只队列中排在第位的船只 放入原为空的己选船只队列，每将一艘船s h i p 从待排船只队列放入己选船只队列 就进行如下操作：调用类似卢方勇等人提出的矩形件优化排样算法的快速编排算 法( 不是真正的以“优先级高的船优先参与编排”为原则的，所以并不实用) ，将 此时的己选船只队列中的船只赋给快速编排算法中的待排船只队列，如果此时己 选船只队列中的船只全部能通过快速编排算法放入闸室，则将最后加入已选船只 队列的那艘船s h i p 保留在欧列中，否则将s h i p 从己选船只队列中剔除。然后将放 在待摊船只队列中下一个权重较高的船只放入已选船只队列继续进行如j 二的运 算。直到待排船只队列为空为止，则最后保留在己选船只队列中的船只就是最后 选中的船只。因为算法总是首先试探权重高的船，高权重的船放不进去，j 试探 低权重的船，这一点对低权重船舶的来说是不公平的。由于修f 的贪婪算法中每 加入一艘船都调用一次快速编排算法，所以运算时间稍长，而且闸室面积利用率 与快速编排算法的结果接近。 为了提高船闸的运行效率和服务质量，韩建平采用c s 体系结构，设计了运 河船闸船舶调度系统【6 】。该系统将船舶信息登记、船舶调度、船舶收费、运行管理、 闸次公告和综合信息流程等模块有机的融合在同个网络系统中( 见图i 2 ) 。其 中船舶调度模型是根据船舶放行的各种条例，以及各船闸自身的特点，被格式化 为一组调度规则，管理部门可以根据需要和实际情况取舍。这样既可以规范管理、 杜绝行业不正之风，又可以适应各船闸不同的应用需求。系统开发完成后，于1 9 9 9 年在京杭运河施桥船闸投入运行，系统的成功运行提高了船闸的船舶通过率和科 学化管理水平，给船闸管理带来了可观的经济效益和社会效益。 逛 行 管 理 管理 规则 模式 船舶登记 船舶调度 闸费征收 键 柱 待闸船舶、) | 综合信息鸯询 拟过闸船舶)电子大屏幕 已过闸船舶- - l 闸次公告 图i 2 系统逻辑结构 杜经农、余绍明研究了多个并联船闸的智能调度问题，并使用动态规划理论 建立了该问题的数学模型，提出了一种基于滑动窗【j 方法的算法，很好地满足了 自动编制船闸调度计划的需求5 刀。该调度方法建立u 二= 三个限制条件：应尽量满足重 点船舶按时过闸，但也要求编制的计划使所有船舶的总体等待时间最短：编制的 4 计划应使船闸面积利用率尽量高：使3 个船闸尽量均衡使用。经过分析研究，调 度计划的编制具有马尔可夫特性，作者选用动态规划求解。在实现算法i ：，由于 浚问题属于多维、大级数动态规划。由_ f 微机计算速度有限，使用传统解法在微 机上无法实现，因此使用了一些创新的思路和方法，采取“墒部全局规划”的处 理办法：在每5 个阶段的范围内进行局豁动态规划，求取局部问题的解；然后向 后滑动3 个时间段，得到下一个局部过程，再次求解：最后对1 6 个局部过程进彳 第二次规划一全局规划，求取全局解。此外，还利用了数据库技术，对每个局 部阶段解的全集使用约束条件过滤后，将可行解集存入数据库，利用数据库存储 容量大、排序与怆索速度快的优势来进行船舶信息的排序和检索。 李中华在现代先进的网络通讯基础上运用排队论、决策论等最优化理论，建 立一种能充分共亭各种船舶调度信息的船闸优化调度模型，提高船闸闸室面积利 用率，减少船舶等待时间，实现船舶快速、安全过闸1 8 1 。作者针对目前我国船闸运 行调度信息共享性差、调度效率不高、不能充分发挥船闸通过能力的现状，根据 船闸运行调度流程及相关的业务规则，采用三层结构数据库开发技术建立了一一套 基于i n t e m e t i n t r a n e t 的船闸优化调度决策系统。采用该系统可以简化船舶过闸申 报手续、规范调度作业流程。同时应用排队论、决策论、整数规划等最优化理论， 从船舶到达规律、船闸运行策略和船舶过闸调度决策三方面深入研究了船闸的运 行调度方法。在船舶调度策略部分作者提出了船型调度决策和船只调度决策的概 念，并建立了相关的船型调度判别指标和船只调度决策的数学模型。针对船只调 度决策的核心一船舶空间调度问题，深入探讨了不同调度期望目标下的船舶空间 调度问题，最终建立了一种行之有效的船闸优化调度数学模型，设计了相关的算 法。 国外相关研究较少，其中美国学者c r o g e r g l a s s e y 和s h e l d o n m r o s s1 9 l 应用排队论理论对m i s s i s s i p p ir i v e r 上的多线船闸的调度管理进行了研 究，该文设计的m g 1 排队模型较好的预测了拥塞状况下船舶的平均等待时间， 同时该模型可以针对不同的调度策略对平均等待时间的变化进行评价。h o y tg w i l s o n i l o l 应用计算机仿真技术和m g 1 排队模型，对不同驳船到达率情况f 的 等待时间的上卜边界和吞吐能力进行了研究，为船闸调度管理提供了有力的支持。 s h a u g e r 博士的研究报告【1 1 l 针对运河上的船闸和船舶设计了一种中心交通控制系 统，浚系统在考虑所有船闸和船舶的基础上，对吞吐能力和船舶等待时间进行j 7 优化。r a y a m u n d a y 等人【1 2 l 在前人研究的基础上，将离散事件仿真模型引入到伊 利诺斯河多船闸系统仿真当中，该模型将季节性相互关联的交通需求和季节性k 分调度策略合并在系统仿真中，分析了不同调度策略对船闸运行效率的影响。 以上关于船闸调度的研究主要集中在如何提高闸室面积利用率，缩短船舶等 待时间，以及提高船闸运行效率j ：。对于待闸现象严重的运河船闸，如何解决船 闸吞吐量与服务公平性之间的冲突，具有很大的现实意义，但目前阁内这方_ 甬1 的 研究尚没有人做过。 1 3 本文的主要工作 本文主要对船闸调度的分组调度算法进行研究。主要内容如下： 讨论了船闸传统的运行管理模式和到闸船舶种类特性。 阐述了分组调度算法的原理、分类和性能指标等相关知识，分析研究了分 组调度的性能评价标准。介绍了几种典型的分组调度算法并分析了各个算法的优 缺点。 建立了船闸运行调度过程的多队列、单服务器的排队模型，从船舶到达规 律、船闸运行策略和船舶过闸调度策略深入研究了船闸运行调度方法，提出了吲 行的解决方案。 采用计算机仿真模拟技术，对船舶调度模型进行了验证，通过计算机仿真 得到了一些有指导意义的船闸调度规律和方法。 第2 章船闸运行管理 2 1 船闸运行管理单元 在船闸的同常运行和管理中，有两项工作是很重要的：一是船舶过闸费的征 收；二是船舶进闸的调度。征收的过闸费是用来管理和养护航道，以达到“以航 养航”的目的；而船舶进闸调度是为r 提高船舶航行安全和船闸的吞吐能力。“一1 于船闸的吞吐能力有限，通常会有大量的船舶等待过闸，所以必须合理地对这些 船舶进行调度，以确保船民的利益和提高船闸管理的质量。作者实地考察了江苏 施桥、谏壁船闸等运河船闸的运行管理模式，为了有效的完成收费和调度任务， 保证船舶快速安全通过船闸、保持航道畅通，一般需要7 个部门共同协作工作， 即：上游海事登记站、下游海事登记站、船闸上游远方调度室、船闸下游远方调 度室、船闸中间票房、船闸上游调度室、船闸下游调度室。这些管理单元分散卉j 置在船闸上下游两三公里范围内1 8 1 1 ”1 。图2 1 是一个典型的船闸管理机构布嚣图。 嘲2 1 船闸远行管理单元布置示意图 22 船舶过闸流程 【 开始 】 船舶进入 上游停泊区 t 登记等 待调度 调度进入上游 引航道待闸 t 开t 游闸门船 舶进入闸室 i 缴纳过闻费 t 开下游闸门 船舶出闸 f 行流程 船舶进入 f 游停泊区 t 登记嚣 待调度 调度进入f 游引 航到待闸 上 开f 游闸门船 舶进入闸室 i 缴纳过闸费l 0 开上游闸 船舶m 闸 图2 2 船舶上f 行流程圈 船舶在航行过程中，每到一个船闸处，首先到海事部门登记处登记，然后再 到船闸远方调度室登记并缴费，再由船闸调度室根据一定的原则对船舶进行调度， 被调度选中的船舶就可以通过船闸了。详细的船舶过闸流程为| ：1 4 1 ： ( 1 ) 到登记站登记，领取管制号； ( 2 ) 凭管制号，到船闸远方调度室登记并缴费( 售票) ； ( 3 ) 船舶听候调出( 调度) ； ( 4 ) 被调出的船舶进入引航道待闸： ( 5 ) 调度室调度进入闸室； ( 6 ) 进闸后再到中间票房根据牌号换幽有关证件 ( 7 ) 船舶出闸； 具体的流程图如图2 2 所示； 2 3 过闸船舶类型划分 一般地，京杭运河苏北段营运船舶包括以下类型：单放船、挂机船、自划船( 义 称人力船、木排) 、帆船、工程船、驳船、拖轮、船队等等。另外，根据船舶装载 的货物的种类的不同，我们还可以把船舶分为危险品船和非危险品船( 包括空船) 。 目阿，何种类型船舶可以起调度，没有统一规定，不同船闸之间各有不同。怍 者认真研究了各种类型船舶的机动特性及相关的调度方法，结合中华人民共和 国航道管理条例、船闸管理办法等规定得出以下的船型划分准则： ( 1 ) 船队、大铁驳等船舶( 本文中我们统一称之为船队) 的机动特性、船舶嘶积 尺寸和单放船、挂机船、工程船等( 统称之为单船) 差别较大，相应的进出船闸方式， 调度策略也各不相同，因此必须分别调度，不能混合进闸。 ( 2 1 出于安全考虑，装有危险品的船不能和装菲危险品的船一一起进闸，必须分 别调度，分开进闸。 ( 3 ) 重载非危险品单放船和空载单放船的机动特性、相应的进出船闸方式差- 3 日 较大，因此也必须分别调度过闸。 似1 挂机船由于机动性能差、安全性能低必须单独过闸。 r 5 1 危险品船的数量较少，因此我们规定危险品船队和危险品单船可以混合过 闸。 根据以上的船型调度划分准则，我们可得到下面的过闸船舶类型：我们将过 闸船舶分为船队、重单船、空单船、挂机船、危险品船等五类船型分别调度过闸。 另外，在船闸优化调度过程中我们还得遵守以下船闸调度原则： f 1 1 夜间只能调度船队过闸，不能调度单船。 ( 2 1 白天优先调度单船。 9 ( 3 ) 原则上先登记的船舶优先被调度。 ( 4 ) 对于提放的船舶，应让其优先过闸。 ( 5 ) 每条船都必须在有限时间内被调度进阐。 ( 6 ) 每一个闸次尽量只通过一种船型。 2 4 过闸组织形式 为安全和便于操作起见，苏北运河船舶过闸组合的方式主要有三种：船队f i ：l 合，单放船组合及挂机船组合。具体过闸形式如下【1 5 】。 ( 1 ) 船队组合：一般个船队作为一个闸次，特别繁忙的时候考虑船队组合。 比如淮安船闸，在繁忙时期，大船队作为个闸次，一般的船队有时和个小的 船队组合，有时将船队解缆，一个半船队作为一个闸次。一般情况船型| ：i = 混放， 但是当待闸船型极不平衡，船队不好排闸时，考虑小船队和钢制单船混放过闸： 水泥质船碰撞极易漏水成沉船，不能和其他船舶混放。见图2 3 。 图2 3 船队过嘲 ( 2 ) 挂机船组合：挂机船相对来说较小， 一般是根据船舶条数来组台调度，如 淮阴和施桥以1 3 2 0 条为标准，有时以一次过闸货运量为标准，如淮阴船闸繁忙 时候以设计通过能力2 1 0 0 吨为标准，但是水泥船、危险品船要单独过闸。 f 3 ) 单放船组合：单放船的数量在苏北运河上呈上升趋势，而且大型化趋势非 常明盟。单机船一般几百吨，有的己经超过一千吨。单放船的过闸组合方式基本 上同挂机船，但闸次的船舶数量略有调整，根据调查，目前主要有1 2 条的缀合。 除此以外，在繁忙时期过闸的组织形式也会有所调整。由于待闸船舶较多， 船闸在组织调度时一般都是预先排闸，有时会将不同的船型混放，如船队过闸刚 船闸还有富余，会附带一二艘单船，但考虑到安全以及过闸效率般不混放。单 船分组过闸见图2 4 。 圈2 4 单船过闸 2 5 船舶过闸时间的确定 船闸过闸时闾的长短是影响船闸运行效率的重要因素，为了深入研究过闸时 问，作者将船舶过闸时间分解为：船舶进闸时问珞，闸室内等待时间和出闸时 间五。三个时闻段。 ( 1 ) 进闸时间 闰2 5 船舶进闸时间 船舶进闸时间珞是指已被调度的船舶在开始进闸到全部进入闸室所消耗的叫 问。可出两部分的时间组成。由图2 5 可知船闸进闸时间一般由第1 艘船在闸 室丽引航道内的航行时间岛i 和第i 艘船进入闸室与第i - 1 艘船进入闸室时问司隔，。 两类时间组成，因此船舶进闸时间我们可以用下式表示： 强一锄+ 。 1 ) ( 2 ) 等闸时间 闸室内等待时间瓦可进一步分为闸门关闭时间、闸室充泄水时间、闸门丌启 时间三个时间段，对于一确定船闸，闸门启闭时间基本上为常数，闸窀充泄水州 问在一段时间内也可近似为一常数。因此对于闸摩内等待时问一一般恒为一常数， 可优化的空间不大。 ( 3 ) 出闸时间 b 二j 一一。问 l 三一一， 图2 6 船舶出闸时间 船舶出闸时间毛是指已被调度的船舶在船闸闸门打开后，闸室内第艘船舶 玎始出闸到全部船舶驶出引航道所耗费的时间。同进闻时问，由图2 6 可知船舶甜j 闸时间。般由最后一艘船在引航道内的航行时间f ；l 和第i 艘船开出闸室与第i - 1 艘 船开出闸室的时间间隔f 两类时闻组成，因此船舶出闸时间我们可以用下式表示： 轳j i + 蓦j 2 一次过闸时间，应根据船舶、船队进出闸时间，闸门启闭时间，充泻水时间， 船舶、船队进出闸时间，可以根据其运行距离和进出闸速度确定，并符合下列蠼 定： 对于单级船闸，一次过闸时问应符合1 i 列规定： ( 1 ) 单向过闸 正= 强+ 焉+ 瓦；= 如l + t 2 + 丑3 + f 4 + 丑5 ( 2 3 ) 式中r l 一单向次过闸时间( h ) t l - - f 门或关门时唰( h ) f 2 - 单向第一个船队进闸时问( h ) t 3 一闸室充水或泻水时间( h ) f n 一单向第一个船队出闸时间( h ) t 5 一船舶、船队进闸或出闸间隔时间( h ) ( 2 ) 双向过闸 7 h = 4 t l + 2 ：+ 2 f 3 + 2 ：+ 4 t 5 ( 2 4 ) 式中疋一上、下行各一次的双向过闸时间( h ) t7 2 双向第一个船队进闸时间( h ) f ，4 双向第一个船队出闸时间( h ) ( 3 ) 一次过闸时间应根据单向过闸和双向过闸的闸次比率确定。当单向过闸与 双向过闸闸次数相等时，可按下式确定： 丁三( t + 吾) s ， 其中丁一次过闸时间 已知船队和单船进出船闸平均速度，见表2 1 1 1 6 1 。船闸闸室长为( m ) ，船队进、 出闸至闸首距离为d ( m ) ，规定各个船舶进入闸室时间间隔船为“h ) 。 表2 t 进出闸平均述度 过闸方式进闸平均速度“；闸平均速度 ( m s )( m s ) 船舶类型 单向双向 单向烈向 船队 0 50 7o 7l0 机动单船 0 71 o1 o14 船闸运行参数见表2 2 。 表2 2 船闸运行参数 【关门时间( r a i n ) 开门时间( m i n )充水时间( m i n )泻水时间( r a i n ) 2 2 8 8 ( 1 ) 船队过闸时间确定 图2 7 船闸尺寸 由于船队每次只可以通过一个船队，过闸时间由通过引航道和闸室的时间，等 闸时间( 开关闸门时间，灌水泻水时间) ： 通过引航道和闸室时间：百a 五+ i t 面：+ 五a 再+ 丽l 2 等闸时间：4 t 1 + 2 t 3 过闸时删：丁螗队= 石考专；磊石+ 石与专；等石+ 甜。+ 丑， c ：6 ， 4 其中屯一开门或关门时间( 小时) f 3 一闸室充水或泻水时问( 小时) f 2 ) 单放船过闸时间确定 单放船过闸时f 白j 应考虑过闸船舶数量的影响，设过闸数量为m 。 进闸时间：旦生一+ m 一1 l o 7 3 6 0 0 等闸时间：4 t 。+ 2 t ， 出闸时间：一! 二兰= + 研f 1 o x 3 6 0 0 过闸时间：。破船；面丽a + l+ b l ，+ 五妻篡丽+ m f + 4 f ，+ 丑s 2 ( 3 1 挂帆船过闸时间确定 挂机船过闸时阃应考虑过闸船舶数量的影响，设过闸数量为h 。t 表示先后进 入船闸两艘船舶的时间间隔( 单位：h ) 。 进闸时间：百亍a 丽+ l + 0 1 等闸时闯：4 t ，十织 出闸时问：a - - i - _ l _ l + n f 1 0 过闸时间：k 帆船一百再a 丽+ l+ b 一1 + i 瓦a 蕊+ l + 眦+ 4 f ，+ 2 f ， ( _ 2 8 ) 2 6 本章小结 章介绍了船闸管理部门的主要机构设置和其相关的功能，以及船舶到闸排剜 的一般规则，最后分析了船闸运行时间的计算方法。 第3 章分组调度算法 在本章中首先结合船闸运行情况概述了分组调度算法的原理、分类和性能 指标等相关知识，接下来分析研究了分组调度的性能评价标准。 3 1 分组调度算法的原理 调 度 、 分 三单放船队列卜j 器 类 船舶到达 啼 垒 鲁 璺& 臻 巳 空 乌 一 叫挂机船队列r 一 图3 1 分组调度示意图 调度是系统资源管理的核心机制之一，是解决多个业务竞争共享资源问题的 有效手段。分组调度算法是一种对不同队列所属分组进行调度的机制，以使得备 个队列的分组之间减少相互干扰，避免系统性能因拥塞而下降f ”1 。将分组调度算 法应用于船闸调度研究当中，通过分析到闸船舶的类型和船舶过闸编排习惯，将 到闸船舶分为船队，单放船和挂机船三种队列进行分组，放入不同的队列当中， 然后按照一定的调度策略调度通过船闸，见图3 1 。 分组调度主要是按照一定的规则，决定船闸服务哪一队列的船舶分组过闸， 使得所有船舶能够根据预定的方式通过船闸。它的目的是使各种类船舶以较高的 效率通过船闸。主要性能指标包括吞吐量，等待时间和公平性等，是船闸服务的 核心内容。 鉴于船闸运行的特殊性( 每一个闸次通过一种类型船舶) ，有必要运用分组调 度方法进行研究。 船闸分组调度策略都是采用多队列排队机制，这就涉及到对多种类船舶进行 有区别的服务，称为c q s ( c l a s s i f i c a t i o n ，q u e u e i n g ，s c h e d u l i n g ) 1 18 1 ，如图3 2 所示。 兰要包括三个部分：船舶交通流分类、队列管理、分组调度。 分类：船舶到达船闸后，根据船舶类型将不同种类船舶放入相应的队列卦儿 对列管理：由于船闸运行每一个闸次对于某一种类的船舶的服务能力是比较 固定的，在队列中将船舶按照闸次容量分为几个分组等待过闸服务。 分组调度：分组调度的作用是决定下+ 个闸次服务的船舶种类，这是本文研 究的主要对象。 c ：分类o ：队列管理s ：分组调度 图3 2 多队列调度系统的功能组成 3 2 分组调度算法的分类 对于某一种特定的调度算法，根据不同的分类标准，又t 可以属于多个不同l ! 种类，没有统一的分类标准。 根据不问的服务规则，可以分为：先到先服务，轮询服务( 依次进行服务) ， 优先级服务和随机服务等。 根据调度目标，可以分为基于等待时问，基于吞吐量和基于公平性。 图3 3 先入先出】：作机理 3 2 1 先入先出 最简单的分组调度就是先入先出( f i f o ) 。先入先出耩于典型的被动式队列管 理方法，它调度各个对列中船舶分组的方法是：所有船舶类型到达船闸，首先进 行分组，按照形成一个分组的先后顺序进入船闸接受服务。先入先出是平十简荦 高效的服务方式，不足之处是f i f o 不能满足公平性，当某一船舶种类入批萤i ：到达 时，会造成其它种类长时间得不到服务。见图3 3 。 3 2 2 基于优先级的调度算法 圈3 4 基于优先级调度算法 基于优先级的调度算法( 见图3 4 ) 就是给每个队列赋予不同的优先级，每 次需要调度时，具有较高优先级且达到数量要求的队列优先被选择服务，姻累最 高优先级的队列为空，或者队列中的数量达不到船闸服务的要求，则选择次优先 级的队列进行服务。这样被分配到较高优先级的队列按照事先的设想优先得到服 务，其等待时问就比较小，通过吨位也相对较大。这个算法实现起来比较简举， 但是它有致命的缺点，由于调度机构对于高优先级的队列优先服务，这样当在某 一时间段内有大量该队列的船舶到达时，会造成船闸在一段时间内被陔队列全部 占用，其它队列的服务质量将无法得到保证，即低优先级的队列长期得不到服务， 产生“饿死”现象，公平性很差【1 9 l 。 解决优先级调度算法中低优先级“饿死”的对策是分隔队列，即设置调度阀 值。q l t ( o u e u el e n g t ht h r e s h o l d ) 为每一个队列设爨调度阀值，需要进行调度时从 最高优先级开始比较队列的长度和调度阀值。当最高优先级队列长度人j 二等j 二调 1 8 度阀值时，该队列先到的船舶批次首先被选择服务，当最高优先级队列的长度小 于其调度阀值时，不再服务调度该队列，而是检查具有次高优先级的队列，依次 类推。通过调度阀值的合理配置，q l t 算法能够对队列进行简单的分隔，限制j - 它们之间的相互影响，提高了公平性【捌。 3 2 3 基于轮询的调度算法 常见的基于轮询的算法有r r ( r o u n dr o b i n ) ，w r r ( w e i g h t e dr o u n d - r o b i n ) ；_ f 1 d r r 。 图3 5w r r 调度算法的工作机理 传统的r r 只是简单的对所有队列进行轮询调度，一次调度发送一个队列的船 舶分组，使得不同船舶队列在某种程度上“平等”地占用船闸。然而，由于不1 司 种类的船舶尺寸差异较大，不同种类船舶每一闸次通过的数量不同，例如由r 船 队船型很大，一个闸次只能通过一个船队，服务船队会导致其它船型的等待时间 过长，使队列之间产生不公平的现象。 加权轮询调度算法( w r r ) ，在r r 算法的基础上为每一个队列赋予了 个权 值，同时为每一个队列维护一个计数器，在每次轮询时，计数器为非零的队列可 以接受一批服务，计数器的计算方法为：初值为权值，每发送一批船舶计数器减 ，当所有队列的计数器都为零时则一个周期结束，所有计数器重置，卜惆期 开始( 见图3 5 ) 。w r r 算法能够提供很好的公平性，同时以较为平滑的方式调度 船舶通过船闸。 1 9 3 2 4 基于延时的调度算法 基于待闸成本的调度算法，由于不同船舶类型的经济效益不问，等待相同的 时间所造成的损失各不相同，调度算法刁i 能简单的根据待闸时间确定接受服务的 船舶种类，而应该根据船舶的等待成本大小进行调度。由f 各种类船舶待闸成本 的确定比较复杂，本文不对其进行细致分析，有待子进一步研究。 33 分组调度策略的性熊评价标准 由于船闸存在闸室面积和服务速度等方面的限制，而且备个队列之问存在竞 争的问题，各队列的通过吨位和待闸时问很难同时保证，有时候它们是互相抵触 的，如某一队列的通过吨位很大而待闸时问过短，就会导致其他队列的通过吨俺 很小，等待时间过长，无法满足公平性的要求。同时满足多个指标的要求是非常 困难的。因为在某些情况下备个指标之间可能存在矛盾，因此任何一种实际的分 组调度策略都只能对多个服务质量要求进行折衷。 33 1 吞吐量 吞吐量( t h r o u 【g h p u t ) 是一个重要的性能参数，它反映了某个时问段内船闸所 服务的船舶吨位。它是一个静态参数，反映了系统的负载情况。单位时间内的吞 吐量则称为吞吐率。吞吐量是船闸调度管理的一一个重要指标。对于船闸管理者来 说，通过船闸的吨位越大，说明船闸的利用率越高。 3 32 胍务公平性指标 公平性则考虑对所有这些请求服务的队列而言，各个队列是否都享有 定的 服务机会。最理想的情况是所有队列享有相同的服务机会，这样的算法将是最公 平的。如果一些队列得到了很多服务机会，而在相当长的一段时i b j 内另一些队列 始终得不到服务机会，这种调度算法就是不公平的i ”。 3 3 3 延时 延时是衡量系统性能的重要参数，它可以采用多种方式来表示，这里主要是 指从船舶到达待闸区到通过船闸所经历的时间。分组的队列延迟由i 部分组成： ( 1 ) 由于在服务中另外一一个分组的到达而使这个分组所收到的平均服务时问。 ( 2 1 由于同一队列中它前面的分组而使这个分组所经历的延时。 ( 3 ) 由于其它队列中在它之后到达而在它之前被服务而使这个分组所产生的 延时。 3 ，4 分组调度算法，j 、结 分组调度是实现系统服务质量控制的核心机制之一，是系统资源管理的重爱 内容，通过控制不同队列的分组对船闸的占用，使不同队列的分组得到不问等级 的服务。 分组调度的基本过程是根据一定的系统信息做出判断，控制各个队列- j ，用船 闸的频率，进而影响吞吐量、公平性等性能指标。一般来讲，考虑的信息越多， 算法越有效，复杂性也就越高。先进的队列调度算法都是把分组按照种类存放存 不同的队列罩，然后为其计算一个动态优先级作为控制参数，根据这些参数进行 调度【2 3 】。 3 5 本章小结 本章主要将分组调度原理进行了阐述，并结合船闸运行将分组调度引入到船 闸调度管理当中，对几个主要的分组调度算法进行了简要的介绍，分析了各个算 法的优缺点。最后提出了评价分组调度算法的几个性能指标。 第4 章算法的设计与实现 在船闸调度系统中，每段时问内只向一种船舶提供过闸服务。为了提高系统 的性能( 吞吐量) ，系统应该优先向单位时间服务吨位大的船舶队列提供服务。这 样以来单位时间通过吨位小的船舶队列可能长时间褥不蓟服务。因此，引入“调 度”概念，在保证系统综合性能的同时，所有队列都能获得适当服务。调度算法 的目的是合理分配系统资源，以提高系统的吞吐量和公平性。 在调度算法研究中，有两个重要的方面需要考虑，一个是吞吐量，一个是公 平性。 吞吐量一般用单位时闻内服务船舶吨位来表示，单位是吨小时。最理想的情 况是船闸始终以最大的通过量为船舶服务，这样的算法吞吐量是最大的。由于船 舶类型的多样性，在多种类船舶过闸的船舶调度系统中，简单的追求吞吐量是不 切合实际的。 公平性则考虑对所有这些请求过闸的船舶队列而言，大家是否都享有一定的 服务机会。最理想的情况是所有队列享有相同的服务机会，这样的算法将是最公 平的。如果某些船舶种类得到了很多服务机会，而在相当长的一段时间内其它船 舶队列始终得不到服务机会，这种调度算法就是不公平的。 好的调度算法，应该兼顾吞吐量和公平性，得到一个比较好的折衷l 矧。 4 1 最大单位时间通过吨位，调度算法 4 1 1 算法原理 最大单位时间通过吨位算法就是在选择服务船舶队列时，只选择单闸通过吨 位大的船舶，即让单位时间内通过量大的船舶队列分组不断通过船闸，直至队列 为空再让其它种类通过。 如果在时刻f 有k 个种类船舶请求过阐服务，此刻每个种类的单位时间通过 吨位玑( f ) ，则u 一调度算法选中的服务种类为( a r g 表示归一化) ： 虹a r g ，m 。a x + , ：，( f ) ( 4 1 ) 选择u 最大的船舶队列，也就是船闸每次服务的都是当前各队列中单位时间 通过吨位最大的船舶种类。因此，该算法的吞吐薰是吞吐量的极限值，无论使用 任何别的算法，吞吐量都不可能超过它。 但是在船闸调度中，由于船队、单放船和挂机船的船型、吨位上的差别，此 算法更多的考虑了u 大的船舶队列，得到更多的服务机会。这将不可避免的使u 小的船舶队列，按照这种调度算法，船舶得到服务的机会很少，甚至出现“饿死 现象”，这样一来，这种最大u 调度算法是最不公平的。 4 1 2 算法实现 系统仿真中采用函数m a x _ u ( e h o o s e l ) 来实现最大，调度算法。本函数的功 能是使用最大u 调度算法得到系统吞吐量、等待时间和各个种类调度次数等参数。 最大u 调度算法的基本原理就是：每一个调度决镱时刻选择服务速率u 最大的种 类对其进行服务，其函数流程图如图4 1 。 4 2 基于轮询调度算法 4 。2 1 算法原理 这种算法循环的调度各个队列中的船舶分组，就被调度上的概率而言，对k 个队列，每个队列被服务的的概率： p ( k ) - l 置 ( 4 2 ) 也就是说每个队列以相同的概率占用系统资源，这种基于轮询的调度算法是 最公平的。 但是由于各个队列的，不同，服务值小的队列的比重增大，那么吞吐量势 必大大减小，影响到整个系统的性能。 42 2 算法实现 系统仿真中采用函数r o u n d r o b i n ( c h o o s e 3 ) 来实现轮询调度算法，本函数的功 能是使用轮询调度算法得到系统吞吐量、等待延时和各个队列被调度次