某楼层库叉车调度问题研究.docx

装备大观i equipment showcase 设施设备某楼层库叉车调度问题研究北京物资学院王成林花龙雪 近年来，在经济全球化的带动到了所有事件的数据，决策时完全 动态调度的出现，一是为了保下，社会节奏日益加快，人们对物 以已知数据为依据，系统在整个作 证低优先级的任务也能被调度，二 流水平的要求越来越高，要求物流 业过程中一直使用同一个调度方 是为了处理出库频率较低的、任务 活动的反应速度越来越快，装卸搬 案，且该方案是在系统状态和作业 到达系统的时间较分散的系统出库 运作为物流活动的重要组成部分， 任务都已确定的前提下，能够使系 调度。对于绝对可预测的系统一般 贯穿于整个物流中心作业流程的始 统各项性能指标得到优化的合理调 不采用动态调度。但是没有绝对稳 终，通常成为决定物流速度的关 度方案。静态调度算法最显著的优 定的系统，当出现临时过载情况键，而装卸搬运设备的合理化调度点是稳定性和可预测性好，且额外时，调度方法要考虑到选择临时最 可以直接决定物流的作业效率。开销小，一旦寻找到一个合适的调紧急的任务去执行，放弃那些优先 度方案，便能够保证所有任务的截 级高却不太紧急的任务。因此，可1叉车调度方法止期都可以得到满足，故得到了广以考虑在静态调度的基础上，准备 一般企业的物流配送中心装卸泛应用。动态的应急机制。搬运设备均以搬运车辆为主，而叉(2)动态调度。动态调度算法 车是物流中心最普遍的搬运车辆，需要在变化的环境中做出反应，是 2叉车调度影响因素分析指系统能够根据当前的状态信息动 在以叉车为主要搬运设备的仓库装21叉车调度存在的问题卸搬运调度系统中，叉车调度策略态地调整调度方案来控制系统的作叉车的合理化调度是仓库装卸 的制定是保证系统稳定运行以及提业过程，因此，这类算法应用比较搬运系统正常运行的关键，但在很 高系统作业效率的关键。叉车的调灵活，适合于任务不断生成。与静 多中小型物流配送中心，叉车的调 度一般由三部分构成，即作业排态调度相比，动态调度更能根据作度经常出现以下问题： 序、作业分配和作业执行。本文以业系统的实施情况形成更具有操作 (1)叉车利用不充分，作业量 某烟草企业楼层库为研究背景，分性和适用性的调度方案。但是，动不均衡； 别介绍两种常用调度方法在叉车调态调度方案的执行必须充分考虑以 (2)叉车数量配置不合理，造 度中的应用，即基于优先级的静态 下两个方面的信息：一是调度过程成资源浪费； 调度算法和基于“最短路径法”的必须充分考虑并利用好反映系统状 (3)叉车搬运路径无规则，经 动态调度算法。 态的实时信息；二是形成调度方案常出现拥堵现象；的过程必须在不影响系统运行的短(1)静态调度。静态调度是假(4)叉车停放不规律，操作非设在应用优化算法求解之前已经得时间内完成。 标准化；万方数据设施设备equlpment showcase i装备大观(5)叉车故障以及叉车事故。此，有必要对叉车司机进行统一培经分析，楼层库每日的订单承22影响因素分析 训，并制定严格的叉车操作规范。接量变动范围很大，且订单到达时 针对以上叉车调度问题，分析(5)调度决策者。调度决策者 间和频率有很大的不确定性。针对其影响因素主要来自于以下几个方 是叉车调度指令的下达者，其对仓 这种变动性较大的订单到达模式， 面：库作业环境的熟悉程度对包括资本文将其分为“订单大量、集中到(1)仓库搬运路径。仓库搬运 源空闲状态等现场调度信息的实时达”和“订单少量、分散到达”两 路径设置不合理，可能会造成仓库掌握程度，对不同调度方案的合理 种情况，并分别提出基于订单优先 作业空间利用率低，高峰期叉车拥选择和灵活运用能力等是叉车调度级的静态调度算法和基于“最短路 堵，从而影响叉车利用率。同时，方案合理选择、调度指令成功下达 径法”的动态调度算法。 搬运路径不规范极容易造成叉车事 以及调度任务顺利实施的关键。31 “订单大量、集中到达”模 故。总之，仓库搬运路径设置的合 式下叉车调度研究理规范性，是叉车调度合理化的基 订单大量、集中到达时，可以3某楼层库叉车调度研究础。将研究对象看成是一个静态的任务 已知某烟草企业楼层库是订单(2)储位布局。储位布局合理 集，假设当日到达系统的所有订单 响应型仓库，该仓库为5层楼结构，化也是保证叉车合理调度的关键，信息均为已知，采用的调度算法是 各层楼之间的货物转储由升降电梯例如基于品规关联度的储位布局或基于订单优先级的启发式调度算 完成，所有出入库及转储作业全部是基于先进先出原则的储位布局法，即对录入系统的所有订单做系 通过电动叉车及人工来完成。货物等，很大程度上都是为了减少搬运统化的归类处理并划分订单优先 的装卸有两种状态，一种是以托盘车辆在途时间，节约仓库搬运成级，然后按照优先级顺序并结合订 为单位直接进行装卸，即整托出本，同时提高出入库作业调度效单特性调度合适数量比的叉车对订 库；另一种是将不同品规的单箱货率。单进行批量处理。 物码成整托盘进行出库，即非整托(3)月台配置。对于设有多个311调度步骤。具体的叉车调度步 出库。整托出库时每个出库任务最装车月台的库区而言，月台合理化表1楼层库资源配置信息表 多可配置3辆叉车，可满足叉车等待配置也是保证叉车合理调度和提高时间最短且出库效率达到最高；非序设备名称数量 计量单位出入库作业效率的关键。月台的配号整托出库时，最多可配置2辆叉车，l电动叉车19辆置需要符合就近原则和负载均衡原可使叉车等待时间最短，出库效率2液压叉车8辆则，使得叉车在月台和取货货位之最高。楼层库参与调度的设施设备3液压升平台(月台)8个间的往返时间最短，将单位货物的4移动小车17 台及人员配置情况见表1。出库作业成本降到最低。6叉车读写设备19 套在出库高峰期，电动叉车数量7装卸人员25人(4)叉车司机。叉车司机的资不足的情况下，需要调度手工装卸8升降电梯3质高低和主观偏好不同能够严重影人员操作液压叉车辅助完成出库任 表2出库作业叉车及人员标准化配置表响叉车调度的标准化和规范化。例务，但是由于液压叉车作业效率较出库设备 出库模式 叉车辆 叉车司机 手工 车拼员搬运人员如司机熟练程度不同使得驾驶速度低，其利用率也很低，具体的电动电动叉车 整托出库 33不同；司机主观偏好不同使得搬运(19辆) 非整托出库222叉车及手动液压叉车在执行出库作路径的选择不同；司机资质高低不液压叉车 整托出库 44业时的标准化数量配置情况见表2。(8辆) 非整托出库34 34 2同使得其故障排除能力不同等。因logistics technology(equipment)2014 no 8万方数据红装备大观f equipment showcase 设施设备骤如下：间，i为订单编码，发货点记为0；doi表示客户i与发货点 (1)确定系统所开时间窗大小，根据系统的处理之间的距离；v是运输车辆的j的标准行驶速度。j能力录入当天处理订单，并确定订单优先级。通过公式(1)的计算，可以反推出订单的触发时(2)匹配配送车辆，并根据订单开始执行时间安间ts，根据订单触发时间先后的不同，确定订单的优 排相应配送车辆在合理时间停靠到指定月台。先级。订单的触发时间越靠前，其优先级越高，在确定(3)匹配取货货位及装车月台。 订单优先级时，需要遵循以下原则： (4)叉车调度。按优先级顺序为订单匹配叉车及(1)订单优先级的设定需满足客户要求送达时人员，并生成订单执行作业计划表以及叉车调度作业间； 计划表，将调度指令在指定时间下达到叉车终端。叉(2)同一优先级的订单，优先执行一层存储量及 车作业调度计划表见表3。存储品规即可满足要求的订单类型，需要触发转储作业表3叉车调度计划表 才能完成的订单优先级设定相对靠后；任务 订单 触发 计划结 执行 目标 订购 出库订单号 优先级完成 (3)同一优先级的订单，对订购品规为核心品序号 类型时间 束时间 时长 货位 数量月台l规，且订购量比较大的订单优先考虑；2(4)在同一级别的订单中，优先执行小型运输车 (5)实时监控叉车运行状态，统计叉车的历史轨 辆即可满足送货要求的订单，以减少总排队时间。迹及在特定时问段内的运行时长、启动和关机时间等 313方法评价。基于优先级的静态调度算法力求在所 信息。有助于调度管理者做好以下工作：考察叉车 开时间窗内完成所有录入系统的订单的出库任务，既要 使用是否充分；考察叉车司机是否存在疲劳驾驶和 保证楼层库整体的订单完成率，又要确保每个订单的到 劳逸不均的状况；为叉车调度提供参考，合理安排 货及时率。同时，这种调度方法能够保证所有叉车均参叉车工作时间；记录叉车维护时间，监督相关部门 与作业，且作业量均衡。做好维护；考察超速等违章状况，方便提供线索追 经过以上分析可知，静态调度算法最显著的优点是 究违章责任。 稳定性和可预测性好，且额外开销少，一旦寻找到一个312订单优先级的确定。将每日待执行订单录入系统合适的调度方案，便能够保证所有任务的截止期都可以 之后，需要对其进行优先级的分配，以确定订单的执 得到满足，故得到了广泛应用。但由于静态调度算法一 行顺序，并粗略计算出每个订单的执行时间进而推算旦做出调度决定后，在整个运行期间就无法再进行更 出订单的触发时间。在确定订单优先级时，首要考虑 改，因此，静态调度的灵活性不如动态调度，不适合于 的是客户要求的送达时间，然后根据此时间点确定最 不可预测环境下的调度。 后的订单触发时间。在订单执行过程中需要考虑的时 32 “订单少量、分散到达”模式下叉车调度研究 间包括订单的出库调度时间、装车时间、运输车辆停 当订单少量、分散到达时，出库任务是随机、不断 泊及等待时间以及车辆在途时间几个方面，计算订单 生成的，针对这种模式，提出基于“最短路径法”的动 触发时间点的公式见式(1)： 态调度方法，调度的目标是叉车在途时间最短，搬运成t，=ts+tw，+t，+d。iv(1)本最小。整个系统由响应订单执行开始，当接到订单 t，为客户i的订单需送达的时间；ts，为客户i订单开时，首先分析订单特性(订购品规和数量)，根据需求 始处理时间(触发时间)；tw为订单i出库调度等待时间t匹配运输车型，然后，根据所订购品规查询其库 时间，主要是车辆停泊及等待时间；t，为订单i的装车时存情况(存储货位和剩余库存数量)，确定所有可取货万方数据设施设备equlpment showcase i装备大观?型货位，最后进行叉车调度，在所有空闲叉车、人员及月q3：整托出库时每辆叉车的工作量，q2：非整托出 台中进行匹配，匹配的原则是三点之间距离最短。 库时每辆叉车的工作量；321调度步骤。具体步骤如下：v：叉车运行速度。 (1)将订单信息录入wms系统，系统根据订单特 构建数学模型：性(订购品规和数量)检索库区内各个储位的信息，从口而确定订购品规的可取货货位。m加jj-14口-1(2)启动叉车调度指令，叉车定位监控系统会输ltl口2 l”+ll口出一个所有叉车运行状态的实时信息表，见表4。同时，月台检测设备将各个月台的运行状态反馈给系统。p|址：f1，又车鹚靠在l号货位一1yiesx,11v七岛m vzb坩=(竺磊g篓燃台咐g是lo，叉车j：c没有停靠在得库区(3)调度系统提取可取货货位、空闲叉车以及可耻徽用小岛停靠月台三方面信息，并通过室内定位系统确定各信标一1 j、-1lo，不从，货位取货运至口月台一”节点之间的距离，按照最短路径原则，用matlab遗传算法工具箱进行测试，求出最优解。一【0，第鹚眄车没被调用(4)将最优解转化为调度指令在指定时间下达到叉车终端和相关出库人员手中，执行出库作业。llj=lj,，当f=，时，l0=o322模型构建。变量定义如下：m：空闲可用月台的数量(m8)； 323局部搜索混合遗传算法设计。最短路径调度算法 n：可取货货位数量(n38)，包括库区内的27个 的关键技术问题是建立叉车调度问题的复杂约束条件 固定仓储货位、3个转储暂存区和8个月台附近的入库暂的任务分配模型。根据仓库调度资源和调度环境的具 存区； 体特点，对标准的遗传算法做出两处改进：一是在每 q：空闲可用叉车数量(q17)，1号月台的19辆叉车产生一代种群后，利用sweep算法对种群进行优化，去 中有2辆停放在高层以备随时执行转储作业；掉不符合约束条件的劣解；二是寻找种群中个体间的 st=(1，2， ，n，n+1， ，n+m)：库区货位 高效邻域结构，局部搜索邻域中的所有可行解并保留与月台编号集合； 最优解。在上述基础上进行选择、交叉、变异操作，s：=(1， ，q)：叉车编号集合； 具体求解过程如下：l。(i，j，ge s，)：叉车停靠位置、取货货位、空(1)编码与适应度函数。遗传算法在编码设计中 闲月台任意三点之间的叉车行驶时间之和，单位为s；常采用二进制编码、格雷码和整数编码机制。本文采 t。：叉车k的剩余工作能力，单位为s；用整数编码机制，编码每四位为一组，表示叉车在每个空闲月台和货位问的分配。假设有3辆空闲叉车可用 q：待执行订单的订购量(以托盘为单位)，于调度，在5、6、7号货位有满足订单需求货物可以运 表4楼层库所有叉车实时信息一览表至1、2、3号月台进行装车，叉车初始停放位置为1、叉车编号 地点 状态 速度剩余能力 更新4、5号月台处，一种可能的编码形式为2462 125108一16l1号月台 开1000kmh 523h13：453573。前四位编码2462中的各个数字分别代表2号叉车081621号月台 关230h13：,15从4号月台行驶至6号货位取货后送往2号月台装车。根081632号月台 开1034kmh 368h 据研究问题的实际情况和相关学者的历史研究经验，13：45本文选用目标函数的倒数作为适应度函数。logistics technology(equipment)2014 no 8万方数据装备大观i equipment showcase 设施设备n个新个体喵(t)le(12 n)。若存在 喵(ok(o，则喵(t)为局部最优解，用 喵(t)代替b(t)。(4)交叉和变异算子设计。由 于叉车编号和初始停放位置已定， 对从父代中随机产生的两个个体的 每四位编码的后两位进行单点或两 点交叉，对一个个体的3个四位编码 的后两位进行随机变异操作，目的 是找到同一辆叉车选择不同搬运路 线的新个体。324方法评价。基于“最短路径 法”的静态调度算法能够有效降低 仓库的搬运成本，节约叉车使用费 用，提高楼层库装卸搬运效率，缩(2)种群优化。种群优化过程整托出库需满足： 短订单响应时间。遗传算法的搜索是在一代种群的所生唑瓦p一可以理解为淘汰不可行解的过程，与静态调度相比，动态调度能根据作业系统的实施情况形成更具有个体中进行的，为了提高算法的非整托出库需满足：有操作性和适用性的调度方案，但运行效率，在一代种群的每个个体壁唑瓦是，动态调度方案的执行必须充分v一产生之后，需要对其做检验和淘汰考虑以下两方面的信息：一是调度处理，用于检验和淘汰个体的约束每个染色体的四位编码过程必须充分考虑并利用好反映系 条件如下：(i，k,j，g)必须满足上述对叉车剩余 统状态的实时信息；二是形成调度pimp2igp=1工作能力的约束。 方案的过程必须在不影响系统运行 分别计算该个体每四位编码的(3)局部搜索。用遗传算法进 的短时间内完成。动态调度算法只pi,p：，值，若为0，说明此编码行迭代时，新一代种群产生之后从 考虑目前就绪队列中任务的特性， 与实际约束条件不符，将此个体淘每个个体出发进行局部搜索，用局并且由此来决定当前的调度任务的 汰，重新产生新个体。部最优解取代原个体在种群中的位 序列，对于将来要到达的任务的特淘汰3个四位编码中照不同的 置。 性却不予考虑。因此，动态调度算 个体，每个个体的34-四位编码设p(t)=p。(t)，p。(t)， ，pi(t)， ， 法的可预测性差并且运行开销较 (i,k,j，g)中的g值必须相同，即目 p。(t)大。对于绝对可预测的系统一般不p(t)表示第t代种群；采用动态调度。 标出库月台需为同一月台。m表示种群中的个体数；p(t)表示第t代种群的第i个个4优化