Effective hybrid teaching-learning-based optimization algorithm for balancing two-sided assembly lines with multiple constraints
Effective hybrid teaching-learning-based optimization algorithm for balancing two-sided assembly lines with multiple constraints
复制标题
DOI：
10.3901/cjme.2015.0630.084
复制
发表时间：
2015-08
影响因子：
4.2
通讯作者：
Qiuhua Tang;Zixiang Li;Liping Zhang;C. Floudas;Xiaojun Cao
中科院分区：
文献类型：
--
作者：
Qiuhua Tang;Zixiang Li;Liping Zhang;C. Floudas;Xiaojun Cao
由于双边装配线平衡(TALB)问题是NP难问题，对实际应用中存在的多约束条件的研究较少，尤其是当一个任务涉及多个约束条件时。针对多约束Talb问题，提出了一种有效的混合算法(TALB-MC)。考虑到TALB-MC的离散属性和基于教-学的优化算法的连续属性，在任务排列表示中引入了随机密钥的方法，以弥补两者之间的差距。随后，开发了一种处理多个约束的特殊机制。在该机制中，通过方向检查和调整来保证每个任务的方向约束。通过梳理约束之间的隐含关联，满足分区约束和同步约束。在解码时允许在一定程度上违反位置约束，并在代价函数中对其进行惩罚。最后，在TLBO搜索全局最优解的同时，进一步混合变邻域搜索(VNS)以扩展局部搜索空间。实验结果表明，对于TALB-MC问题，该混合算法在大多数情况下都优于晚验收爬山算法(LAHC)，特别是对于具有多约束的大型问题，表现出较好的探索性和开拓性。本研究将TLBO和VNS相结合，提出了一种求解Talb-MC问题的高效算法。
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 function. 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.