动态规划启发式算法禁忌搜索算法作业调度越库作业物流管理

来源：互联网   发布日期：2011-08-28 22:30:06   浏览：6980次  

摘要:本文主要研究两阶段越库物流作业调度问题及其算法设计越库作业Cross docking指在物流的任何中间点仓库或配送中心只实现收发货功能而消除货物存储与订单获取功能的运作模式越库作业的优势体现在不增加库存的同时充分利用运输规模经济，从而降低运输费用和减少运输时间 作者在对越库物流作业的流程、类型及实施条件等进行分析研究后，基于越库作业特点，提出并建立两阶段越库作业的调度模型将货物在越库区的流动过程看作是需要在两台机器上进行顺序加工的任务在第二阶段即装车时，多数车辆都需要装载几种不同货物，若某个订单中的某种货物不能及时分拣装车，就会影响到其它货物的正常送达因此，本文研究的问题是具有前序限制关系的两机器越库作业调度问题，即给定两台机器M1、M2及两个任务集，J1=J11,J12,…,J1n, J2=J21,J22,…,J2m其中J1与J2中的任务分别在机器M1与M2上加工任务集J1中的任务J1i在机器M1上加工时间记作p1i任务集J2中的任务J2j在机器M2上加工时间为p2jJ2中的每个任务J2j，均存在任务集J1的一个子集Sj，使得J2j必须等待所对应的Sj中所有任务在M1上加工结束后，J2j才能在M2上开始加工其目标函数为最小化加权完工时间和用三参数表示法，该问题简记为F2︱CD︱∑wjCj，其中，wj为任务J2j的权重，Cj为任务J2j在M2上的完工时间 考虑越库作业中缓存区容量限制情况，本文针对如下二类基本问题进行研究无限缓存区越库作业调度问题F2︱CD︱∑wjCj有限缓存区越库作业调度问题F2︱CD，B︱∑wjCj，其中B代表缓存约束 1对F2︱CD︱∑wjCj问题，在证明该问题为NP-难的基础上，通过研究该问题解的特性，提出计算复杂性为Onm2m的动态规划算法同时，通过数值实验，表明该算法至少可以有效地求解25个任务规模的越库作业调度问题 2考虑到实际作业情况，重点研究F2︱CD，B︱∑wjCj问题通过对该问题的特性进行深入的研究后，提出有限缓存区越库作业在制品概念，并对其性质进行分析同时，对缓存区容量受限的情况分析后，提出死锁性质，并针对死锁特性展开研究，提出死锁度的定义针对有限缓存区越库作业调度问题的特点，提出求解该问题的启发式算法及其改进算法并以启发式算法作为初始解产生方案，提出求解该问题的禁忌搜索算法同时，针对所研究问题的特点，及禁忌搜索算法的不足，采用并行邻域搜索策略进一步，对禁忌搜索算法中的关键参数，如迭代次数、候选解个数、禁忌表长，采用数值实验分析比较，确定较优的参数值的选取，提高算法性能 最后，通过数值实验对有限缓存区越库作业的缓存区容量与货物流通量之间的关系、在制品库存水平与问题规模及订单规模之间的关系展开研究，为越库物流中心设计与越库物流调度管理提供一定的决策理论依据标题:动态规划启发式算法禁忌搜索算法作业调度越库作业物流管理专业:管理科学与工程学位:硕士单位:上海交通大学@关键词:动态规划　启发式算法　禁忌搜索算法　作业调度　越库作业　物流管理　论文时间:2007分类:F253.1 导师:陈峰 语种:中文文摘URL:

赞助本站