非标准HFS-B问题的设备协同调度研究  

Equipment Co-scheduling of Non-basic HFS-B Problem

作　　者：张煜[1] 匡家喜[1] 李文锋[1] 容芷君[2] 

机构地区：[1]武汉理工大学物流工程学院,武汉430063 [2]武汉科技大学汽车与交通工程学院,武汉430081

出　　处：《武汉理工大学学报（交通科学与工程版）》2012年第2期239-242,共4页Journal of Wuhan University of Technology（Transportation Science & Engineering）

基　　金：国家自然科学基金项目(批准号:50805108);湖北省自然科学基金项目(批准号:2009CDB108;2010CDA022);中央高校基本科研业务费专项资金项目(批准号:2010-1a-014)资助

摘　　要：在同贝位边装边卸工艺的集装箱作业环境中,提出了一类非标准的HFS-B问题,即同时存在2种方向互逆的工件流、与紧前紧后机器相关的准备和处理时间.这类来自港口背景的非标准HFS-B问题,主要涉及空间位置决策、任务分配和设备调度等子问题的决策,目标是makespan最小.鉴于HFS-B的NP-hard特性,在分析设备顺序约束和协同关系基础上,基于Fill ratio启发式、表调度理论和设备的状态空间变换,设计了3阶段决策的启发式算法.基于阶段的下界理论和makespan的下界理论,对多个实际的大规模案例进行仿真分析,结果表明:算法的makespan与理论下界的最大偏差不大于7%,具有良好的实用性.Aiming to the container handling system using dual-cycle operation,we present a non-Basic HFS-B problem,which involves bidirectional flows and machine-dependent setup and processing time.The non-Basic HFS-B problem from container handling system needs to solve three sub-problems： space allocation,task assignment and equipment scheduling in order to minimize makespan time of container handling system.Since HFS-B is NP-hard,we design a three-stage heuristics to solve the problem based on these methods： fill ratio heuristics,list scheduling and transform of equipment＇ state space.As for some scenarios,we use stage-Based and makespan-Based lower bound to evaluate the three-stage heuristics developed by us,and the simulating results show the three-stage heuristics is effective because the gap between makespan from our heuristics and lower bound is less than 7%.

关 键 词：混合流水车间 协同 调度 启发式 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置] U691[自动化与计算机技术—控制科学与工程]