Due to the NP-hardness of the two-sided assembly line balancing （TALB） problem, multiple constraints existing in real applications are less studied, especially when one task is involved with several constraints. In ...Due to the NP-hardness of the two-sided assembly line balancing （TALB） problem, multiple constraints existing in real applications are less studied, especially when one task is involved with several constraints. In this paper, an effective hybrid algorithm is proposed to address the TALB problem with multiple constraints （TALB-MC）. Considering the discrete attribute of TALB-MC and the continuous attribute of the standard teaching-learning-based optimization （TLBO） algorithm, the random-keys method is hired in task permutation representation, for the purpose of bridging the gap between them. Subsequently, a special mechanism for handling multiple constraints is developed. In the mechanism, the directions constraint of each task is ensured by the direction check and adjustment. The zoning constraints and the synchronism constraints are satisfied by teasing out the hidden correlations among constraints. The positional constraint is allowed to be violated to some extent in decoding and punished in cost fimction. Finally, with the TLBO seeking for the global optimum, the variable neighborhood search （VNS） is further hybridized to extend the local search space. The experimental results show that the proposed hybrid algorithm outperforms the late acceptance hill-climbing algorithm （LAHC） for TALB-MC in most cases, especially for large-size problems with multiple constraints, and demonstrates well balance between the exploration and the exploitation. This research proposes an effective and efficient algorithm for solving TALB-MC problem by hybridizing the TLBO and VNS.展开更多
文摘货位分配(storage location assignment problem,SLAP),即在存储区域为物料分配货位的过程。当仓库布局、拣货路径、订单组合等其他因素确定时,货位分配策略对订单拣货效率有很大影响。本文研究实际生产型仓库中的关联物料区位分配问题。生产中使用的相对稳定的BOM(bill of material)使得仓库中的物料具有稳定的相关性,因此,本文考虑将具有需求关联的物料存储在同一区域,以尽可能地减少在拣选物料时所需要的区域访问次数。此外,该仓库还存在两个重要特征,即存在两类不同尺寸货架构成的两类不同容量的区域及采用严格的重物下置原则。本文建立了以最小化区域访问次数为目标的数学规划模型,给出了求解该问题的一种聚类启发式方法与自适应大邻域搜索算法(adaptive large neighborhood search,ALNS),并设计了能够反映物料关联特征的小规模和大规模算例用于测试两种算法的性能。将两个算法结果与随机策略、CPLEX求解结果对比,结果显示聚类启发式方法与ALNS在大规模算例中表现明显优于随机策略和CPLEX的求解结果。
基金Supported by National Natural Science Foundation of China(Grant Nos.51275366,50875190,51305311)Specialized Research Fund for the Doctoral Program of Higher Education of China(Grant No.20134219110002)
文摘Due to the NP-hardness of the two-sided assembly line balancing （TALB） problem, multiple constraints existing in real applications are less studied, especially when one task is involved with several constraints. In this paper, an effective hybrid algorithm is proposed to address the TALB problem with multiple constraints （TALB-MC）. Considering the discrete attribute of TALB-MC and the continuous attribute of the standard teaching-learning-based optimization （TLBO） algorithm, the random-keys method is hired in task permutation representation, for the purpose of bridging the gap between them. Subsequently, a special mechanism for handling multiple constraints is developed. In the mechanism, the directions constraint of each task is ensured by the direction check and adjustment. The zoning constraints and the synchronism constraints are satisfied by teasing out the hidden correlations among constraints. The positional constraint is allowed to be violated to some extent in decoding and punished in cost fimction. Finally, with the TLBO seeking for the global optimum, the variable neighborhood search （VNS） is further hybridized to extend the local search space. The experimental results show that the proposed hybrid algorithm outperforms the late acceptance hill-climbing algorithm （LAHC） for TALB-MC in most cases, especially for large-size problems with multiple constraints, and demonstrates well balance between the exploration and the exploitation. This research proposes an effective and efficient algorithm for solving TALB-MC problem by hybridizing the TLBO and VNS.
