智能化仓储中箱式缓存区调度算法的设计与应用

段旭磊　张仰森　张涛

摘 要： 在传统的智能化立体仓库中，成品将被直接存储，这种模式对于多品种、多批次的产品生产方式而言，极大地浪费了设备资源，增加了整个调度系统的成本和难度。提出箱式缓存道的概念，将不同成品在缓存区进行积存，当达到一定数量时，将成品统一存储处理。以国药集团致君（深圳）坪山药业智能化立体仓库系统为研究对象，其中的箱式缓存区调度算法将主要研究智能调度系统中成品合理的分道缓存积放和释放码垛，及在节省缓存道占用的前提下合理分配缓存道的问题。箱式缓存道的应用，解决了产品分品种、分批次统一存放的问题，能够对不同品种、不同规格、不同批次的成品进行准确地分道缓存，提高了生产和存储效率。

关键词： 智能化立体仓库； 智能调度； 箱式缓存道； 生产方式

中图分类号： TN915.5?34 文献标识码： A 文章编号： 1004?373X（2017）16?0086?04

Abstract： The final products are stored directly in the traditional intelligent stereoscopic warehouse system （ISWS）. This mode， for multispecies and multi?batch production pattern， is a waste of equipment resources， and increases operating cost and difficulty of the entire dispatching system. The concept of box?type cache is proposed in this paper. According to this concept， the different final products are stored in the cache area firstly， and then the products are released when the number of the products is accumulated to a certain quantity. Taking the intelligent stereoscopic warehouse system （ISWS） of Shenzhen Pinshan Pharmacy as the research object， its final products are distributed into cache and release stacking temporarily in the pipeline in this system. The algorithm that how to split different batches， different specifications and different finished kits into some rails called the multi?objective optimization is proposed. This algorithm improved the utilization of emergency stopping lane， and speed and efficiency of storage.

Keywords： ISWS； intelligent scheduling； box?type cache； production pattern

随着物流技术和工业生产的快速发展，现代企业对物料搬运和贮存提出了更高的要求，仓储方式也逐渐发生改变，从最初人力手工作业的简单堆积，到通过叉车等简单设备的仓库式存儲，发展到如今的采用高位叉车、堆垛机、无人导引小车、箱式输送线、拆/码垛机器人等自动化设备的立体仓库存储。智能化立体仓库系统（Intelligent Stereoscopic Warehouse System，ISWS），是一种新型的仓储技术，是物料搬运和仓储科学中的一门综合科学技术工程。它是以先进的计算机控制技术为主要技术支持，以高层立体货架和托盘系统为主要手段对货物进行存储，以自动化搬运设备为基础，能够适应现代化大批量生产、存储和物资流通的需要，并且在沟通物流信息、衔接产需、进行科学储备和企业经营决策等方面也起到了特殊的作用。

智能化立体仓库软件系统，主要包括管理及调度系统，而调度系统关乎整个系统的自动化程度和成本支出。在现代企业的生产?存储?销售链条中，产品品种众多，批次严格，传统的边生产边存储的方式已经不能满足实际需求。本文以国药集团致君（深圳）坪山药业智能化立体仓库为基础，探讨调度系统开发与实现中采用箱式缓存道的方法解决产品分品种分批次存储问题。

1 相关工作

美国学者J.A.White将仓储中自动化技术的发展分为5个阶段[1]：人工仓储→机械化仓储→自动化仓储→集成化仓储→智能自动化仓储。随着计算机智能化技术的快速发展，智能自动化仓储成为自动化技术的主要发展方向和研究重点。

国内外许多研究学者针对智能化立体仓库的调度问题进行了大量的研究，并取得了不少的研究成果。在国内，田国会等利用计算机仿真技术分别使用Petri网、时态逻辑、模拟退火、遗传算法、神经网络等方法对调度优化问题进行了研究[2?5]；常发亮等通过对物资配送中心的库存管理与布局优化的研究提出了货位的布局策略以及优化算法[6]；周奇才提出立体仓库运行控制的优化准则[7]，分析确定仓库系统控制的优化控制数学模型，并运用有关原理，提出仓库巷道堆垛机及出入库系统货箱运行的优化控制程序。徐香玲等通过归纳ISWS作业调度的相关原则，建立了专家系统知识库，并对专家系统在ISWS调度中的应用可行性进行了分析研究[8]。李诗珍，李振等也分别通过不同的研究方法对调度优化问题进行了深入的分析与研究[9?19]。endprint

在国外，美国学者Linn.R.将专家系统的思想应用到立体仓库的控制中[20]；Kim.Byung等提出了一种基于调度和控制系统的混合智能Agent结构，并将其应用于ISWS的货位拣选问题[21]；Donald.Tepas提出了用一种知识信息系统来辅助决策立体仓库中的调度问题并得到了应用[22]；N.Mishra等对批量订单调度问题进行了研究[23]。P.H.Koo等对不同的调度规则对堆垛机的运行时间的影响进行了分析研究[24]。S.R.Nenad通过提出了一种基于时间窗的调度方法对仓库的调度问题进行了分析研究[25]。J.M.belenguer采用分支定界的方法对有一定约束条件的路径规划问题进行求解[26]。

尽管国内外的研究学者对智能化立体仓库的研究的侧重点不同，但是其主要的研究内容主要还是集中在对堆垛机的拣选作业的优化和入库货位选择优化方面，对除堆垛机外的设备进行研究的较少。其实，在整个调度系统中针对物料如何合理入出库的前期设计对效率的提高至关重要，箱式缓存道就是为了解决如何合理集中分配设备资源的问题而被提出。如何根据实际的情况设计出一个尽量减少优化复杂性的调度方式仍是一个重要的课题。因本实例是深圳国药一致药业立体仓库，该公司集药品的生产、存储及销售于一体，生产车间在打包完药品成品后会直接将药品放在箱式输送线，药品经过输送线运送到仓库进行存储。由于车间会同时生产不同品种不同批次的药品，而为了提高仓库货架的利用率，将在一个托盘上码垛一定多的药品进行存放，所以不同批次不同产品的药品在进入仓库时不能立即进行码垛入库，需要先进行分别积放，等积放一定的数量后才可进行机器人码垛入库。箱式缓存道就是为了能够使药品进行分品种分批次积放而设计。

2 箱式缓存区系统描述

深圳国药一致药业的生产车间共有三层，其中二层和三层分别有一道输送线与仓库部分相连接，所以本系统的箱式缓存区分为上、下两层，分别有三层车间和二层车间相连接，并且上、下两层通过再检区相连接。上层和下层缓存区各有9条缓存道。

上层和下层缓存区俯视图如图1所示，再检区俯视图如图2所示。

从生产车间输送过来的成品外箱上都贴有惟一标识该成品各种信息的药品电子监管码，该电子监管码为一维Code128条码。

如图2 所示，箱式缓存区共设有5个条码扫描器，其中上层和下层分别设有2个，再检区设有1个。为了加快箱子进入缓存区的节奏，默认三楼车间输送过来的箱子优先进入上层缓存道，二楼车间运输过来的箱子优先进入下层缓存道，只有上层或下层的缓存道已经积放满后才考虑进行换层存放。现以下层缓存道为例描述箱子入缓存道流程，如图3所示。

3 系统原则及算法

本系统中箱式缓存区的作用主要就是对药品成品进行分品种分批次缓存积放，由于缓存道的数量已经确定而生产车间的生产产品的品种数量并不能确定，所以为了尽可能地合理利用缓存道，对箱式缓存区的调度要求应具备以下几点：

（1） 按照成品批次分配缓存道，即不同产品不同批次的成品分配不同的缓存道。

（2） 按照生产车间与上下层缓存道对应原则优先分道，即二层车间的成品优先分配下层缓存道，三层车间的成品优先分配上层缓存道，以此减少成品的换层时间，加快成品缓存的节奏。

（3） 如果同品种同批次的产品占用两条以上的缓存道，那么优先分配给数量多的缓存道使其优先达到满托盘数缓存道。

（4） 对于同品种同批次的缓存道可以实现缓存道的同时释放及同时进入，尽量减少缓存道的占用，提高缓存道的利用率。

（5） 为了减少异常产品占用缓存道，只对异常产品开放第九道缓存道。

（6） 如果缓存道全满，提示释放，暂停输送机上产品调度。

（7） 如果当前产品可用缓存道满，并且后续产品有可用缓存道，对当前产品进行循环换层处理（大批量产品的效率要求）。

根据系统提出的调度原则以及在实际应用中成品入缓存道的情况，提出以下算法：

Step1：设[ai]表示缓存道号，[a=1]表示下层缓存道，[a=2]表示上層缓存道，并且令[xaia=1，2 ， i=1，2，…，9]表示[ai]缓存道的状态，[xai∈0，1]，0表示[ai]缓存道未绑定产品批号信息，1表示[ai]缓存道已绑定产品批号信息。[Nai]表示缓存道[ai]内箱子的数量，[Oai]表示缓存道[ai]剩余需要释放的数量，[Fai]表示缓存道[ai]满托盘的数量，[Fai]的取值根据缓存道内产品的不同取值不同，不同产品的满道数量在入缓存道前应该维护进数据库，转到Step2。

Step2：箱子通过箱线进入缓存道之前有一个换层区域，这里通过条码扫描器验证条码，如果条码扫描器扫到条码，将条码上传给调度系统，系统根据条码提供的产品批号信息查询该条码扫描器所在层的缓存道的产品批号绑定信息，若存在[ai]缓存道绑定了此产品批号信息且未满（[Nai+Oai

Step3：若[i=19x1i

Step4：换线再检区，条码扫描器扫描条码，若扫描成功，将条码上传调度系统，系统获得条码提供的产品批号信息，依次遍历上层和下层缓存道绑定信息，尝试获取绑定该批号信息且未满的缓存道号[ai]，若获得且缓存道号为下层，则下发换层下层命令，转至Step2；若为上层，则下发换层上层命令。如果没有获取符合条件的，则遍历依次遍历下层和上层缓存道，获得空缓存道号[ai]，若为下层，则下发换层下层命令，转到Step2；若为上层，则下发换层上层命令。若没有找到符合上面两个条件的缓存道则下发换层下层指令，是箱子进入循环状态直到找到符合条件的缓存道。如果扫描条码失败，下发剔除指令将此箱送至剔除位由人工进行后续处理，转至Step7。

Step5：箱子进入缓存道前也需要进行扫码，调度系统获得条码信息后查询当前层的产品批号绑定信息进行分道，并将分道号迅速发送给箱线PLC控制器，PLC控制器根据分道号将箱子进行分道缓存，转至Step6。

Step6：调度系统实时监测缓存道与机器人状态，若存在机器人空闲且缓存区存在可释放缓存道，则下发释放指令，释放缓存道箱子进入码垛箱线，同时将产品批号信息以及释放数量和箱型信息与码垛机器人信息进行绑定，同时更新该释放缓存道的数量信息，如果释放条件为满足一托盘释放时，数量更新情况为[Nai=（Nai-Fai）]，[Oai=Fai]，若释放条件为产品结批释放，则数量更新情况为[Nai=0]，[Oai=Nai]，其中[Oai]的值是调度系统实时监控缓存道的释放情况逐一递减直到为0，当缓存道[Nai=Oai=0]，则表明该缓存道为空缓存道，应清空绑定情况，[Xai=0]，转至Step7。

Step7：结束。

4 系统实现

国药集团致君（深圳）坪山药业立体仓库智能调度系统采用Delphi语言开发，其开发平台为Borland Delphi 2010。在搭建本系统的开发环境与运行环境时，还涉及到一些其他的通信软件与技术，比如OPC技术、Delhpi多线程机制等。在整个系统设计的过程中，充分考虑了各种异常情况，并进行相应的处理。实践表明，智能化立体仓库箱式缓存道调度系统的研究与实现是成功的，如表1所示。

表1 管理及调度系统部分功能和性能与目前部分厂家对比

5 结 论

本文主要对箱式缓存区系统进行描述，并提出了一种对成品合理分配缓存道的算法，实现了对不同产品不同批次进行分配缓存存放，在分配緩存道方面实现同批次同缓存道的边进边出，大大减少了同批次产品进入不同缓存道情况，并大大提高了缓存道的利用率。在实际使用中效果良好。本智能化立体仓库较一般的智能化立体仓库增加了箱式缓存道。在对不同产品或同产品不同批号进行分道缓存时如何减少对缓存道的占用，在箱子的分配上如何保证缓存道分配的准确性都是系统研究的重点。在缓存道的调度分配算法中，采用持续换层的方法处理极端情况下缓存道不够用的异常，但是在箱子进行上下层换道过程中，由于不能保证硬件的绝对正确性，比如条码扫描器，可能出现抖动从而被多次触发，对同一个箱子多次扫码，现在只是在每个箱子扫码完毕后增加延时处理信号，在逻辑上还不能完全避免扫码异常这个问题。在实际的生产过程中，需充分考虑各种情况，才能避免不必要的错误。

注：本文通讯作者为张仰森。

参考文献

[1] 吕广明.物流设备与规划技术[M].北京：中国电力出版社，2009.

[2] 田国会，张攀，尹建芹，等.基于混合遗传算法的固定货架拣选优化问题研究[J].机械工程学报，2004（2）：141?144.

[3] 田国会，张攀，李晓磊，等.一类仓库作业优化问题的混合遗传算法研究[J].系统仿真学报，2004，16（6）：1198?1201.

[4] 田伟，田国会，张攀，等.考虑非对称情形的一类拣选问题的改进LK算法求解[J].中国工程科学，2004（11）：47?52.

[5] 宁春林，田国会，尹建芹，等.Max?Min蚁群算法在固定货架拣选路径优化中的应用[J].山东大学学报（工学版），2004，33（6）：676?680.

[6] 常发亮，刘长有.智能化立体仓库存储管理策略的优化[J].基础自动化，1996（5）：6?9.

[7] 刘道华，原思聪，兰洋，等.基于组态监控的设备运行管理系统设计[J].微电子学与计算机，2005（10）：116?119.

[8] 徐香玲，傅卫平，李德信，等.基于专家系统的智能化立体仓库出入库调度研究[J].物流技术，2005（2）：38?40.

[9] 常发亮，刘增晓，辛征，等.智能化立体仓库拣选作业路径优化问题研究[J].系统工程理论与实践，2007（2）：139?143.

[10] 李诗珍，王转.订单拣取路径优化研究：S形启发式方法在配送中心拣货中的应用[J].物流技术与应用，2005（5）：67?70.

[11] 李梅娟，陈雪波，刘臣奇.基于改进蚁群算法拣选作业优化问题的求解[J].计算机工程，2009，35（3）：219?221.

[12] 杨玲，关志伟.智能化立体仓库拣选路径优化问题研究[J].中国制造业信息化，2011，40（7）：47?50.

[13] 姜山，季业飞.GASA混合优化算法在智能化立体仓库堆垛机作业调度问题中的应用[J].制造业自动化，2010，32（10）：63?64.

[14] 刘志雄.物流自动化仓库拣选作业调度粒子群优化研究[J].机械制造，2010，48（1）：66?69.

[15] 杨华龙，陈志俊，计莹峰，等.基于时间驱动作业成本法的配送中心作业优化[J].大连海事大学学报（自然科学版），2012（4）：103?106.

[16] 刘万军，黄杨波，丁鹏.基于单亲遗传算法的拣选作业优化研究[J].计算机应用，2010（11）：2891?2893.

[17] 计三有，陈厚松.基于蚁群算法的立体仓库拣选作业优化[J].武汉理工大学学报，2010（23）：69?71.

[18] 李振，胡庆东，张国英，等.基于小生境遗传算法的人工拣货路径优化研究[J].物流科技，2011（6）：85?88.

[19] 杜亚江，王娴.物流中心高层货架拣选作业的路径优化[J].计算机系统应用，2013（9）：160?163.

[20] ZHAN Yuedong， LUO Ying. Guided and detecting technology of intelligent robot AGV and new?style AGV [C]// International Conference on Sensors and Control Techniques （ICSC 2000）. [S.l.： s.n.]， 2000： 461?464.endprint

[21] RATLIFF H D， ROSENTHAL A S. Order?picking in a rectangular warehouse： a solvable case of the traveling salesman problem [J]. Operations Research， 1983， 31（3）：507?521.

[22] TEPAS Donald. Workware decision support systems： a compare?hensive methodological approach to work?scheduling problems [J]. Theor issues in ergon， 2003， 4（7）： 1012?1018.

[23] KOO P H， JANG J. Vehicle travel time models for AGV systems under various dispatching rules [J]. International journal of flexible manufacturing systems， 2002， 14（3）： 249?261.

[24] MISHRA N， KUMAR V， KUMAR N， et al. Addressing lot sizing and warehousing scheduling problem in manufacturing environment [J]. Expert systems with applications， 2011， 38（9）： 11751?11762.

[25] SMOLIC?ROCAK N， BOGDAN S， KOVACIC Z， et al. Time windows based dynamic routing in multi?AGV systems [J]. IEEE transactions on automation science & engineering， 2010， 7（1）： 151?155.

[26] BELENGUER J M， BENAVENT E， PRINS C， et al. A branch and cut method for the capacitated location?routing problem [J]. Computers & operations research， 2006， 38（6）： 1541?1546.endprint