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

在同贝位边装边卸工艺的集装箱作业环境中,提出了一类非标准的HFS-B问题,即同时存在2种方向互逆的工件流、与紧前紧后机器相关的准备和处理时间.这类来自港口背景的非标准HFS-B问题,主要涉及空间位置决策、任务分配和设备调度等子问题的决策,目标是makespan最小.鉴于HFS-B的NP-hard特性,在分析设备顺序约束和协同关系基础上,基于Fill ratio启发式、表调度理论和设备的状态空间变换,设计了3阶段决策的启发式算法.基于阶段的下界理论和makespan的下界理论,对多个实际的大规模案例进行仿真分析,结果表明:算法的makespan与理论下界的最大偏差不大于7%,具有良好的实用性.

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

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%.