（管理科学与工程专业论文）港口集装箱作业计划模型研究.pdf

一 h 0 - 1 一 f _ l 厶_ m o d e l i n gs t u d yf o rp o r tc o n t a i n e ro p e r a t i o np l a n n i n g at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g b y z h a ox u e j i n g ( m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g ) t h e s i ss u p e r v i s o r ：p r o f e s s o rc h e nj i a m a y 2 0 1 1 7246 98jly 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文! = 鲞旦塞苤笪簋些进剑搓型婴塞：。除论文中已经注明引用的 内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本论文中不包含任何未加明确注明的其他个人或集体已经公丌发表或未公丌发表 的成果。本声明的法律责任由本人承担。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属丁：保密口往年解密后适川本授权f 5 。 不保密盯( 请在以上方框内打“”) ：幽蜂新躲邴札 日期：矽f 年多月汐日 中文摘要 摘要 集装箱运输自从2 0 世纪5 0 年代中期在美国出现以来，由于这种运输方式可 以有效的提高单件杂货的装卸效率、节约包装材料、增加货物在运输过程中的安 全性、减少货损货差以及便于丌展多式联运等优点，在短短六十多年的时间内得 到了蓬勃发展，但集装箱运输也是一种资本密集型行业，船舶在港时i 日j 直接影响 客户及整个港口的经济效益，船舶在港时问主要取决于装卸时间，而装卸机械岸 桥又是一种稀缺的昂贵资源，它的工作效率直接决定着整个港口的收益，因此如 何制定合理的装卸顺序提高岸桥利用率、最小化船舶在港时间、提高客户满意度 已成为各个港口竞争力的重要体现。 集装箱作业顺序问题是如何在满足一系列约束条件的情况下为集装箱分配合 适的岸桥，并确定各个岸桥上集装箱作业顺序，使得最后完工岸桥的作业时i 日j 最 短。该问题非常类似于柔性作业车间调度问题，但是由于岸桥位置等特殊因素的 限制它比柔性作业车问调度更复杂，本文在对调度问题及集装箱作业研究的基础 上建立了集装箱作业顺序的数学模型。 集装箱作业顺序问题关键是解决资源分配和排序问题，是u p h a r d 问题，求 解具有相当的空1 1 叫复杂性和时间复杂性，是典型的组合优化问题。组合优化方法 主要包括精确方法与近似方法，本文通过对各种优化算法进行比较分析，最后选 择蚁群算法对该模型求解，蚁群算法是一种新型进化算法，它的j 下反馈、负反馈、 并行性等优点使其在解决组合优化问题方面显现出一定的优越性，但它发展还不 成熟也存在收敛速度慢，容易出现早熟的缺点，文章针对这些不足用一种改进后 的蚁群算法对集装箱作业顺序模型求解，以克服以上不足。 最后将改进的蚁群算法用c 拌n e t 语言实现，并进行实证分析，以2 个岸桥对 5 个贝进行作业为例，若采用传统方式按贝作业，第一个岸桥的作业时间为2 0 2 ， 第二个岸桥作业时间为3 0 4 ，而采用本算法后两个岸桥作业时间均为2 5 6 ，实验表 明，使用该算法要比传统方式得到的结果要好得多，进而达到了本文研究的目的。 关键词：集装箱作业顺序；改进的蚁群算法：柔性作业车间调度；调度优化方法 英文摘要 a b s t r a c t s i n c et h ec o n t a i n e rt r a f f i ca p p e a r e di nt h em i d d l e19 5 0 si nt h eu n i t e ds t a t e s ，a s t h i sm o d eo ft r a n s p o r tc a ni m p r o v et h el o a d i n ga n du n l o a d i n ge f f i c i e n c yo fb r e a kb u l k c a r g oe f f e c t i v e l y , s a v ew r a p p e r ，i n c r e a s et h es e c u r i t yo fc a r g od u r i n gt r a n s p o r t a t i o n ， r e d u c et h el o s sa n dd a m a g ea n db ec o n v e n i e n tf o rm u l t i m o d a lt r a n s p o r ta n ds oo n ，i n j u s ts i x t yy e a r st i m e ，c o n t a i n e rt r a f f i cd e v e l o p e dq u i c k l y h o w e v e r i ti sa l s oa c a p i t a l i n t e n s i v ei n d u s t r y , s h i pt u m a r o u n dt i m e sa tt h et e r m i n a ld i r e c t l ya f f e c te c o n o m i c b e n e f i to fc u s t o m e r se v e nt h ew h o l ep o r t t h et i m es p e n ti np o r t sl a r g e l yd e p e n d so n l a y t i m e ，a n dq u a y s i d ec o n t a i n e rc r a n ei sas c a r c ea n de x p e n s i v ec o n t a i n e rh a n d l i n g m a c h i n e r y , i t sh a n d l i n ge f f i c i e n c yd i r e c t l yd e c i d e st h ep r o f i to fp o r t t h e r e f o r e ，h o wt o m a k ear e a s o n a b l eh a n d l i n go r d e rt oi m p r o v et h eu t i l i z a t i o nr a t i oo fq u a yc o n t a i n e r c r a n e ，m i n i m i z es h i pt u m a r o u n dt i m e s ，i m p r o v ec u s t o m e r ss a t i s f a c t i o ne t ch a sb e c o m e t h ei m p o r t a n te m b o d i m e n to ft h ec o m p e t i t i v e n e s sb e t w e e np o r t s c o n t a i n e rh a n d l i n gs e q u e n c ep r o b l e mi st o d i s p a t c h a l lt h eq u a yc r a n e st o c o n t a i n e r si nas e r i e so fc o n s t r a i n tc o n d i t i o n sa n dt od e t e r m i n et h eh a n d l i n go r d e ro ft h e c o n t a i n e r so nc r a n e s ，a c h i e v et h ep u r p o s eo fm i n i m i z i n gt h em a x i m u mh a n d l i n gt i m eo f c r a n e s t h ep r o b l e mi sv e r ys i m i l a rt ot h ef l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ，b u td u e t os o m es p e c i a lf a c t o r ss u c ha sl o c a t i o nc o n s t r a i n to fq u a yc r a n e s ，s oi ti sm o r ec o m p l e x t h a nf j s et h i sp a p e rp r e s e n t sam a t h e m a t i c a lm o d e lf o rc o n t a i n e rh a n d l i n gs e q u e n c e p r o b l e mb a s e d o nt h es t u d ya b o u ts c h e d u l i n gp r o b l e ma n dc o n t a i n e rh a n d l i n g c o n t a i n e rh a n d l i n gs e q u e n c ep r o b l e mf o c u so no p t i m i z i n gm a c h i n ea s s i g n m e n t a n ds c h e d u l i n g i ti sat y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ，a n dh a sb e e np r o v e d t ob en p h a r d ，t h es p a c ea n dt i m ec o m p l e x i t yo fs o l v i n gi sr a t h e rh i g h c o m b i n a t o r i a l o p t i m i z a t i o na l g o r i t h mm a i n l yc o n t a i n se x a c tm e t h o da n da p p r o x i m a t i o nm e t h o d t h e p a p e rf i n a l l yu s e sa n tc o l o n yo p t i m i z a t i o n ( a c o ) t os o l v et h ep r o b l e ma f t e ra n a l y z i n g a n dc o m p a r i n gk i n d so fc o m b i n a t o r i a lo p t i m i z a t i o na l g o r i t h m s a c oi s an e w e v o l u t i o n a r ya l g o r i t h m ，d u e t oi t sf e e d b a c kw h i c hi s p o s i t i v e o rn e g a t i v ea n d p a r a l l e l i s m ，i t ss u p e r i o r t os o m eo t h e ra l g o r i t h mw h i l e s o l v i n g c o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m h o w e v e r , i t sd e v e l o p m e n ti sf a rf r o mm a t u r e ，i ta l s oh a ss o m e s h o r t c o m i n g ss u c ha ss l o wc o n v e r g e n c ea n dp r e m a t u r ec o n v e r g e n c ee t c t oo v e r c o m e 英文摘要 t h ed e f a u l to fb a s i ca c o ，a n i m p r o v e da c oi si n t r o d u c e da n dd i s c u s s e dc o n c r e t e l vi n t h i sp a p e rt os o l v ec o n t a i n e r h a n d l i n gs e q u e n c ep r o b l e m f i n a l l y , i m p l e m e n tt h ei m p r o v e da c ow i t hc l a n g u a g eo nc o m p u t e r , a n dc o n f i r m i tb ye x a m p l e s ，t a k i n gd i s p a t c h i n g2q u a yc r a n e st o5b a y sf o re x a m p l e ，o p e r a t i o nt i m e o fo n eq u a yc r a n ei s2 0 2 ，t h eo t h e ri s3 0 4i nat r a d i t i o n a lw a y i nb a yt os c h e d u l e ， h o w e v e rh a n d l i n gt i m eo fb o t h2q u a yc r a n e si s25 6s c h e d u l e db yi m p r o v e da c o t h e r e s u l ts h o w st h a ti m p r o v e da c oi sm u c hb e t t e rt h a nt r a d i t i o n a lw a y , t oa c h i e v et h e p u r p o s eo ft h es t u d y k e yw o r d s ：c o n t a i n e rh a n d l i n gs e q u e n c e ；i m p r o v e da n tc o l o n yo p t i m i z a t i o n ； f l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ；o p t i m a l s c h e d u l i n ga l g o r i t h m 目录 目录 第1 章绪论1 1 1 课题研究背景1 1 2 港口集装箱作业顺序现状分析2 1 3 本文的工作及组织结构4 第2 章调度问题及其求解方法综述j 5 2 1 组合优化5 2 2 调度问题概述7 2 2 1 调度问题的定义7 2 2 2 调度问题的分类7 2 2 3 实际调度问题的特点1 0 2 2 4 调度问题的评价体系1 1 2 2 5 调度问题的现状分析以及发展趋势1 l 2 3 柔性作业调度概述1 2 2 3 1 柔性作业调度问题的提出1 2 2 3 2 柔性作业调度与经典作业调度的比较1 3 2 3 3 柔性作业调度的分类一1 4 2 3 4 柔性作业调度问题的描述及其数学模型1 4 2 3 5 柔性作业调度的现状分析1 6 2 4 生产调度问题的求解方法1 7 2 4 1 精确方法1 7 2 4 2 近似方法18 第3 章基本蚁群算法研究2 3 3 1 蚁群算法基本原理2 3 3 2 人工蚂蚁与真实蚂蚁的比较2 6 3 3 基本蚁群算法求解旅行商问题2 8 第4 章基于改进蚁群算法的集装箱作业调度模型研究3 4 4 1 集装箱作业概述3 4 4 1 1 问题描述3 4 4 1 2 集装箱介绍3 4 4 1 3 装卸机械岸桥的介绍3 5 4 2 集装箱作业模型3 7 4 2 1 集装箱装卸顺序描述。3 7 目录 4 2 2 集装箱装卸顺序数学模型以及解释3 8 4 2 3 集装箱约束的矩阵表示以及传递闭包算法：4 l 4 3 求解集装箱作业顺序的改进蚁群算法4 2 第5 章集装箱柔性作业顺序的实证分析4 7 5 1 所用到的数据结构以及算法实现4 7 5 2 试验结果及分析5 3 5 3 算法中各参数的选取5 9 第6 章总结与展望6 2 6 1 总结6 2 6 2 展望6 3 参考文献6 5 攻读学位期问公丌发表论文6 9 致谢7 1 港口集装箱作业计划模型研究 第1 章绪论 1 1 课题研究背景 集装箱运输自从2 0 世纪5 0 年代中期在美国出现以来，在短短六十多年的时 间内得到了蓬勃的发展，集装箱运输通过把单件杂货装入集装箱，由水、陆、空 等不同的运输方式不问断的运送，将物品由发货方直接送到收货方，从而实现了 门到门的服务，是人类在运输界的一个重大变革】。使用集装箱运输可以有效的提 高单件杂货的装卸效率、节约包装材料、增加货物在运输过程中的安全性、减少 货损和货差、以及便于丌展多式联运等，这将极大限度的满足客户的需求，由于 集装箱运输方式具有许多单件杂货运输所不具备的优点，因此随着世贸组织成员 的不断增加，集装箱运输已经成为各国之问进行贸易运输的主要方式和各国运输 现代化的主要标志，以往任何一种运输方式都不可能代替集装箱运输在现代运输 中的地位和作用。 随着经济全球化的不断发展，我国集装箱吞吐量已经超过美国居于世界首位， 集装箱吞吐量的不断增长也使得船舶向大型化和高速化的方向发展，如一些世界 著名的集装箱船的装载能力甚至达到1 0 0 0 0 标准箱以上，这同样也给我国集装箱 码头的作业能力带来新的挑战，如果集装箱码头作业效率仍保持不变，这势必会 制约大型船的运作，从而使船舶在港时间过长，直接影响到运营成本和货主的切 身利益，因此随着船舶不断的大型化，对集装箱码头的作业效率提出了新的要求。 由于集装箱码头中的泊位、场地以及机械等是非常有限的，集装箱运输也是 一种成本密集型运输体系，因此如何提高设备利用率、最小化船舶在港时间、提 高客户满意度已经成为各个港口竞争力的重要体现，船舶在港时间主要包括停泊 时间、卸载时间、装载时间和离丌时间四部分，而装卸时i 日j 是决定船舶在港时问 的关键因素，因而船舶运营商和港口经营者热衷于制定能够提高装卸效率的船舶 作业计划，达到在保证船舶稳定的情况下，最小化驻留时间的目标。 集装箱装卸桥本文中简称岸桥，是一种价格非常昂贵的用于装卸的专用设备， 它是集装箱码头装卸的主力军，它的工作效率直接决定着船舶的在港时间，由于 岸桥的额定载荷是确定的，为了提高岸桥的工作效率，通常都是通过提高机构的 第l 章绪论 行走速度来实现，但这势必会影响岸桥的工作寿命，而影响集装箱码头的整体效 益，在以往装卸过程中，通常是以贝为单位进行作业，这样往往会使得一个岸桥 已经完成工作，而由于岸桥之间必须保持一定的安全距离而使得其他一些岸桥闲 置，最后一个岸桥的完成时问决定了船舶的在港时间，因此，近年来如何制定一 个合理的装卸计划来提高岸桥的作业率、减少岸桥闲置时间，成为许多集装箱码 头最为关心的问题之一，而目前国内外对该问题的研究还不够成熟，但这又在港 口实际运作过程中具有重要的价值，因此，本文就如何制定一个合理的装卸顺序， 来在岸桥额定载荷的范围内，最大化所有岸桥的工作效率进行了研究求解。 1 2 港口集装箱作业顺序现状分析 d a g a n z o 2 】岸桥调度问题，是第一篇真f 意义上论述岸桥作业调度的文章，作 者在该文中以所有延误惩罚费用最小为目标建立混合整数规划模型，从而确定分 配给多个船舶的岸桥数，并采用精确方法和近似方法求解，用实例验证近似方法 比精确方法更加容易求解大规模问题；p e t e r k o f s k y 3 】贝4 在d a g a n z o 研究的基础上， 通过提高岸桥装卸效率来最小化船舶在港时间，将岸桥调度模型看作是丌放式车 间调度问题，岸桥被视为没有任何差别的同种机器，并用分支定界对该模型求解； k i m 和p a r k 4 】考虑了实际操作中各种制约因素，将岸桥调度看作平行机调度问题， 建立了该问题的混合整数规划模型，并用分支定界法对其求解，得到了每个岸桥 的作业顺序，最后又提出一个贪婪随机搜索的启发式算法克服分支定界中计算复 杂的缺点，并获得较好的解；j f s h e n 将分支定界法引入到禁忌搜索法中，以嵌套 式遗传算法的形式求得了一个用户可以接受的满意装卸方案【5 1 ；d e r - h o m gl e e 6 】 对集装箱码头作业进行研究，将船舶集装箱按船舱划分，建立了考虑到岸桥之间 安全作业距离的混合整数规划模型，并用遗传算法给出了岸桥作业的顺序。 国内对集装箱作业顺序也有不错的研究成果，如：缪立新在文献【7 】“集装箱 装船顺序优化模型及算法研究”中建立一个用于优化集装箱装船顺序的动念整数 规划模型，该模型将堆场作业、岸桥装卸、以及集装箱在不同港口的作业整合在 一起，同时还考虑到集装箱在堆场和船上的位置以及配载完后船舶的稳定性等因 i 素，该模型研究的目标是在“装载一运输一卸载”整个过程中倒箱次数最少，并 用遗传算法对该模型进行求解，并用正交因子对参数进行分析；文献 8 】中综合考 港口集装箱作业计划模型研究 虑到集装箱之间的顺序约束、设备调整时间、岸桥之间的位置约束等建立了岸桥 作业的混合整数规划模型，该模型的目标通过岸桥的合理调度来使所有作业的完 成时间最小，用启发式算法对边装边卸的混合作业模型进行求解，并在该算法中 引入了基于连续b a y 的作业规则、最短作业时f h j 规则( s p t ) 、最长时i u j 作业规则 ( l p t ) 和随机规则( r a n d o m ) 等，最后通过数据验证了采用连续b a y 作业规则和s p t 可以节省装卸时i 目j ，进而使算法取得更好的优化结果；梁亮，陆志强【9 】将集装箱码 头调度系统描述为混合流水作业的延伸，并为其建立数学模型，由于集卡并非瓶 颈设备，因此将其从模型中分离出去，将模型简化为如下两阶段，第一阶段是在 不考虑集卡的情况下对岸桥、厂桥进行调度，第二阶段是在岸桥、厂桥调度完成 的条件下对集卡进行指派，并用j o h n s o n 法则的启发式算法对其进行求解，以减少 码头对船舶的作业时间；梁亮【lo 】还在硕士论文中首先用遗传算法对集装箱码头岸 桥调度进行优化，然后用j l s 算法对集装箱装卸系统在单装或单卸情况下的调度 问题优化，并在前两者的基础上建立了集装箱码头的混合装卸模型，用拓展析取 图对该问题分析，提出了改进后的基于模板的双层t a b us e a r c h 方法并对其求解； 文献【11 q h 曾庆成，杨忠振等人建立了集装箱码头作业的双层优化模型，上层模型 的目标是最小化集装箱装卸时| 1 ；i j ，下层目标是最小化集卡的行驶路径，用遗传算 法对该模型求解，通过上下层模型问的反馈与相互作用决定集装箱码头作业调度 的整体优化方案；刘晓燕【1 2 】在硕士论文“集装箱装卸计划自动编制研究”中综合 考虑集装箱和列车位置的基础上建立集装箱双层车辆配载模型，并运用启发式算 法和禁忌搜索算法结合来求得使机械行走路径最短的满意的装卸顺序；屈援，王 雪莲1 1 3 】用加入了禁忌规则的模拟退火算法对有卸货顺序约束的集装箱装卸问题求 解并验证了其有效性。 综上所述，国内外虽然对集装箱作业顺序有一些研究成果，但基本都是用遗 传算法和禁忌搜索等一些发展比较成熟的算法进行求解，蚁群算法是种新型的进 化算法，近年来在求解组合优化问题方面显现出了它独有的优势，但是还没有看 到有文献将该算法应用在集装箱作业顺序求解问题上。因此本文用一种改进后的 蚁群算法对集装箱作业顺序进行优化。 第1 章绪论 1 3 本文的工作及组织结构 集装箱作业顺序问题随着集装箱码头的发展已经需要亟待解决，本文介绍一种 改进的蚁群算法，并用它求解集装箱作业顺序问题，并将该算法在n e t 平台下用 c j f j 语言实现，并用实例验证了了该算法的可行性，本文的组彩：结构如下： 第1 章：主要介绍了课题的研究背景和本课题在国内外的研究现状，并在最 后介绍了本文研究的主要内容和组织结构。 第2 章：主要对本文用到的一些理论知识如：组合优化问题、i p h a r d 问题、 调度问题的分类以及各类调度问题的模型进行研究，最后介绍了柔性作业车间调 度( f j s p ) 的描述、模型、分类以及特点等，并对调度问题的求解方法进行介绍， 并对这些算法进行比较研究。 第3 章：阐述了基本蚁群算法的原理，并以旅行商问题为例来对基本蚁群算 法的模型和求解步骤进行详细说明。 第4 章：本章节主要对集装箱、岸桥进行简单介绍；并对集装箱作业顺序问 题建立了数学模型，用传递闭包的算法求解集装箱约束矩阵；针对基本蚁群算法 容易出现早熟的现象和收敛速度慢等问题介绍了一种改进的蚁群算法，并且用改 进后的蚁群算法对该作业模型的求解进行了研究。 第5 章：用c n e t 对第4 章中的算法进行实现，对在实现中用到的一些数据 结构和主要方法进行简单介绍，并用一个直观简单的例子来对改进后的蚁群算法 进行分析验证，证明使用该算法要比原始的用以贝为单位作业的方式要好的多， 进而达到了本文研究的目的，最后对算法中各个参数的选取进行了分析。 第6 章：对本文进行总结以及对未来集装箱作业顺序发展的一个展望。 港口集装箱作业计划模型研究 第2 章调度问题及其求解方法综述 2 1 组合优化 在现实生活中，为了最大限度的节省资源、降低成本，出现了许多最优化利 用资源的问题【14 1 。最优化问题往往指从一组可行解中选取出最优解或最适应解的 过程【15 1 。总体来说，优化问题有如下两类：一科，是连续变量的优化问题；另一种 是离散变量的优化问题，该问题又叫做组合优化问题，前者的解通常是一组实数 或一个函数，而后者则是从一个无限集合中寻找一个对象，该对象可以是一个整 数、集合、排列甚至是一个图【1 6 】。 组合优化是- - a - j 既古老又年轻的学科，它是数百年前一些数学家们偶然提出 的问题与方法，一些著名的学者如：f e r m a t 、e u l e r 都在其形成和发展过程中作 出了极其重要的贡献，在二十世纪中后期以来，随着科学技术、现代化管理尤其 是计算机技术的不断发展，组合优化问题已经逐渐发展为运筹学中的一个独立分 支，并且在物流管理、交通运输与规划、网络通信、决策、调度等领域发挥了不 可替代的作用【17 1 。 所谓组合优化问题，是指在一个有限并且离散的数学结构上，寻求一个在满 足一系列约束条件的情况下，使得目标函数最大或者最小的解；通常来说，组合 优化问题存在大量的局部极值点，该模型一般是不连续、不可微、多维的、有约 束条件的、高度非线性的u p h a r d 问题f 1 4 】：所提到的u p 问题是指不存在一个 问题规模以的多项式p ( n ) ，使得一个算法可以在最坏的情况下对该问题至多进行 以以) 次基本运算f 1 6 1 。 通常组合优化问题可以定义为：q = 鸽，s ：，s 。) 为所有可行解组成的解空 间，c ( 暑) 为状态墨所对应的目标函数值，目标是寻找最优解s 章，使得 c ( s * ) - - m i n ( c ( s i ) ) ，l f n 并- h s * q 1 8 】。 第2 章调度问题及其求解方法综述 组合优化问题的求解方法和连续变量最优化问题的解法不同，组合优化这类 问题都有非常精确的数学模型，计算很复杂，理论上只有枚举方法才能得到问题 最优解【1 9 】。但使用该类方法求解时随着问题规模的不断增大，可行解数目呈指数 型增长，将会导致搜索空间的“组合爆炸”【2 0 】。 组合优化是一种离散最优化问题，它在越来越多的领域得到了广泛的应用， 典型的组合优化问题有旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 、加工调度 问题( s c h e d u l i n gp r o b l e m ) 、0 1 背包问题( k n a p s a c kp r o b l e m ) 、装箱问题( b i n p a c k i n gp r o b l e m ) 、图着色问题( g r a p hc o l o r i n gp r o b l e m ) 等；这些问题的描述都 非常简单，并且有很强的工程代表性，但组合优化问题的求解却很困难，其主要 原因是求解这些问题的算法需要极长的运行时f h j 与极大的存储空间，以致根本不 可能在现有计算机的基础上实现，即会产生所谓的“组合爆炸”1 2 0 。 由于组合优化问题应用的广泛性和求解的复杂性激起了人们对组合优化理 论与算法的研究兴趣，迄今为止，人们对优化问题以及它的求解方法己经相当深 入，已经形成了较为系统的理论体系，并且很多研究成果得到了实际的应用。如 在文献 1 4 d p 作者马玉玲对求解组合优化问题常用的几种近似算法：下次适应近 似算法、首次适应近似算法、降序首次适应近似算法、最佳适应近似算法、降序 最佳适应近似算法等进行了研究，并且用装箱问题的实例来验证这几种近似算法 的优劣；在文献 1 9 】中张鸿宾对几种常用的解决组合优化问题的方法如：局部搜 索法、多起点局部搜索法、模拟退火法、禁忌搜索法、遗传算法进行研究，分析 了这些算法的广泛搜索性和集中搜索性，比较了他们之间的优缺点，以及不同算 法所适用的范围；文献 2 0 1 中马立肖和王江晴通过分析了遗传算法的原理以及特 点，介绍了该算法在组合优化问题中的具体应用，针对传统的遗传算法在求解中 存在的局限性，对传统的遗传算法进行改进，并用旅行商问题对该算法进行验证； 在博士论文【2 1 中作者姚国辉对几个典型的组合优化问题：低度网络设计问题、 路径规划问题还有集合覆盖问题进行研究，并为网络问题提出了最小生成树的一 个精确算法和一个近似算法，为规划问题提出了一种状态空间削减算法，用一个 随机启发式算法对集合覆盖问题求解。 港口集装箱作业计划模刑研究 2 2 调度问题概述 2 2 1 调度问题的定义 从2 0 世纪9 0 年代以来，随着全球竞争的不断加剧，我国的制造业以高速持 续发展，成为带动国民经济发展的主要力量，这j 时也给我固的制造业带来了新 的压力与挑战，因此，企业要想从激烈的竞争中脱颖而出，则必须提供质量最好、 成本最低、速度最快、服务最好的产品来响应市场的需求变化【2 2 1 。伴随着市场竞 争的不断激烈化和客户需求的多样化与个性化，越来越多的企业采用多品种、中 小批量的方式来生产产品，这种离散的生产方式会造成产品生产加工过程中的信 息复杂化且难以控制；生产计划和作业计划的均衡难以实现；拖延产品交货期限， 质量问题得不到保证，经济效益降低等等；由于以上的一系列问题的存在，调度 优化问题应运而型2 2 1 。 调度问题，就是为了实现一个或者多个目标而对共同使用资源进行时问上的 分配【2 3 1 。车间调度问题是调度问题的一个子集，它是在满足一系列等式或者不等 式的约束条件下，将可用的设备集在时间上分配给所有的作业集，并确定作业在 机器上的加工顺序和每个作业的丌始加工时间，目标是使一个或多个调度性能指 标最优【2 4 】。调度问题的定义虽然很简单，但是在实际制造系统中，还要必须考虑 人员、天气等其他一些因素，因此它本身要更复杂，调度问题可以说无时不有， 无处不在，它涉及制造业、运输业、金融业、管理业等许多领域【2 5 1 。 2 2 2 调度问题的分类 随着诸多学者对车间调度问题研究的不断深入，有很多文献对该问题分类作 了论述，但是依据不同的原则有不同的分类，本文对文献 2 2 】、 2 4 、【2 6 、【2 7 、 2 8 】、【2 9 的分类进行了总结，从不同的角度对调度模型进行了分类【2 引。 ( 1 ) 根据研究对象的复杂程度可以将该问题分为以下几类： 单机调度问题( s i n g l em a c h i n es c h e d u l i n gp r o b l e m ) 单机调度问题中有且仅有一台加工设备，所有待加工零件也都仅有一道工 序，所有的零件都在这台设备上进行加工，这是最简单的调度问题【2 2 1 。 并行机调度问题( p a r a l l e lm a c h i n es e h e d u l i n gp r o b l e m ) 第2 章调度问题及其求解方法综述 并行机调度问题是在单机调度的基础上，减少了机器约束的条件，加工系统 中存在一组相同功能的机器，所有工件同样只有一道工序，零件可以在任意一台 机器上进行加工【2 2 1 。 作业车i 日j 调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，j s p ) 在j s p 中，系统中有一组功能不同的加工设备，所有待加工零件有多道工序， 不同零件的加工工艺不同，每道工序在其相应的一台设备上加工，在设备能力和 工件加工路线双重约束的条件下，j s p 的求解变得极其困难，是砌一h a r d 问题 中最困难的问题之一【2 2 1 。 流水车间调度问题( f l o w s h o ps c h e d u l i n gp r o b l e m ，f s p ) 在f s p 中，加工系统拥有一组功能不同的机器设备，待加工的工件包括多 道工序，并且所有工件的加工路线都相同，每道工序在其对应的一台机器上加工； f s p 是j s p 的一个特例，它是将作业车间调度问题中所有工件的加工路线进行统 一，因而要比j s p 简单的多【2 2 】。 丌放式车间调度问题( o p e n s h o ps c h e d u l i n gp r o b l e m ) 在开放车间调度问题中，工件的工序之间没有顺序上的制约，加工调度可以 开始于任何一道工序，结束于任一道工序，工件的加工没有特定加工路线的约束， 因此也是一种比较简单的调度问题【2 2 1 。 柔性流水车间调度问题( f l e x i b l ef l o w - s h o ps c h e d u l i n gp r o b l e m ，f f s p ) 柔性流水车间调度问题又叫混合流水车问调度问题，它是流水车间调度问题 和并行机调度问题的综合与扩展，它在流水车间调度的基础上，至少有一个阶段 可以在多台机器上进行加工【3 0 】。 柔性作业车问调度问题( f l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ，f j s p ) 柔性作业车间调度是经典作业车问调度问题的扩展，在j s p 的基础上消除了 机器惟一性限制，每个工序可以在可选的机器集中的任何一台上进行加工，这使 f j s p 更符合实际的生产实践活动，同样也增加了问题的复杂性，因为它包含两 方面内容，其一要为每个工序分配合理的机器，其二才是工序调度问题；一旦确 定了每个工序的加工设备后，柔性作业车间调度问题便转化成了经典的j s p 3 1 1 。 港口集装箱作业计划模型研究 综上所述，由于f s p 和j s p 在生产实践中的典型性、特殊性以及重要性， 人们将其称为经典的基本调度问题【2 2 】。 ( 2 ) 按照工件的准备状态来说，可将调度问题分成静态调度和动态调度以及混 合调度三类。 静念调度 静态调度又叫做确定性调度，足指在调度的时候，所有作业集中的工件均处 于待加工状念【2 8 1 。 动念调度 动念调度，是指未加工的作业陆续进入待加工状念，然后接受设备的加工， 最后加工完成后离丌系统，同时在加工过程中还应考虑设备修好或损坏、作业未 按时到达、作业加工延时等随机因素的干扰，因此，动态调度随着加工环境的变 化来实时调整，虽然更加符合实际调度但也会增加相应的丌销【2 引。 混合调度 混合调度方式是居于静态调度与动态调度之间的一种调度策略，在丌始时部 分作业已经处于准备加工状态，其他的作业则陆续进入待d i 】- r 状念，先对处于待 加工状态的作业进行静态调度，其余陆续进入准备加工状态的作业采用动态调度 的方式给他们分配机器。 ( 3 ) 基于性能指标，调度问题可以分为最小化调度费用和最优化调度性能两大 指标的调度【2 4 1 。 ( 4 ) 按照调度问题目标的数量分类，可将调度问题分为单目标调度和多目标调 度问题。 只考虑单一优化目标作为评价指标的调度问题称之为单目标调度；考虑多个 优化目标作为评价指标，称之为多目标调度，多目标调度中各个子目标之间既相 互联系又相互制约，因此应该在各个子目标中寻求一种平衡【2 7 】。 ( 5 ) 按照调度时是否允许工序抢占执行，可分为抢占式调度和非抢占式调度。 如果一个工序一旦丌始加工，就不能被中断，机器必须一直等到该工序被加 工完成后才可以加工其他的工序，这种方式是非抢占执行方式；若工序在丌始加 工后允许被中断而把它所占的机器分配给其它工序，称为抢占执行方式2 8 1 。 第2 章调度问题及其求解方法综述 ( 6 ) 根据调度目标的被优化的程度，可以将调度问题划分为最优调度和次优调 度两类。 最优调度追求的是系统目标值的最大化或最小化，而次优调度则以一定的时 间或费用为基准，获得一个用户可以接受的满意解；由于调度问题被证明是砌问 题，求解十分复杂，因此一般采用近似算法获得用户满意解【2 8 1 。 ( 7 ) 就生产方式而言，调度问题分为丌环型调度和闭环型调度。 在开环调度中，调度策略一旦被定下来后，将用已经定好的调度策略来指导 整个调度过程，而不会根据库存大小等一些执行的实际状况来调整调度策略【6 4 1 。 、闭环型调度是将闭环反馈控制策略引人到调度系统中，根据调度实际进行中 资源需求变化状况的反馈来动态调整调度策略，以处理调度过程中产生的没有预 测到的问题，达到优化系统调度性能的目的f 3 2 】。 2 2 3 实际调度问题的特点 ( 1 ) 多约束性 对调度问题研究时，涉及到的资源数量、- r f ：f = 属性、时间限制以及工序之间 的顺序制约等都属于约束条件，在调度过程中不仅要考虑以上约束条件，还应考 虑人、工具、物流等其他约束，此外还应满足一些特殊生产环境中的一些约束条 件【2 6 1 。因此，调度问题本质上是一个多约束条件下的组合优化问题 2 6 1 。 ( 2 ) 离散性 调度问题是典型的组合优化问题，因此