越库作业调度模型与算法研究  

Operational scheduling model and algorithms of cross-docking

作　　者：毛道晓[1] 徐克林[1] 杨璐琦[1] 

机构地区：[1]同济大学机械与能源工程学院,上海201804

出　　处：《广西大学学报（自然科学版）》2013年第5期1079-1085,共7页Journal of Guangxi University（Natural Science Edition）

基　　金：国家自然科学基金资助项目(71071115)

摘　　要：针对暂存区容量有限的越库中心的作业调度问题,以暂存成本、额外搬运成本和换车成本总和最小化为目标,建立数学模型。构建分支定界算法对问题进行精确求解;结合贪婪算法和遗传算法构建混合启发式算法对问题进行近似求解。大、小规模情形下的数值实验结果表明:分支定界算法可以有效求得小规模问题的精确解,但随着问题规模的增大,难以在较短时间内求得精确解;混合启发式算法在小规模情形下与分支定界算法的求解误差最小为0,最大为0.58%;大规模情形下,在给定1 800 s内,混合启发式算法的求解质量均优于分支定界算法,两者差距最大为7.16%。这表明所构建的混合启发式算法是有效的。To study the operational scheduling problem of a cross-docking center with finite tempora- ry storage, a mathematical model was presented with the objective to minimize temporary storage cost, additional handling cost and truck replacement cost. Both branch and bound algorithm （B＆B） and a hybrid meta-heuristic of greedy algorithm and genetic algorithm were proposed to solve the problem accurately or approximately. Numerical experiments under small and big scale situations show that B＆B can obtain optimal solution for small scale problems while it is difficult to obtain opti- mal solution in a short time for large ones; the minimum and the maximum of result error between hybrid meta-heuristic and B＆B are 0 and 0. 58% respectively under small scale situation, while un- der big scale situation the calculating results of hybrid meta-heuristic is better than that of B＆B with- in the given 1 800 seconds and the biggest gap between them run up to 7. 16%. This indicates that the proposed hybrid meta-heuristic is effective.

关 键 词：越库 调度 分支定界算法 混合启发式算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] F253[自动化与计算机技术—计算机科学与技术]