（系统工程专业论文）基于排队和排序理论的两阶段越库作业调度算法研究.pdf

中文摘要 中文摘要 摘要：越库作业是一种实践性非常强的物流仓储作业方式，越库作业的调度 润题是一种典型的面且较为复杂的车间作业接序阕题，本文将排队论和排序理论 中相关的算法引入到越库作业调度的优化求解中，利用柔性流水作业排序方法求 解越库中心的调度问题。 首先介绍了排序排队论中的理论基础，分别从越库作业的分类、实旄条件、 作业流程、优越性、成本构成等各个方愿对越库配送进行了分析；其次，对数学 排序问题进行分析，提出排序理论中的柔性流水作业排序问题是比较适合越库配 送作业调度的优化方法，此问题可以转化为同顺序作业排序问题和平行机排序问 题地扩展。 越库作业调度问题包括货物到达数与进站通道数之间的关系问题，进站通道 数量直接影响到设备和劳动力的成本投入，进站通道数量越多，则服务能力越大， 但成本也随之增加；迸站通道数量越少，则服务能力越小，但成本会比较低。对 此闻题，本文采用排队理论求解最佳进站通道数，首先介绍了撵队论的知识背景， 然后阐述了排队论求解进站通道数的算法流程。采用最少的服务设施，使排队长 和进站货物个体的排队时长较短。 在优纯越库中心的作鲎调度闯题中，首先介绍了排序理论中的相关知识背景， 并对j o h n s o n 规则进行了介绍，然后基于本文所要解决的问题，燎j o h n s o n 规则进 行改进，利用改进的j o h n s o n 规则求解柔性流水作业在两个处理机中心的条件下的 越库作业调度问题。并通过计算机编程求解，验证排队排序算法在越库配送作业 中的应用能力和时间响应速度。 关键词：越库配送；排队论；排序算法；柔性流水作业；仓储作业；调度 分类号：f 2 5 2 3 北京交通大学硕士学位论文 a b s 瞰c t a b s t r a c t ：讹ec r o s sd o c k i n gi sav e r yp r a c t i c a lm e t h o do fo p e r a t i o n so fl o g i s t i c s w a r e h o u s i n g 。t h es c h e d u l i n go fc r o s sd o c k i n gi sat y p i c a lo fj o bs h o ps o r t i n g ；i ti s m o r ec o m p l e x ，t h er e s e a r c ho nq u e u i n ga n ds o r t i n ga lev e r yi m p o r t a n tf o u n d a t i o n so f c r o s sd o c k i n gs c h e d u l i n g 。t h ea r t i c l ep u tf o r w a r dt h i sv i e wb yt h e o r yw i t hp r a c t i c e f i r s tt i m e t h i sa r t i c l es t u d i e dt h ec r o s sd o c k i n go nt h ev i e wo ft h e o r yf i r s t , i n c l u d i n gt h e c l a s s i f i c a t i o no fc r o s sd o c k i n g , c o n d i t i o n so ft h ei m p l e m e n t a t i o n s ，p r o c e s s e s , a n d a d v a n t a g e s t h e ns t u d i e do ns o r t i n g , a n dp u tf o r w a r dav i e wo ft h eb e s ts c h e d u l i n gm e t h o do f c r o s sd o c k i n gw h i c hi sj o bs h o ps o r t i n gf i r s t l y t h i sq u e s t i o nc a nb et r a n s f e ri n t o s c h e d u l i n gp r o b l e m 蛾mt h eo r d e ro f o p e r a t i o n sa n ds o r to f p a r a l l e lm a c h i n ep r o b l e m s 。 t h ec r o s sd o c k i n gs c h e d u l i n gc o n t a i n st h er e l a t i o n s h i pb e t w e e nt h eq u a n t i t yo fg o o d s a n dt h eq u a n t i t yo ft h ed o o r so fc r o s sd o c k i n gd i s t r i b u t i o nc e n t e r t h ei n d o o r sc a n i n f l u e n c et h ec o s t so ft h ef a c i l i t i e sa n dl a b o r s t h em o r ei n d o o r st h e r eh a s ，t h em o r e c o s t si tw i l lb e ；o nt h eo p p o s i t et h ec o s t sw i l lb el o w e r b yt h i sv i e w p o i n t , t h i sa r t i c l e p u tf o r w a r dam e t h o do fq u e u i n gt h e o r yt o s o l v et h eo p t i m a li n d o o r s ，i no r d e rt o s h o r t i n gq u e u i n gt i m ea n dq u e u i n gl e n g t hb yl e s sc o s t s t | l i sa r t i c l eu s eq u e u i n gt h e o r yt os t u d yt h ec r o s sd o c k i n gs c h e d u l i n g , a n d i m p r o v et h ej o h n s o n m e t h o dt os o l v et h et w os t a g es c h e d u l i n gp r o b l e m s a n ds o l v i n g t h ep r o b l e mb yp r o g r a m m i n g , v e r i f i e dt h ec a p a b i l i t yo ft h es o r t i n ga n dq u e u i n gt h e o r y u s e dt os h o r to p t i m a lt h er e s p o n s i b l et i m eo fc r o s sd o c k i n g k e y w o r d sic r o s s d o c k i n g ；q u e u i n gt h e o r y ；s o r t i n g ；f l e x i b l ef l o w - s h o p ； w a r e h o u s i n go p e r a t i o n s ；s c h e d u l i n g c i a s s n o ：f 2 5 2 3 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保色、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 著采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：5 抄试t 签字只期：7 r 孑年莎月，口日 导师签名： 影嚷勤 签字日期伽子年占月口日 结论 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 繇幽叫 签字日期：沙孑年 2 ，m 2 ，2i c 臌。，f f 2 表示是柔性流水作业，m l 表示第一阶段在第一处理机中心的机器数大 于等于两台，m 2 表示第二阶段在第二处理机中心的机器数大于等于两台，c m 缸表 示时阆表长。 在求出进站通道数量后，对于站台的调度，会存在以下两种情况： 第一种情况是如果j 2 中的某个任务j 2 l 存在任务集j l 的一个子集s ；，且s i 中只有一个任务； 第二种情况是s i 中存在多个任务，而且必须是s i 中所有的任务都完成了之 后，j f 2 i 才能开始。 这样划分可以使问题更加清晰，在第一种情况下问题可以转化为单机排序问 题，丽单枫排穿问题是一个比较篙单的排序闯题，采用一般的j o h n s o n 算法即可求 出最优排序，也就是最佳调度算法；但是第二种情况就比较复杂了，它不满足一 般的j o h n s o n 算法规则，所以其计算方法比较复杂，本文采用启发式算法进行求解。 1 5论文结构 本文各章节内容如下：嚣 1 绪论。简要_ 介绍了越瘁配送，并对越库配送在国内岁 懿应用现状和研究现 状进行了研究，在此基础上提出了自己所要研究的问题。 2 。越瘁配送作业方式的研究。研究了越库瓤送方式的实施条件、实用价值， 并在此基础上提出车间作业排序方法对越库配送作业调度进行研究。 3 。越库中心货流控制优化研究。由于越库中心的货流大小直接影响到越库中 心的调度问题，因此越库中心的进站通道数量的设置是很关键的，对于不同的进 站通道数，可采用不同的调度算法。 4 基予排序算法的调度算法研究。针对攀前序任务和多前序任务分别采用 j o h n s o n 规则的算法以及基于j o h n s o n 的改进启发式算法相结合对越库中心调度算 法进行研究，求出最优调度算法。 5 针对改进的j o h n s o n 算法，进行了案例计算。 6 结论。总结论文的研究成果和不足，以及后续研究的方向。 9 北京交通大学硕士学位论文 1 6本章小结 本章主要介绍了越库配送的蕃肉辨发展现状、应用现状，对不同领域的学者 在此问题上的研究现状进行了总结，并分析了前人的研究不足，在此基础上提出 ? 自己的研究方向。篱要的会绍了自己将要采耀的研究方法，指出了本文的蜃续 研究方向。 1 0 越库两已送作业方式及调度问题描述 2 越库配送作业方式及调度问题描述 越库作业的核心思想是取消库存或者只有极少量的库存。典型的越库配送物 流系统就是以最短的时间、最小的成本实现商品从制造商到零售商的转移。商品 在仓库中停留的时闻很短，通常不超过1 2 个小时。越库配送物流的有以下显著特 征： 越痒配送物流配送方式以“零库存挣为最终西标，是一种基于即时生产的 先进的现代库存管理系统。 越瘁配送物流需要以更精确的顾客需求预测为基础，是一种需求驱动的 “拉动 系统。 越库配送物流需要供应链上各方的积极参与，旨在追求和提高供应链的整 体系统性能和效率。 越库配送物流以成本效益分析为基础，是一种先进的配送战略h 越库配送物流是一个遵循p d c a 循环( 计划实施检查行动) 的连续改进过程。 无论是从公司的运作角度，还是从物流供疲链的研究的角度，对于越库配送 物流的上述特征的充分理解并达成共识，都是一个非常重要的基础与出发点，本 文的研究也是基于上面的思想进行的。 2 1越库配送模式特性 2 1 1 越库作业的分类 从国外越库配送物流成功实践和运作来看，零售商根据自身条件和能力以及 掰处的终都环境开展了较为灵活的越麾配送物流运作。关于越库配送的分类，已 有的研究按照行业或者是终端的不同都有不同的划分方法，但是都没有清楚地说 明各种分类的功能。本节主要是对越库的功能进行研究，通过功能划分可以清楚 地看出无论在那一种类型的越库配送模式下，都可以获得货物循环和整合的短周 期，因此按照其功能划分为以下几种主要的类型。 制造型越库。接收并整合入货供应，这样以便更好的实现即时制造策略。 例如，制造商可能会在工厂附近建立仓库，以用于准备相关零件或整合配套元件， 茵为这些仓库离工厂很近，麸仓库到王厂的过程也可以看成是生产线的一部分， 而不是运输节点。而且需求可以直接从m r p ( 物资需求计划) 系统预知，零件到 北京交通大学硕士学位论文 达仓库后，按照要求进行简单处理詹直接运到车间，无需存储。 配送型越库。将来自于不同供货商的入站产品合并到同一个有多种类型的 单品的托盘，此托盘的要求是一旦最近时刻的货物到达就立帮发送出去，其鹜的 是为了获得规模效应。例如：计算机分销商经常从不同的制造商那里采购零部件， 并且在一个合并装运中心合并到一批货物进行运输。 运输型越库。把零担行业或小包裹行业中的不同发货人那里接收到的货物 进行合并，以获得规模经济。对予小包裹运输，一般主要是靠运输器械和分拣器 将货物运输到越库中心的一个站台上；而对于零担货物运输，大多数是靠人工搬 运或者叉车进行运输。 与配送型越库的主要区别是运输型越瘁主要面对零担货物和小包裹货物的运 输，且运输型越库是某一个越库中心角度进行的，而配送型则可能是供应链中的 任何一个越库货配送中心，主要是在予货物的配送。而且配送型比运输型具有更 快的时间响应要求。 零售型越库。从多今货主接收货物并且根据不同商店的需求将货物分拣到 出货卡车上。这一类型最好的例证是1 9 8 0 年始创于1 9 6 2 年的沃尔玛在零售业务 上在超过了始创予1 8 9 9 年的k m a r t 6 1 。 机会性越库。在任何仓库，将某一货物直接从接受区转移到发送区来满足 某一既定的需求。 上述五种越库作业类型的共同特点是赞物整合和极短的循环周期，之所以使 这种极短的循环周期成为可能，是因为在接收货物前，其目的地已知。因此，还 哥依据信息将越库作韭分为前配送与后配送掰种类型。在前配送类型中供应商为 分销商的越库作业准备直接配送的产品，按照不同目的地将货物进行分类和对货 物进行标价或贴条形码等操作。由予对入货的托盘露经完成了标记，越库区的操 作工人可以直接将货物装入出货车辆，而不需要临时堆码。同时由于不需要接触 货物，可以降低操作成本。 前配送类型有利于分销商，但较难妥善安排，因为分销商的上级供应商们必 须知道每种货物需要多少及送到哪个客户手中，以便贴上相应的标签。因此，前 配送类型要求在各环节中有完善的信息共享。 后配送类型则缓解了这种负担，分销商从所有供应商处订购货物后运至越库 中心进行分拣整合，在接收货物时贴上标签。但这种模式会为分销商增加劳动成 本。 另终，还可以按照越库作业的操作流程分为单阶段越库作业、两阶段越库作 业及多阶段越库作业，但是它们不是孤立的，例如，某越库中心可能同时具备两 种操作流程。 1 2 越库配送作业方式及调度问题描述 2 1 2 影响越库配送的因素 越库配送要成功地实施需要各种硬件和软件条件的协调配合才能成功运行。 成功的越库配送物流运作需要以下几方面的条件： l 。供应链上的各个成爨之闻必须建立密切的合作伙伴关系。当供应链的一个 成员实施越库配送时，可能会引起其它成员成本的增加。例如，贴标签的成本、 信息成本等。因此，需要供应链上的各个成员建立密切的伙伴关系，对发生的额 外的成本进行合理的分担，互利共赢，这是成功运作越库配送的一个基本前提和 要求。 2 对产品的质量和可获得性的绝对信任。越库配送要求产品的流动没有中断， 实时运作，必须确保在需要的时候，能够获得满足质量要求的正确的产品。在尝 试越痒配送运作时，需做好以下足个方面的准备工作： 对所有适当的要求制订出详细的规范； 参与越瘴配送运作的供应链备方对这些规范要进行明确遣沟通； 为参与越库配送运作的各方提供机会，以便对这些规范进行评审、提出修 改建议，以更好的满足各方的要求； 对参与越库配送运作过程各方满足配送要求的能力要进行正式的测试。在 实施越库配送运作后，需要有一个正式的分析系统对遵守要求的情况进行 度量和跟踪。此外，还需要对所有规范进行定期评审，并进行适当地修改。 3 供应链上各成员之间的交流。越库配送是实时的运作，供应链上各成员之 间的信息交流必须是即时的。一般物流运作中快速的信息流动都是通过e d i 来实 现的。 4 越库配送运作的内部交流和控制。一垦实施越库配送运作之后，产品必须 迅速而无中断地流经越库配送设施。为了完成内部的交流任务，一般都需要仓库 管理系统必须有条形码和无线通讯设施。 5 。人员、设备和设施。由于越库配送取消了或者极大地减少了仓库储存和分 检工作，因而增加了产品收货和发货的频率和要求，并且要配置相应的资源以保 证这些要求彳罨到满足。一般丽言，越库配送运作实施的启动需要很大的投资。 6 越库配送运作的管理。越库配送运作的日常管理是相当复杂和非常重要的， 这种运作的复杂性要求管理者有更高的素质，各方的运作计划也要切实可行。 因此在整个供应链中，既要求各种硬件的支持，信息化技术的支持，还要求 各成员之间的相互信任、沟通交流、信息共享，监督合作，才能形成成功的越库 配送模式，提高供应链中各个阶段的效率，降低成本。 1 3 北京交通大学硕士学位论文 2 1 3 越库配送的运作模式 一般的越库配送运作流程如图2 ，l 所示： 供应商零售商配送巾心零售商门店 鬟越库配送运作佟业流程l 图2 l 越厍酉己邀运作流程 f i g u r e2 - 1t h eo p e r a t i o no f c r o s s - d o c k i n gp r o c e s s 各门店根据自己的销售情况，通过网络向公司配送中心的信息中心发出需 求订单； 公司配送中心的信息中心对所有门鹰的需求订单进行汇总后，透过与供废 商共享的e d i 网络向供应商信息中心发送需求订单； 供应商由予事先能够获褥对所有门店的p o s 及相关数据分析，能够较快地 组织生产，在供应商信息中心收到零售商配送中心的需求订单后，经过相 应的准备王作，首先向零售商配送中心的信息中心发送a s n ( 预先发货通 知) ，然后按照需求订单发货； 零售商配送中心的信息中心接到a s n 后，安排组织收货准备工作，首先 根据各门店的需求，对商品进行分拣、包装等一系列i 作，然后把商品配 送到各门店。通常要求商品在c d 物流场地的停留时间不超过2 4 小时。 越库醌送要求在浪费最小的情况下确切的知道在确切的时间确切地方需要的 确切的货物的需求【l i 】。尤其是对于小件、流动频率高的货物，在这种情况下，货 物可以从多个供应商到达某个商店，在这个过程中配送中心便可以从更短的前篝 时间中获益。而传统的仓储运作主要是应用子流动频率低的大宗货物。一般，越 库配送都会包含货物分解、货箱分拣、货物单元重组；而传统仓储则包括货物分 解、货箱存储，并对已经安排好的单元货物进行拣货。 补货订单的数量是根据越库运作中零售商的订单而确定的，当补货订单到达 时，配送方就已经知道零售裔的订单数量。然蔼，在仓储运作中，补货数量一般 是根据经济订货量来确定的。当补货订单到达时，配送方不知道零售商确切的订 1 4 越库配送作业方式及调度问题描述 单量。 已经准备好配送的货物要求在天或几个小时之内发送到零售商店。因此， 要求其运作具有高效性。为达到这个目的，一方面，制造商需要有更复杂的订单 处理设施来高效的处理单个商店的订单，另一方面，制造商需要建立e d l 设施， 以使所有的泣务文档可以通过e d i 进行发送。 对于传统的物流仓储模式而言，库存是非常重要的基础，这样可以使仓库建 立一个安全库存来处理具有较长前置时闻的产品以及某些不确定的需求。而越库 配送模式下是不需要安全库存的，但是如果某单个门店的需求有着很大的不确定 性，就会绘制造商带来很大的压力或者无法满足客户需求，因此要求其他环节的 相互配合，已达到及时响应。 仓储模式下，i t 设施和仓储管理系统维护整个系统的运作过程。越库配送运 作主要是在配送中心对商店订单的分拣，这样就不需要太多的i t 设施，但是它更 依赖于电子商务设施。例如w a l m 矾建立了卫星网络应用于整合货物订单，使公 谣能获得更多的整车数量以免产生更多的库存成本。根据w a l m a r t 2 0 0 5 年的年报， 公司的数据中心平均每周内跟踪超过6 0 0 0 0 的库存单元( s k u ) 并且拥有一个大 予5 7 0 t b 的数据仓库，报告说w a l m a r t 的数据仓库是“比因特网上的所有网页都 大0 9 。 越库配送运作中，配送方与制造商和零售商之间可以共享信息，制造商非常 清楚零商店的需求，并且制造商和零售商之闻相互信任。w a l m a r t 的卫星系统可 以使公司的商店、配送中心和供应商之间信息共享。然而在传统仓储运作中，只* 有在产品的数量低于某一个水平的时候才会下订单，制造商很难知道某个零售商 的需求，这样就有可能造成货物不能及时到达或牛鞭效应。 传统仓储运作中订单分拣会造成大量的旅行距离，对每一个货物的操作都会 花费大量的时间，因而，完成订单是一个劳动密集型作业。越库运作则大量地减 少了无价值的附加操作活动，同时也减少了对货物的损害。 越库配送模式下，产品不用进入仓库存储，最多也只是短时间存储，因此， 在零售商处会有更长的货架存放寿命，这是有益于零售商的；在传统仓储模式下， 零售门癌没有下订单前，货物就要一直存放在制造商仓库货架上，它们在零售商 的货架存放寿命就比较短。 因此从上面对订单类型、毒 货方式、订单处理、信息传递及仓储管理等方面 的研究可以得出结论，越库配送可以使货物有更快的响应时间，更小的库存占用 或者没有库存，货物的流动是没有停滞的，这也是物流配送所要考虑的墨 常重要 的因素。 1 5 北京交通人学硕十学位论文 2 1 4 越库配送的优越性 一般情混下，配送战略包括传统於库存战略、经过性物流战略和门店直送战 略( d s d ) 2 0 1 。但实际上零售连锁商一般不会采用单一的配送战略，而是采用组 合的配送战略。表2 1 列粥了三静配送战略在风险承担、运输成本、仓储威本以及 配送时间等各方面的优势对比。 表2 - 1 三种配送战略的比较 t a b l e 2 - 1c o m p a r i s o no ft h et h r e ed i s t r i b u t i o ns t r a t e g i e s 战略属性传统配送战略d s d 配送战略c d 物流配送战略 风险分担利用 运输成本 降低进货成本降低进货成本 保管成本 无念痒液本无保管成本 需求变化延迟配送 延迟配送 d s d 是指商品不经过仓库和配送中心。实旄d s d 麓制造商或供应裔把商品直 接运送到零售商门店。d s d 战略的优势在于g 零售商避免了经营配送中心的费用； 缩短了提前期。 但是这季中战略的缺陷有以下两点： 由于没有中央库存，因而否定了风险分担效应； 制造商或供应商的运输成本增加。 d s d 在杂货业中较为流行，采用d s d 可以保持商品的新鲜度、减少商品运输 破损、缩短交货周期和时间等。 与传统的仓储配送战略相比，传统的仓储模式中，仓库持有存货，直到客户 订单到达后，工作人员依据订单从货架上拣选货物，然后打包运出。其补货策略 主要基于仓库存货量来制定。越库配送物流战略的最大特点是取消或者极大程度 地弱化了仓库的储存功能，在越库作业中，配送中心库存极少，在接到客户订单 后向上级供应商提货，其补货策略是基于客户订单需求而制定，货物不进行长期 储存。这体现了与传统的仓储配送战略截然不同的运作方式，它的成功运作和实 施需要诸如在理念、组织结构、物流设施等方面进行一系列变革。与仓储库存相 毙，优势显而易冤。表2 - 2 是对两种作鲎的比较。 1 6 越库配送作业方式及调度问题描述 表2 2 越库作业与仓储作业的比较 t a b l e2 - 2c o m p a r i s o no fc r o s sd o c k i n ga n ds t o r a g e 顾客货物差库存装卸及运输货物前货物到达及 配送战略 需求损率成本成本置期时性 越库作业大，整车装运低无低短高 普通仓储库存模式无明确要求高高一般较长一般 通过表2 2 中的比较可以显示出越库作业的多种优势，如可以降低分销成本， 减少仓储空间，降低零售商的库存，使整个供应链的仓库数量减少，降低库存成 本和装卸成本，降低货物破损率，提高分销中心的利用率，整合订单以提高客户 响应水平等。同时，该配送模式是符合准时制策略的，可为企业实施准时制造提 供良好的保障。 因此可以得出结论，越库配送模式的物流可以在时间、空间和成本上获得较 好的效益。具体而言，参与越库配送运作的供应链上各方可以获得如下明显的利 益和改进： 从整体上降低配送成本； 降低零售商门店的缺货率； 提高配送中心的利用率，加速配送中心商品的周转； 降低库存水平； 增加商品在门店货架上的时间； 减少门店商品交货的复杂性； 更快的信息共享，能够更快的获得商品活动的信息，如流动信息和销售信 息等； 减少对配送中心的物理空间的占用。 越库配送长期成功实施还可以获得以下潜在的预期利益： 由于有着更快的信息交流和客户响应，因此可以增进零售商和供应商之间 的合作关系； 通过减少仓储、减少停留时间等措施可以降低整个供应链系统的成本； 减少了在配送中心的停留，因此可以提高整个供应链运作的效率； 准确、持续、快速地响应和满足顾客需求。 从国内零售连锁业来看，大多数零售商仍然采用的是传统配送战略与门店直 送配送的组合战略。上文已经提到的联华超市有限公司目前已经开始了越库配送 战略的探索与实践。 1 7 = i 匕京交通人学硕士学位论文 2 1 5 越库配送成本构成 从越库配送的运作过程可以看出越库配送包括货物的接收、分拣以及运输环 节等，下面分别对越库配送不同环节的成本构成进行研究。 1 收货成本 越库配送本身是配送中心运用的一项技术，以保证配送中心在一天之内完成 胄台新有货物的接受、分拣、配送，常常能够实现准时翩标准。接收货物的过程 包含以下内容： 预定到达时阀和托运人数据的电子收据； 接收顾客发送的订单的详细信息的电子收据，包括运输中的细节、托运人 和目的地： 确定接收和发送货物的可选月台位置； 每个货盘到达后的条形码扫描； 接收到的货盘的条形码和e d i 通知书的比较； 接收的货物的差异鉴定，并与通知书进行比较； 此顼活动的成本包含仓库和行政管理费用、叉车和托盘占用的时间费用等【2 h 。 2 ，劳动力成本 越库配送和仓储配送中的物料处理都是劳动力密集型的，越库配送的劳动力 成本尤其昂贵。实际上货物形式的多样性( 特别是在零担运输中) 导致其自动化 难度很大，甚至有时几乎不可能实现自动化。而且，就算在零售型越库中货物形 式比较统一的情况下，就成本和生产量磊言，岛动讫物料处理系统也不像入力搬 运那样具有更好的灵活性，并且自动化技术也会造成巨大的固定成本。因此，许 多公司不愿将公司监务引入一个动态物流环境巾阱】，然丽，只要处理戒本没有超 过运输成本和库存成本的节约，越库配送仍然是比较经济的。此外，根据b a r t h o l d i 【2 3 1 ，越库配送终端恰当的布局设计可以降低旅行距离，避免阻塞进而减少劳动力 成本。例如，越库配送也在装卸货物上帮助w a l m a r t 降低了装卸货物的劳动力成 本( 洲。 3 运输成本 尽管越库配送不会产生储囤费用，但是其中的运输环节却比直接运输要花费 更多的时间。因此，导致了运输成本的增加。然两，对于零售商来说，对零担卡 车和小包裹运输，越库仍是降低运输成本的一种方式。例如，w a l m a r t 只从供应 商接收满载卡车的货物，然后通过越库中心将货物分装到其他卡车上，每个卡车 上都满载着不同种类的货物，以满载的形式运送到各个门店，这样就大大降低了 它的运输成本【2 5 1 。 1 8 越胯配送作业方式及调皮问题描述 4 i t 投资成本 先进的科技对越库配送的成功实施是至关重要的，诸如供货商、越库运作方以 及客户之间的实时信息共享【2 6 1 。这就要求有一些重要的技术投资，如e d i 技术、 条形码技术、扫描技术，还包括仓储布局变化，如低的顶棚和少的货架等等。 为了使越痒效用达到最大，w a l m a r t 使用卫星网络支持越库库存信息系统 2 7 1 。 这个系统使w a l m a r t 降低了2 - 3 的成本，达到了一定的经济规模。有了这个系统 的支持，货物在4 8 小时之内连续不断地运送到门店焉不用将货物存入库存，这样 w a l m a r t 的货架补货速度就比它的竞争对手快4 倍。另外，w a l m a r t 应用它的卫 星通信系统将每天的销售数据直接发送给它的4 0 0 0 名供货商【2 引，以达到信息共享， 实时交互响应。 w a l m a n 在射频识别技术上投资了2 0 个亿，从长远来看，通过提高供应链效 率能够节省巨大的成本。同时，大量弓l 迸射频识别技术还会进一步把成本降至更 低【2 9 1 。 5 。设备相关费用 相关设施的成本与越库的形式有着直接的联系，如越库月台的数量、越库中心 所采用的设计和布局等都会影晌到总成本。进出口通道太多就会增加成本，然焉 太少又会导致运输供应延误和产品的积压1 3 0 】。b a r t h o l d i 和g u e 做了一系列的计算 及实验以确定哪种越库形式的越库成本最低，运行拥塞最2 3 1 。 传统仓储配送包括了收货、上架、存储、订单分拣、包装、标记、转运和运 输，而越库配送本着库存最小化或零库存的目标，压缩了存储和部分操作环节【3 0 】。 一般来讲，仓储配送诸环节中存储和操作成本最大。实际上，存储成本包括了物 料的自然安全保管成本，如房屋占用成本、设备费用、设备维护成本、税率、保 险、折| 墨费用以及管理费用的分摊和其他间接费用等，操作成本包括货物的装卸 费用【3 ，越库配送通过直接将接收到的货物发送给客户而不进入仓库存储来降低 物料处理费用【3 2 】。w a l - m a r t 通过越库配送这种方式降低了库存成本，从弱比它的 竞争对手高出了2 5 的盈n t 3 3 j 。 然而，要想使越库配送更为有效地运行，以上提到的越库运作和相关设施引 起的其它成本在实际操作中还是会产生的。另外，越库配送可以通过合并各个门 店之间的订单以及按照卡车满载量进行装载等来降低采购成本。工人把货物装上 货车然后运向不同的门店，越每个货率上装有不同供应裔提供的货物列。 越库配送适用于季节性的、大批量的货物处理，并且也被大多数商家和食品 供应商应用子商店之间的运输；另外，越库配送也被用予集中贴标签的物流环节， 也可用于整合现有的配送中心。 总之，越库配送通过压缩库存和操作活动这两个费用最大的环节，加速产晶 1 9 北京交通大学硕士学位论文 从供货商到各个门店的运作流程，减少系统中的戚晶库存，并增加了库存周转。 正如w a l - m a r t 员工所悉知的理念：“越库配送从概念上讲是一个货物流，我们不 想让健在任何地方有停滞。然而，诸如c o l e s 超市一样很多零售商都没有实施这 种技术，主要原因在于它成本高又难于管控。为了运行越库配送系统，w a l m 缸 投入了巨大的成本来维护它的连锁体系。例如，越库配送要求配送中心、供货裔、 单个门店的各个销售点有持续的信息共享，以便掌握库存和限定时间内的订单需 求。嚣此，w a l m 娥启用了卫星系统每天囊4 0 0 0 个供货商发送销售点的数据。 w a l 。m a r t 越库配送得以成功实施的另一个关键因素在于它拥有快速且高度负责的 运输体系，他们拥有1 9 家物流配送中心，近2 0 0 0 家分公司配有货车【蚓。 2 2两阶段越库作业调度问题及其特征描述 在两阶段越库作业中，货物到达配送中心后由工人按照其预先设定的接受区 将货物放入，然瑟另一缀工人将这些货物按照一定的规则把接受区货物运到滋货 拖车上，如图1 3 所示，将此问题转化为车间作业排序问题如图2 2 所示： 第二 处理机中心 缓冲区 第一 处理机中心 图2 2 基于排序算法的越库中心作业流程 f i g u r e2 - 2s o r tb a s e dc r o s s - d o c k i n gj o b p r o c e s s 在图2 2 中，第一处理机中心也就是第一阶段，有一定数量的处理机，作业在 第一阶段分别经过某一个处理机处理之后，直接被送到第二阶段，也就是第二处 理机中心进行处理，经过第二处理机中心处理完毕以后，作业在越库中心的全部 处理过程完毕。发生以下两种情况时，要将货物暂时堆放在缓冲区：第一种，当 越库配送作业方式及调度问题描述 第二处理机中心的所有处理机处于繁忙状态时，这时从第一处理机中心完成处理 任务的货物，则暂时先堆放在缓冲区：第二种，当第二处理机中心待加工的作业 有紧前工序作业集时，在其紧前工序作业集中的所有作业还没有完全完成时，暂 时将已经加工好的紧前工序作业集的部分作业放在缓冲区。 本文是基于车间作业排序算法对越库作业的调度问题进行研究的，首先描述 一下本文涉及到的排序算法的相关概念，包括平行机排序、不可中断时间表长、 可中断时间表长、总完工时问、最大延误、车间作业同顺序作业、柔性流水作业 等概念。 2 2 1 平行机排序 平行机排序问题是多处理机排序问题的一种情况，在多处理机排序问题中， 如果所有的处理机都具有相同的功能，就是平行机排序问题。 在平行机排序问题中，一般假定有n 个作业组成的任务集t = 互，乃，瓦 ， m 台处理机组成的处理机集p = 只，只，己 。 任务集一般分为相关的和无关的两类。处理机类型分为同速机、恒速机和变 速机。对于同速机，其加工速度相同，通常设为1 ；对于恒速机，其加工速度向量 为b = 慨，6 2 ，6 肘 。其中处理机p i 的加工速度为b i ( i - 1 ，2 ，m ) 。在这两种 情况下，任务集的加工时间设为p = 0 ，p ：，p 。) ，其中，任务t j 的加工时间为 p j ( j = l ，2 ，n ) 。如果处理机是变速机，则任务的加工时间与处理机加工速度 之间的关系可用加工时间矩阵p 表示。 尸=( 2 1 ) 其中，任务瓦在处理机p i 上的加工时间为：p i j ( i - 1 ，2 ，m ，j = l ，2 ，n ) 。 2 2 2 不可中断时间表长 对于任务具有任意加工时间的，即使所有的处理机为同速机，而且任务集是 无关的，则问题也是n p 难的18 1 。为研究方便，同速机不可中断极小化时间表长 问题一般描述为只0 c 哪。 2 l 玎 玎 阱鼢； 北京交通人学硕士学位论文 2 2 3 可中断时间表长 有时允许任务在加工时可以中断，以使问题可以简化，甚至可以使时间表长 缩短，如果任务集是无关的，则问题比较简单。问题的一般描述为匕l p 仰l 。 2 2 4 总完工时间 对于目标函数是加权总完工时间的情况，如果各个任务的权因子不同，即使 限定只有两台处理梳，问题最l 罗国，c ，也是n p 难的雒8 1 。所以当权因子相同时也是 n p 难的，即蜀标函数为总完工时间问题。在这类闽题中，如果任务集是相关的， 则问题都比较复杂，只有极个别情况例外。对于同速机的情况，可中断往往弗不 能使问题简化。如果任务集是无关的，则问题相对简单。其问题的一般描述为 圳q 。 2 2 5最大延误 由撵序问题的传递性和时间表长c ，姒与最大延误l m a x 两者之闻的关系可知， 目标函数为时间表长c 瑚x 的n p 难阀题，当目标函数为最大延误l 啊粼时，仍为n p 难问题【l8 1 。这类问题大多比较复杂，只有在任务加工时间为单位时间或任务加工 可中断的情况下，问题才有多项式算法。因此，如采任务加工不可中断，只有任 务加工时间均为单健时闻且优先约束为入树的排序问题相对篱化，般描述为： p m i n t r e e , p j = l 陋一。 2 2 6 车间作业同顺序作业问题 同顺序作业排序问题也称流水作业排序问题，可以表达为 f i i g ( 2 2 ) 其中g 是完工时间的不减函数，这是一类常见髂车闻作业排序问题，在此问 题中一般把任务称为作业，设有作业集j = “，j ：，歹。 ，处理机集 m = ，m ：，m 。 ，每个作业巧有m 道工序：正，五，工序t o 的加工时 间为脚，p i j 一 o 。各作业以此在处理机m 1 ，肼2 ，m 卅上完成各道工序。 在同顺序作韭排序闯题中，各俸韭均依次在处理祝m ，膨2 一，m 。上完成备道 工序。但对于台处理机来说，各作业在其上的加工顺序可能不同。如果在全部 处理机上各个作业的加工顺序也相同，则是排列排序。对于n 各作业，m 台处理 越库配送作业方式及调度问题描述 机的同顺序作业问题，由于每台处理机上n 道工序的可能排序数为n ! ，因此全部 的可能排序数为( n ! ) 胂。如果仅考虑排序排列，则排序数为n ! 。但是，对于m 4 的情况，同顺序作业排序问题的最优排序未必是排列排序。即，排列排序中可能 不含有最优排序。 2 2 7 柔性流水作业排序 柔性流水作业排序问题是一类混合流水作业排序问题，也是一类复杂的车间 作业排序问题。在柔性流水作业排序问题中，设有s 个处理中心：z l ，z ，z 。 第1 个处理机中心z l 中有m 1 个同速机。任意两个处理机中心之间具有无限的存储 能力，n 个作业：，。，j 2 ，j 。，作业j j 有s 道工序：互，正，一，乙，工序t l j 的加 工时间为珈，p l j 一0 ，1 = 1 ，2 ，s ；j = l ，2 ，n 。工序t l j 可在处理机中心z l 中的任一个处理机上加工。其一般形式为： 册l 肼l ，m 2 ，m ，恒 ( 2 3 ) 其中g 是作业完工时间的不减函数。如图2 3 所示： z lz 2z 3 图2 - 3 柔性流水作业流程 f i g u r e2 - 3f l e x i b l ef l o ws h o pp r o c e s s 由图2 3 可知，如果每个处理机中心均只有一台处理机，则问题转化为同顺序 作业排序问题；如果只有一个处理机中心，则问题转化为平行机排序问题。因此 柔性流水作业的排序问题是平行机排序问题和同顺序作业排序问题的扩展。 而对于两阶段越库作业调度问题，可以看成是由两个处理机中心组成的一个 柔性流水作业问题。 2 3本章小结 本章首先对越库作业进行了描述，分别从其分类、实施条件、作业流程、优 2 3 北京交通大学硕士学位论文 越性及成本构成各个方面进行了分析，然后，对数学排序问题进行了简要概述， 确定比较适合越库配送作业调度的排序方式为柔性流水作业排序，但是柔性流水 作业阀题是排序闯题中较为复杂的闻题，此问题又可以转化为同顺序作业排序闯 题和平行机排序问题的扩展。 越库中心货流控制优化 3 1问题的提出 3 越库中心货流控制优化 由越库作业的性质可知货物的到达是不能间断的，假定货物的到达服从 p o i s s o n 分布，且每个到达的货物在越库中心所需要的处理时间服从指数分布，在 越库中心有c 个越库站台，丽且到达的货物遵循先到先服务( f c f s ) 的原则。奚| j 问题转化为排队论中的多服务台负指数分布( m 侏嗄c ) ：( o o o o f c f s ) 模型。 在实际应用中，影响总体效益的因素除了在越库中心内对货物本身的调度方 法之外，根据不同时段或季节货物的到达率和市场需求来调整进站通道的数量也 是很关键的。这个最优化过程可以通过排队论的( m m c ) 模型来计算。根据计 算的结果可能会得到下列两种货物调度方案： 第一种是当到达顺序与离开顺序相同时，这其实是平行机排序调度问题的一 种特殊形式，如图3 - 1 所示： l。匹 。圆 ? l 器， 毒l i口匹 j 7 o 匝口 1 2薹 恁：-幺 j 2 磐 ： 嚣 妻一 豺 ：l 鬻缫搦缀；彩鳃话瓣麓糍殇缓缀鲻缀缀缴弱缀缀戮醐瑷缓戮彩瓣翳黪甥缓缀镕疆麓 l。匝 一卜一卜一一卜寸 。阅 k 入口一作业过裰出1 2 1 k 匿3 一l 司颁缪越浑调度 f i g u r e3 - 1t h es a m eo r d e ro f j o bs c h e d u l i n g 这样可以将间题转换为含有k 个平行处理机的排序问题来处理，则阀题就会 简化。在这种情况下，到达车辆和离开越库中心的车辆顺序是相同的，出发的1 号车辆其在作业过程的前序任务也只是l 号入口车辆，即不存在出库车辆在入库 时有多个前序作业的情况。 而另种情况是，存在多个前序作业的情况。这样问题比较复杂，而且这种 方式也是实际应用中最普遍的方式，本文采用启发式算法来计算。 北京交通大学硕士学位论文 l口匹 “ 一- = - = _ = _ = = - - = _ ? = ， r l 旺 一z i f 1 二 亨 嘎， h _ ， l j l口四 一一l #，l 彬 口旺，： _ l 2 ， 蠹，妻 7， 2 j二 i 。“ 孑 ：。p ： 绷 q ，学 l 。o 。z ： ， v “ i i蔓，g 一秽：瑞 ：二 l l 口囤 ，+ ：i 善 口圈 ? 二 k ： k 参+