（系统工程专业论文）自动化立体仓库堆垛机调度系统的建模及优化研究.pdf

摘要摘要自动化立体仓库作为现代物流技术领域内出现的一种新型仓储方式，在工业生产中发挥着日益重要的作用。自动化立体仓库堆垛机的调度优化是提高仓库作业效率的关键，因而一直是当前工程优化领域研究的重点。首先，本文以现代物流为背景，阐述了自动化立体仓库与现代物流的关系、自动化立体仓库的调度优化在现代物流系统的重要作用；介绍了自动化立体仓库的分类、构成以及基本概念，为后续的建模及优化调度做铺垫。接着，以自动化立体仓库系统中堆垛机的出入库调度系统为研究对象，并针对其离散性和事件驱动的特点，引入着色赋时p e t r i 网的建模方法。应用该方法构建了自动化立体仓库堆垛机出入库调度问题的模型，为其进一步的研究奠定了理论基础。然后，分析了堆垛机的调度及其调度优化的目标，具体的对堆垛机常见的五种停留策略进行了讨论，并采用概率模型比较了五种停留策略的性能。最后，文章针对堆垛机作业方式的特点进行了分析，提出了堆垛机拣选作业和复合作业方式的优化方法。针对拣选作业方式，提出了含装箱约束的拣选作业的数学模型。经过对模型的分析，指出该模型是一个n p 完全问题，并选用遗传算法对其进行求解。针对复合作业，建立了动态作业路线模型，并通过制定相应的转化规则，将复合作业调度问题转化为t s p 问题，并运用遗传算法对复合作业调度进行了优化。对以上两种作业方式的优化进行了仿真验证，并与随机调度进行了比较，结果表明，优化后的算法能够较大的缩短调度的运行时间。关键词：自动化立体仓库；p e t r i 网；停留策略；复合作业优化；拣选作业优化a b s t r a c ta u t o m a t e ds t o r a g e & r e t r i e v a ls y s t e r n ( a s r s ) ，a san e ws t o r a g ew a ya p p e a r i n gi nm o d e r nl o g i s t i c st e c h n o l o g ya r e a , i sp l a y i n gm o r ei m p o r t a n tr o l e si nt h ei n d u s t r i a lp r o d u c t i o n t h eo p t i m i z e dd i s p a t c ho fs t a c k e ri na s r si st h ek e yo fh i g hw o r ke f f i c i e n c yo ft h ew a r e h o u s e a tf i r s t ，b a s e do nt h eb a c k g r o u n do fm o d e r nl o g i s t i c s ，t h ep a p e re x p o u n d st h ep e r f o r m a n c eo ft h eo p t i m i z e dd i s p a t c ho fs t a c k e ri na s r si nm o d e ml o g i s t i c sa n dt h e i rr e l a t i o n s h i p s t h e ni n t r o d u c eac l a s s i f i c a t i o no fa s r s ，t h eb a s i cc o n c e p t sa n dc o m p o s i t i o n ，w h i c hp l a c e df o u n d a t i o nf o rf u r t h e rs t u d ya n do p t i m i z a t i o n s e c o n d ，c o n s i d e rt h ed i s p a t c ho fs t a c k e ri na s r sa n di t sc h a r a c t e r i s t i co fd i s e r e t ea n dp a s s i v e ，t h ep a p e ri n t r o d u c e st h et i m e dc o l o r e dp e t r in e tm o d e l i n gm e t h o da n db u i l d st h em o d e l i n go ft h ed i s p a t c ho fs t a c k e ri na s r s ，w h i c hh a sl a i dat h e o r e t i c a lb a s i sf o rf u r t h e rr e s e a r c ha n do p t i m i z a t i o n t h i r d ，t h ep a p e ra n a l y s e st h ed i s p a t c ho fs t a c k e ri na s r sa n dt h eg o a lo ft h eo p t i m i z e dd i s p a t c ho fs t a c k e ri na s r s s p e c i f i c ，f i v ed w e l l i n gp o i n ts t r a t e g i e sw e r ed i s c u s s e da n dc o m p a r e dt h ep e r f o r m a n c eo ft h ef i v ed w e l l i n gp o i n ts t r a t e g i e sb yp r o b a b i l i t ym o d e l f i n a l l y , t h ep a p e ra n a l y s e st h ec h a r a c t e r i s t i co ft h es t a c k e r sw o r k i n gm o d e ，a n dp r o p o s e sam e t h o dt oo p t i m i z et h ep i c k i n go p e r a t i o na n dc o m p o u n do p e r a t i o n a i m i n ga tp i c k i n go p e r a t i o n s ，ab o u n dw i t hp a c k i n gm o d e lw a se s t a b l i s h e d a f t e ra n a l y s i so ft h em o d e l ，p o i n t i n go u tt h a tt h em o d e li san pc o m p l e t ep r o b l e m a i m i n gc o m p o u n do p e r a t i o n s ，d y n a m i cr o u t em o d e lw a se s t a b l i s h e d t h r o u g ht h ed e v e l o p m e n to ft r a n s f o r m a t i o nr u l e sc o r r e s p o n d i n gt oc o m p o u n do p e r a t i o n s ，t h ec o m p o u n do p e r a t i o n sp r o b l e mw a st r a n s f e r r e di n t oat s pp r o b l e m t h r o u g hc h o o s i n ga l g o r i t h m ，g e n e t i ca l g o r i t h mw a su s e dt oc a r r yo nt h e s et w ow o r k i n gm o d e r e s u l t so fs i m u l a t i o ns h o w e dt h a tt h eo p t i m i z e dm e t h o dc o u l da b b r e v i a t er u n - t i m eg r e a t l y ,c o m p a r i n gw i t ht r a d i t i o n a lm e t h o d s k e yw o r d s ：a s r s ；p e t r in e t s ；d w e l l i n gp o i n ts t r a t e g i e s ；t h eo p t i m i z a t i o no fp i c k i n go p e r a t i o n ；t h eo p t i m i z a t i o no fc o m p o u n do p e r a t i o n ；厦门大学学位论文原创性声明本人呈交的学位论文是本人在导师指导下，独立完成的研究成果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学术活动规范( 试行) 。另外，该学位论文为() 课题( 组)的研究成果，获得() 课题( 组) 经费或实验室的资助，在() 实验室完成。( 请在以上括号内填写课题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特别声明。)声明人( 签名) ：径勇1 年艺只 日厦门大学学位论文著作权使用声明本人同意厦门大学根据中华人民共和国学位条例暂行实施办法等规定保留和使用此学位论文，并向主管部门或其指定机构送交学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。本学位论文属于：() 1 经厦门大学保密委员会审查核定的保密学位论文，于年月日解密，解密后适用上述授权。() 2 不保密，适用上述授权。( 请在以上相应括号内打“”或填上相应内容。保密学位论文应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权。)社勇第一章绪论1 1 课题的背景及意义第一章绪论1 1 1 课题的背景自动化立体仓库又称为自动存储自动检索系统( a u t o m a t e ds t o r a g e r e t r i e v a ls y s t e m ，a s r s ) ，是一种新型的仓储技术。它是以高层货架为主体，以成套搬运设备为基础，以计算机控制技术为手段的高效率物流、大容量存储的机电一体化高科技集成系统。它集机械、电子、计算机、通信、网络、传感器和自动控制等多种技术于一体，以搬运机械化、控制自动化、管理微机化、信息网络化为特征，成为现代化物流设计中产品生产与存储的枢纽【l 7 】。目前，自动化立体仓库系统主要有两大应用领域：其一是各种自动化生产线中的在线立体仓库系统，如c i m s中的在线立库系统；其二是各种物资配送中心如超市配货中心等。1 9 5 9 年世界上第一座自动化立体仓库在美国阿尔巴马州建成。之后，美国于1 9 6 3 年建成了世界上第一座计算机控制的自动化立体仓库。现在，以自动化功能齐全的立体仓库取代传统的普通房式仓库己成为世界仓储建设发展的潮流，其中，应用最多、发展速度最快的国家是日本。近年来每年约有上千个各种类型的自动化物流系统投入使用。据不完全统计【引，美国拥有各种类型的自动化立体仓库2 0 0 0 0 多座，日本拥有3 8 0 0 0 多座，德国拥有1 0 0 0 0 多座，英国有4 0 0 0 多座，俄罗斯有1 5 0 0 多座，高度达4 0 米以上的巨型立体仓库数量也越来越多。我国在2 0 世纪7 0 年代开始进行自动化立体仓库的开发研究工作，已有几十家企业、科研院校和高等学府从事自动化物流系统的开发研究和工程应用。北京起重运输机械研究所于1 9 6 3 年就研制了我国第一台桥式堆垛起重机，1 9 7 3 年开始研制由计算机控制的自动化立体仓库，并于1 9 8 0 年投入使用。同时，由北京机械工业自动化研究所等单位研制建成的我国第一座自动化立体仓库在北京汽车制造厂投产。我国的自动化仓库技术已实现了与其它信息决策系统的集成，正在做智能控制和模糊控制的研究工作。到目前北京机械工业自动化研究所已为国内企业建立和完善了3 0 多座自动化立体仓库，如济南第一机床厂、仪征化纤工自动化立体仓库堆垛机调度系统的建模及优化研究业公司、成都飞机制造公司、株洲南方摩托集团有限公司、重庆长安汽车有限公司等。据不完全统计，到2 0 0 5 年为止我国已建成的立体仓库已达5 0 0 余座，其中高度在1 5 米以上的大型立体仓库1 0 0 多座。2 0 0 5 年建成的有5 0 个左右【9 1 。现在我国更有多家单位研制和生产自动化立体仓库，如西安迪普物流机械有限公司生产的托盘式立体仓库、料箱式立体仓库、重力自动立体仓库，还有太原双塔刚玉股份有限公司、西安斯达机电有限责任公司等多家公司【l o 】。现在，自动化物流技术和成套设备的开发研制己经发展成为一个庞大的产业。目前，物料搬运产业年产值超过2 0 0 亿美元，其中立体仓库和自动导引车a g v 等直接组成自动化物流的产品，1 9 9 7 年达到了2 7 亿美元，其研究及应用也已经达到标准化、系列化、流水线生产的程度，并具有相当高的自动化水平。在德国，自1 9 9 2 年以来，自动化物流系统的产品己经发展成为机械制造业中最大的专业分支，1 9 9 6 年产值为1 7 5 亿马克。今天，现代物流的理论已进入世界各国经济生活的各个领域，自动化的物流系统己成为现代化工厂不可缺少的重要部分。可以说，物流是经济发展的命脉，像人体的血液一样，时刻支撑着人体的各种循环，维持着生命。在物流学众多的研究领域中，工业企业物流一直是被关注的焦点，这不仅由于物流组织的好坏直接决定着企业生产过程是否能够顺利进行，决定着企业产品的价值和使用价值是否能够顺利实现，而且企业的物流费用己成为生产成本和流通成本的重要组成部分。1 9 7 9 年英国的第一次调查表明，在从原材料获取到把产品送到用户的整个生产流通过程中，只有7 2 的费用是生产成本，其他( 剩余的2 8 ) 的6 3 都消耗在运输和仓储过程中。在第五次国际物流会议上，美国产业界人士明确指出，当前美国全部生产过程中只有5 的时间用于加工制造，9 5 的时间则用于搬运、储存等物流过程。在我国，1 9 9 9 年全社会物流费用支出约占g d p 的2 0 t 1 1 】。在这种情况下，企业将主要力量花在降低生产成本上是“不得要领 的，明智而有效的方法是改善物流。因此，以降低物流成本、减少资金占用、缩短生产周期为主要目标的物流合理化( r a t i o n a l i z a t i o n )被称为企业的“第三利润源泉 、“最重要的竞争领域 ，它被放到企业发展的战略高度来加以研究和实施。而自动化仓库作为物流系统的一个枢纽和核心，是物流系统实现物流合理化的关键所在，在国民经济中有着举足轻重的地位。因此，随着国民经济的发展，无论是在流通领域还是在生产制造领域，优化自动化立体2第一章绪论仓库的调度，提高系统的整体性能，已成为产学界研究的热点。1 1 2 课题的意义自动化立体仓库是物流系统的重要组成部分。自从自动化立体仓库应用到机械生产过程中的那一天起，大批科学家和工程师就致力于对提高其工作效率的研究，近3 0 年来，自动化立体仓库的硬件设备的技术和自动控制和通讯技术已经十分完善，自动化立体仓库的工作效率已经大大提高，但现代机械制造对自动化立体仓库的工作效率的要求也不断提高，要单纯在该领域基础上继续提高自动化立体仓库的工作效率已经很困难，或者是需要巨大的经济投入。于是，很多工程师和研究人员转而从自动化立体仓库的优化管理、调度方面入手，可以在不增加设备投资的情况下，减少作业时间，提高自动化立体仓库的工作效率。对自动化立体仓库的堆垛机调度优化问题的研究正是以此作为出发点的。随着自动化立体仓库的广泛应用，人们对自动化立体仓库的系统模型和调度策略的合理性、实时性以及自动化立体仓库的效率要求也越来越高。现有的研究方法已经不能满足求解大规模问题的需求，需要发展高效的启发式方法来设计优化调度方案。因此，开展自动化立体仓库优化调度的研究，具有重要意义和实用价值。本课题的研究目的在于结合现实经济和相关技术背景，构建成品高架库系统中堆垛机运行系统的模型，深入研究出入库调度合理化的目标；发展简便实用的调度优化算法和个案问题的一般性方法等。通过该课题的研究，可以为自动化立体仓库的管理者和建设者提供良好的决策依据。1 2 自动化立体仓库优化调度的研究现状1 2 1 自动化立体仓库优化调度方法自动化仓库的优化调度问题主要是在满足各种约束条件的情况下，对目前要求的作业任务进行排序，使得整个自动化仓库的性能达到最优。目前研究自动化仓库的方法主要有以下几种：( 1 ) 部分枚举法即用部分枚举法对堆垛机的运输线路进行调度的方法，这3自动化立体仓库堆垛机调度系统的建模及优化研究种方法采用部分启发式方法和图形搜索方法，确保能够很快的得到多项完全解，可通过一个特别决策对此法进行评价。( 2 ) 启发式规则法基于约束的调度方法，利用现有研究领域的知识，将搜索空间缩小的一种方法。启发式规则是在分析影响全局的各种因素的基础上做出的优化，因此效果通常要好于简单的优化的算法。( 3 ) 遗传算法遗传算法是一种基于进化论的优胜劣汰、自然选择、适者生存和物种遗传思想的随机优化搜索算法，通过群体的进化来进行全局性优化搜索。目前在工程中应用比较广泛，而且许多学者都在研究调度问题时采用了改进的遗传算法。( 4 ) 模拟仿真方法利用可对自动化仓库系统进行模拟的软件，并通过软件对几种调度算法进行测试，以得到比较理想的结果。1 2 2 国内外研究现状自动化立体仓库系统作为现代物流的关键技术，很大程度上反映企业的发展状况，国内外研究机构在自动化立体仓库系统的理论和技术研究方面投入了大量的人力物力，使得自动化立体仓库无论是软件还是硬件均有突飞猛进的发展。在自动化立体仓库调度问题方面，国内外学者也进行了广泛的研究并取得了一定的进展。在国内，剡昌锋等运用遗传的算法对自动化立体仓库的调度问题进行了研究，研究结果表明该方法能够得到可行的调度策略并能够使系统达到较好的性能指标【1 2 1 。山东工业大学的田国会、刘常有等针对自动化仓库的实际运行过程，提出了影响仓库运行效益的若干优化调度问题，并分别采用p e t r i 网、时态逻辑、模拟退火、遗传算法、神经网络等方法进行仿真研究”】。西安理工大学的徐香玲等人通过对自动化立体仓库作业调度和货位分配原则的归纳总结，建立了专家系统的知识库；并通过计算机算例仿真，探讨了专家系统在立体仓库调度中应用的可行性【1 4 1 。天津大学的杨华等人将堆垛机拣选作业调度归纳为旅行商问题，并从遗传算法角度，研究了求解堆垛机拣选作业调度最优路径的具体方法。经过仿真实验验证，这一方法完全可行【l5 1 。在国外，d o n a l dt e p a s 引入了一种知识信息系统来对辅助决策立体仓库中的调度问题并得到了应用【1 6 1 。k i mb y u n g 等提出了一种基于调度和控制系统的混合4第一章绪论智能a g e n t 结构并将其应用于a s r s 的货位拣选问题，仿真也证明这种方法可以优化立体仓库的货物库存【1 7 1 。1 3 本文的研究内容及创新点1 3 1 研究内容解决自动化立体仓库优化调度问题的目标在于：在兼顾仓库一般经济技术原则的前提下，使作业效率最高。因此，本课题的研究不但要对先前研究理论进行必要的完善，更要考虑实践操作方面的可行性，并使其简便易捷、可靠性高。由于现在已经投入使用的自动化立体仓库都是以固定货架为主体，而自动化立体仓库的工作效率也主要决定于堆垛机的作业效率，所以本文主要讨论自动化立体仓库固定货架下堆垛机作业调度的优化问题。本文的主要研究内容如下：( 1 ) 本文主要研究堆垛机调度系统的优化问题，为了研究堆垛机调度的优化，本文第三章对堆垛机系统进行了建模，采用p e t r i 网建立了堆垛机运行系统的出入库模型。( 2 ) 堆垛机系统的调度优化主要包括堆垛机的停留策略和作业优化两个方面，本文第四章主要分析了堆垛机系统优化调度的原则和目标，并对堆垛机常见的五种停留策略进行了分析。( 3 ) 针对拣选作业的特点，本文第五章先对拣选作业方式进行了详细的分析，提出了含装箱约束的拣选作业的数学模型，根据问题是一个n p 完全问题，提出了采用遗传算法求解该类问题的方法，并通过具体实例使用m a t l a b 编程验证了算法了的合理性。( 4 ) 针对复合作业的特点，本文第六章先对复合作业方式进行了详细的分析，针对问题的特点，提出了相应的转化规则，将堆垛机的复合作业转化为以时间为代价的t s p 问题，同样采用遗传算法进行求解，并通过具体的实例进行了验证。1 3 2 主要创新点主要创新点包括：( 1 ) 针对自动化立体仓库系统中堆垛机的实际运行过程，运用着色赋时p e t r i5自动化立体仓库堆垛机调度系统的建模及优化研究网的建模方法，构建了堆垛机调度系统的动态模型。( 2 ) 针对堆垛机常见的五种停留策略，采用概率模型的方法分析了五种停留策略的性能。( 3 ) 对于堆垛机的拣选作业问题，大多数文章将其归类为t s p 问题，本文通过对拣选作业的分析，提出了含装箱约束的拣选作业的数学模型，并采用遗传算法进行实现。( 4 ) 对于堆垛机的复合作业问题，大多数文章采用贪心算法的思想近似优化，本文通过对堆垛机的复合作业的分析，提出了一定的转化规则，将其转化为以时间为代价的t s p 问题，并采用遗传算法实现。6第二章自动化立体仓库第二章自动化立体仓库2 1 自动化立体仓库简介自动化立体仓库【1 8 】，也称高层货架仓库、自动存取系统，是指在不直接进行人工处理的情况下，运输设备能自动地存储和取出货物的多层仓库存储系统。它一般采用几层、十几层甚至几十层高的货架，并用自动化物料搬运设备进行货物出、入库作业。自动化立体仓库是集物料搬运和仓储科学为一体的一门综合科学技术工程，它的规划和设计是涉及到物流监控技术、计算机应用技术、通信技术、设备控制及货位优化管理等技术领域的综合工程项目。自动化立体仓库具有传统仓库的基本功能外，还具有分拣、理货的功能，以及在不直接进行人工处理的情况下，自动存储和取出物料的功能。现代自动化立体仓库，是在生产力和科学技术不断发展的情况下出现的一种崭新的物流技术，也是一种处于不断发展中的技术【1 9 1 。美国学者j a w h i t e 将自动化技术在仓储领域的发展分为以下五个阶段2 0 】：第一阶段是人工仓储技术阶段。在这一阶段当中，物资的输送、存储、管理和控制主要靠人工实现，其实时性和直观性有较明显的优点。人工仓储技术在初期设备投资的经济指标也具有优越性。第二阶段是机械化仓储技术阶段。物料可以通过各种各样的传送带，工业输送车、机械手、吊车、堆垛机和升降机来移动和搬运，用货架、托盘和可移动式货架存储物料，通过人工操作机械存取设备，用限位开关，螺旋机械制动和机械监视器等控制设备的运行。机械化满足了人们对速度、精度、高度、重量、重复存取和搬运等方面的要求。第三阶段是自动化仓储技术阶段。自动化技术对仓储技术的发展起了重要的促进作用。2 0 世纪5 0 年代末和6 0 年代初，相继研制和采用了自动导引小车( a g v ) 、自动货架、自动存取机器人、自动识别和自动分拣等系统。2 0 世纪7 0 年代和8 0 年代，旋转式立体货架、移动式货架、巷道式堆垛机和其他搬运设备都加入了自动控制的行列，但这时只是各个设备的局部自动化各自独立应用，7自动化立体仓库堆垛机调度系统的建模及优化研究被称为“自动化孤岛 。随着计算机技术的发展，自动化仓库研究的工作重点逐渐转向物资的控制和管理的实时、协调和一体化，信息自动化技术逐渐成为仓储自动化技术的核心。计算机之间、数据采集点之间、机械设备的控制器之间以及它们与主计算机之间的通信可以及时高效地汇总信息，仓库计算机及时地记录订货和到货时间，显示库存量，计划人员可以方便地做出供货决策，他们知道目前工厂正在生产什么、需要订什么货物、什么时间发什么品种、规格的货物，管理人员随时掌握货源及客户的需求。在这一阶段信息技术的应用己成为仓储技术的重要支柱。第四阶段是集成自动化仓储技术阶段。在2 0 世纪7 0 年代末和8 0 年代，自动化技术被越来越多地用到生产和分配领域，显然，“自动化孤岛”需要集成化，于是便形成了“集成系统”的概念。在集成化系统中，整个系统的有机协作，使总体效益和生产的应变能力大大超过各部分独立效益的总和。集成化仓库技术作为计算机集成制造系统中物资存储的中心受到人们的重视。在集成化系统里包括了人、设备和控制系统，而前面所叙述的三个阶段是它的基础。第五阶段是智能自动化仓储技术阶段。人工智能技术的发展使自动化技术向更高级的阶段智能自动化方向发展。现在，智能自动化仓储技术还处于发展阶段，但已引起国际上有关设计研究人员的极大关注，它将是仓库自动化技术的主要发展方向。2 2 自动化立体仓库优点由于自动化立体仓库具有节约劳动力，作业迅速准确，提高保管效率，减低物流费用等优越性，因此受到了广泛的重视。它是工厂物流、柔性制造系统和计算机集成制造系统中不可或缺的重要组成部分，它在提高生产效率、实现仓储自动化方面起到了越来越大的作用，其智能化管理在提高企业竞争力和满足客户服务等方面已经越来越成为一个重要的因素。其优点主要体现在以下几个方面【2 1 1 ：1 、提高空间利用率及货物管理质量。由于使用高层货架存储货物，存储区可以大幅度地向高空发展，充分利用仓库地面和空间，因此，节省了库存占地面积，提高了空间利用率。采用高层立体货架储存，不同的货物在不同的货架空间8第二章自动化立体仓库内，彼此之间不互相挤压，存取时互不干扰。而且由于采用机械化作业，所以货物在运输过程中的完好性比较好，不容易发生破坏。另外，结合了计算机管理，可以容易地实现先入先出，防止货物的自然老化、变质、生锈或发霉等。2 、提高劳动生产率，降低劳动强度。自动化立体仓库使用机械和自动化设备，运行和处理速度快，大大提高了劳动生产率，减轻了仓库管理人员的工作强度和工作环境，确保安全、文明生产。同时，机械化使立体仓库的存取过程完全融入到企业的物流系统当中，使物流系统的运行更加流畅和有效。采用自动化技术后，还能较好地适应黑暗、低温、污染、有毒和易爆等特殊场合的物品存储需要。3 、科学储备，提高物料调节水平，加快储备资金周转。由于自动化仓库采用计算机控制，计算机能准确的对仓库中的各种信息进行存储和管理，调控仓库中的堆垛机和智能运货车合理、高效率的运行，使仓库的运行更加流畅，能减少货物处理过程中的差错，而利用人工管理不能做到这一点。同时借助于计算机管理还能有效地利用仓库储存能力和库存信息进行有效的评估，便于清点和盘库，合理减少库存，加快储备资金周转，节约流动资金，从而提高仓库的管理水平。另外，在自动化系统的管理和控制下，能对物料进行科学的管理，使物料在存储过程中合理利用各种资源，提高处理效率，适应多种存储要求。4 、有效衔接生产与库存，加快物资周转，降低成本。作为生产过程的中间环节，具有原材料、在制品和成品的缓冲存储功能，在自动化和机械化设备处理下，自动化程度提高，各种物料库存周期缩短，从而降低了总成本。对不同运输方式、不同装运方式、不同状态的物料衔接，改变运输方式，改变装运方式和采用有效的技术，都会带来费用的降低。5 、为企业的生产指挥和决策提供有效的依据。自动化立体仓库的信息系统可以与企业的生产信息系统集成，实现企业信息管理的自动化。由于仓储信息及时准确，便于企业决策人员及时掌握库存情况，根据生产以及市场情况及时对企业规划做出调整，提高了生产的应变能力和决策能力。因此，使用自动化仓库，促进企业的科学管理，减少了浪费，保证均衡生产。国内外的实践经验表明，以自动化仓库为中心的物流管理自动化，在实现物料的自动化管理，加速资金周转，提高劳动生产率，降低劳动强度，节约库存的9自动化立体仓库堆垛机调度系统的建模及优化研究占地面积，提高厂房空间的利用率，保证生产均衡等诸方面能带来巨大的效益。2 3 自动化立体仓库的组成自动化立体仓库是机械和电气、强电控制和弱电控制相结合的产物。巷道堆垛机式自动化立体仓库如图2 - 1 所示。图2 1 巷道堆垛机式立体仓库自动化立体仓库主要由货物存储系统、货物存取和传送系统、控制和管理三大系统组成，还有与之配套的供电系统、空调系统、消防报警系统、称重计量系统、信息流通系统等【2 2 ，2 3 ，2 4 】。一、货物存储系统：由立体货架的货格( 托盘或货箱) 组成，用于存放货物，货物放在托盘上，出入库时连同托盘一起出入库。其高度分为高层货架( 1 2 米以上) 、中层货架( 5 米至1 2 米) 、底层货架( 5 米以下) ，按货架形式分为单元货架、重力货架、活动货架和拣选货架等。二、货物存取和传送系统：该系统承担货物存取、出入仓库的功能，通常由巷道堆垛机、出入库输送机、装卸机械等组成。巷道堆垛机是在高层货架的窄巷道内作业的起重机，可实现沿轨道行进、垂直起降和货叉伸缩三种功能，用于从两侧货架的任何货位上自动存入或取出货物。每两个高层货架之间有一台巷道堆垛机。出入库输送机可根据货物的特点采用传送带输送机、机动辊道、链传动输1 0第二章自动化立体仓库送机等，主要将货物送到堆垛机上下料位置和货物出入库位置。装卸机械承担货物出入库装车或卸车的工作，一般由行车、吊车、叉车等机械组成。三、控制和管理系统：由管理计算机、中央控制计算机和堆垛机、出入库输送等直接控制的可编程控制机械组成控制系统，控制调度整个立体仓库的出入库作业的正常运行。计算机管理系统主要完成对整个仓库系统信息管理和作业管理，并负责与上级系统的通讯以及企业信息管理系统的部分任务。自动化立体仓库堆垛机调度系统的建模及优化研究第三章堆垛机调度系统的p e t ri 网模型3 1 前言研究自动化立体仓库堆垛机的调度问题首先必须先建立自动化立体仓库堆垛机输送系统的调度模型。自动化立体仓库堆垛机输送系统属离散事件动态模型( d e d s ) ，涉及的因素很多，难以建立数学解析模型。近些年，研究人员对离散动态系统的建模、分析、优化等方面的研究取得了很大进展，开发了很多新的建模技术。概括的讲，这些建模方法可以分为两类：形式化建模技术和非形式化建模技术。所谓形式化建模技术是指采用大量的数学工具通过状态方程对系统进行描述和分析，像排队网络法，扰动分析法，p e t r i 网方法等等。非形式化建模技术是指采用图形符号或语言描述等较为贴近人们思维习惯的方式对系统进行描述和分析，这种分析主要借助计算机程序实现，比如活动循环图、流程图法，面向对象的建模技术等等。在d e d s 系统的优化中，p e t r i 网是一个较为理想的模型，它具有较强的关系和条件表达能力，是d e d s 系统计算机仿真的有力模型工具【2 5 1 。目前国内外对于自动化立体仓库调度的研究主要集中在对p e t r i 网进行改进的基础上构建模型。山东工业大学常发亮、刘长有直接使用p c t r i 网建立了输送系统的调度仿真模型2 6 】；山东工业大学田国会等采用面向对象着色p c t r i 网( o o c p n ) 对其进行了过程建模、分析和控制【2 7 1 ；i t a l y 的f b a s i l e 等应用有色p e t r i网( c p n ) 构建了a s r s 的模块化模型，各子模型间通过接口( f u s i o np l a c e s ) 通讯脚1 ；这些模型都获得了一定的效果，然而自动化立体仓库堆垛机输送系统是基于时间的离散事件动态系统( d e d s ) ，执行过程中的任务在各站台或巷道上需要一定完成时间，上述研究均忽略这一点；意大利的m d o t o l i l 2 9 】等应用着色赋时p e t d网研究了高架库a s r s 模型构建问题，不过与国内的实际问题有出入。本章将通过对一个巷道式堆垛机系统的出入库调度模型的建立，描述出该系统的行为和特性，为下一步堆垛机调度优化打下基础。3 2p e t r i 网理论自动化立体仓库属于典型的离散事件动态系统( d e d s ) ，对于离散事件动态1 2第三章堆垛机调度系统的p e t r i 网模型系统的建模，p e t r i 网已经证明是一个较为理想的工具，它具有较强的关系和条件表达能力，是离散事件动态系统计算机仿真的有力模型工具2 5 ，2 8 2 9 , 3 0 , 3 1 1 。3 2 1p e t r i 网的发展p e t r i 网简称p n ，由德国的c a r la d a mp e t r i 在1 9 6 2 年所写的博士论文3 2 】c o m m u n i c a t i o nw i ma u t o m a t a ( 用自动机通信) 中提出的，p e t r i 先生在论文中使用网状结构模拟通信系统，研究信息系统及其相互关系的数学模型【3 3 】。p e t r i 的工作引起了欧美学术界与工业界的注意。从1 9 8 0 年召开第一次p e t r i 网理论和应用的国际研讨会以来，每年一次的国际研讨会连续不断，p e t r i 网理论和应用的研究成果大部分集中在会议论文集中。四十多年来，p e t r i 网的理论日臻完善，己发展成为具有严密的数学基础，多种抽象层次的通用网论。其模拟能力已证明与图灵机等价。近些年，p e t r i 网技术已获得极大发展。各种各样的网系统已经被开发出来。像条件事件网，库所变迁网，有色网，赋时网系统等等。这些网系统的开发极大地扩展了对复杂系统的建模能力【1 7 ，2 1 , 3 4 , 3 5 】。本文将综合有色网和赋时网的特性，提出着色赋时p e t r i 网构建a v s r s 的动态模型。有色p e t r i 网( c o l o r e dp e t r in e t s ) 是通过赋予每个托肯( t o k e n ) 不同的颜色来区分具有不同个体特征的托肯( t o k e n ) ，通过有效变迁的输入库所资源中的不同t o k e n 颜色的组合构成变迁的不同颜色，用以区分由不同实体所参与的统一类型的活动。赋时网( t i m e dp e t r in e t s ) 系统能表达时间概念，在这种模型中，变迁需要一定的时间才能完成。有一个最短时间和最长时间，变迁将在此时间段内被激发，随机地完成。时序的引入有效的描述和解决了变迁事件之间的并发、冲突等现象。随着p e t r i 网研究的不断深入和发展。它的抽象、描述能力也不断地向纵向和横向发展。它的纵向扩展表现为：从基本的条件事件( c e ) 网，发展到高级网。它的横向扩展表现为：从没有参数的网，发展到时间p e t r i 网和随机p e t r i 网【3 q ；从一般有向弧发展到禁止弧和可变弧等等。p e t r i 网描述能力的增强就会在某种程度上增加p e t r i 网分析的难度，增加对系统模型性质的判断和计算的困难。1 3自动化立体仓库堆垛机调度系统的建模及优化研究3 2 2p e t r i 网的特点与应用随着理论上的不断完善和应用上的不断扩大，p e t r i 网己经成为在逻辑层次上对离散事件动态系统( d e d s ) 进行建模和分析的主要方法之一。本质上，p e t d网方法是一种以图形形式研究系统组织和动态特性的理论，具有直观、易懂和易用的优点，对于描述和分析现象有着独到的优越之处，极其适合于描述异步并发现象，同时又是严格定义的数学对象，可方便地借助数学中的方法和技术对模型进行分析和求解【3 2 捌。由于p e t r i 网能够表达并发的事件，被认为是自动化理论的一种。研究领域趋向认为p e t d 网是所有流程定义语言之母。作为图形工具，其具有类似流程框图和网图的可视描述功能，还可以通过托肯( t o k e n ) 的流动模拟系统的动态和活动行为，是一种高效的图形化的研究离散事件动态系统的建模工具。p e t r i 网的特点主要表现在事件驱动、图形表示和数学分析等方面，它是一种适用于多种系统的图形化、数学化建模工具，为描述和研究具有并发、异步、冲突、死锁、分布式和随机性等特征的系统提供了强有力的手段，与传统的系统建模、分析和控制方法相比，p e t r i 网有独特的优越性，它作为一种图形化和数学化的建模工具，能够提供一个集成的建模、分析、和控制环境，为系统的设计提供便利。因此被广泛应用于离散事件系统、工作流、并发和并行计算、分布式数据库系统、神经元网络和决策模型等领域【3 8 】。目前，p c r t i 网的发展己涉及计算机科学的各个领域，特别适用于模拟这样的一类系统：系统中含有相互作用的并行分支。由于p e t r i 网对带有并发性、异步性、分布式、非确定性、并行性系统的有力描述，已成为目前广泛使用的建模工具。p e t r i 网用于设计和分析系统时，它着眼于系统发生的变化、变化发生的条件、发生后的影响以及变化间的关系等。p e t r i 网的建模及分析过程可表示为【2 l 】：系统一苎堡，p e t r i 网模型分析结果图3 1p e t r i 网建模及分析过程1 4第三章堆垛机调度系统的p e t d 网模型近年来，p e t r i 网在各个领域中得到了广泛的应用，特别是其直观、易懂和易用的优点，对描述和分析离散事件动态系统( d e d s ) 有它独到的优越性。而物流系统中立体高架库的运行行为属于典型的离散事件动态系统，用p e t r i 网方法来描述自动化立体仓库系统是一个较为理想的模型工具。利用p e t f i 网对其进行建模与分析，能极大的保障所设计系统的合理性。3 2 3p e t r i 网的基本概念p e t r i 网是由节点和有向弧组成的一种有向图，基本p e t r i 网由四个元素组成【3 9 】，即：p n = ( p ，t ，i ，o ) 。其中：p = ( a ，p 2 ，见) 称为库所( p l a c e ) ，n 0 ，为一有限集合，一般表示系统中的资源和状态。t = 辑，乞，乙) 称为变迁( t r a n s i t i o n ) ，m 0 ，为一有限集合，一般表示系统中可能发生的事件。p 和t 是相互分离的，p u r 彩，p n r = a ，a 表示空集合。i ：p x t 专 o ，1 ) 表示从某库所到某变迁是否存在有向弧相连。0 ：t x p - - 9 , o ，1 ) 表示从某变迁到某库所是否存在有向弧相连。p tt t mp m图3 2 一个简单p e t r i 网示例如图3 2 所示为一个简单p e t r i 网示例，其中包含四种结构如下：1 、库所( 或称为位置、位子) 、也称为p 元素，用圆圈“o 表示。库所不仅表示一个场所，而且还表示在该场所存放了一定的资源。库所总是与状态概念相关，为信息的载体。在a s r s 系统中，信息主要包括货物托盘，堆垛机以及系统施加的控制原则等。2 、变迁( 或称为转移) ，也称为t 元素，用矩形框“_ ”表示。资源的消耗、1 5自动化立体仓库堆垛机调度系统的建模及优化研究使用及产生对应于状态的变化，因而变迁可以用来描述事件( 涉及条件的变迁称为事件) ，即由已有的信息产生新的信息。在a s r s 系统中，所谓事件主要是指堆垛机装载、卸载货物托盘以及堆垛机在巷道内的移动等。3 、箭头“一 ，它表示有向线段，用来连接库所和变迁。p e t d 网的形式化定义是，库所和库所、变迁和变迁之间不可直接联系。箭头即表明这种非直接作用的关系，它表达了库所和库所、变迁和变迁之间的因果关系。一个变迁可以有多个输入和多个输出库所。4 、令牌“”，它是一种标记符号，用点表示，令牌位于库所内，它们沿有向线段流动，表示了信息的流动。在网p n = ( p , t , i ，o ) 中，t 仨t ，记t = p p i i ( p ，f ) = 1 ) 为变迁t 的所有输入库所的集合，称为t 的前集，t = p p l o ( p ，f ) = 1 ) 为变迁t 的所有输出库所的集合，称为t 的后集。另外，记m 为网p n = ( p , t , i ，o ) 的初始标识，用库所( 位置) 圆圈中的小黑点( t o k e n ) 表示。通过变迁( 转移) 的发射，导致托肯在各位置间动态流动，由此来模拟系统的动态过程，从而反映系统的动态特性。记w 为p n 上的权函数，它是有向弧到正整数集的映射：形：jh l 2 ，l d 专 1 ，2 ，)、，其中，上式表示变迁发生所需前集中各库所的标识下限，下式表示变迁发生后后集中各库所表示增加的上限。3 2 4p e t r i 网的运行规则上一小节描述的是p e t r i 网的静态结构描述，为描述网系统的动态行为，还需给出变迁发生的条件和规律，把这种规律称为p e t r i 网的运行规则。平凡p c t r i 网p n = t i ，o ，m ) 中，设m 为网上的一标识，则网系统的运行规则如下：一个变迁f ，t 发生的条件是：v p , t jj m ( 只) 形( 易，0 )1 6第三章堆垛机调度系统的p e t r i 网模型这时称m 授权0 发生，记干t gm t o 。若0 在m 有发生权，那么，就可以发生，其结果从，的各输入库所移去一个托肯，并像0 的各个输出库所加入移入托肯，m 亦变成如下定义的新标识m ：川驴鼢_ 翟少职盯p 吩t j 的发生把标识m 变成m 的事实记作m 【0 m 。3 3 着色赋时p e t r i 网3 3 1 着色赋时p e t n 网方法的提出着色赋时p e t r i 网是一个9 元组c t p n = ( p r ，c o ，i n h ，c + ，c 一，q ，z ，m o ) 。其中：( 1 ) - p 为有限库所集，p = 只u p ；其中为逻辑位置集，用于存放系统调度层下达的控制指令，这些指令包括下达给堆垛机的路径指令，以及防止死锁产生的逻辑控制指令，比如输入变迁使能标志指令；只为堆垛机运行中经过的物理位置集和所有货位，p ，p p t 。( 2 ) ：t 为变迁集，用于描述堆垛机的行为事件，如接受调度层下达的指令、装载卸载货物、传送货物等，t t ；托肯代表自动化立体仓库堆垛机输送系统中的堆垛机以及控制指令，托肯颜色代表堆垛机运行的路径。( 3 ) ：c d 为颜色集，c o = c o ( p ) u c o