求解随机型双边装配线平衡问题的混合回溯搜索优化算法

针对现实生产中普遍存在的操作时间为随机的双边装配线平衡问题,提出一种混合回溯搜索优化算法。该算法将变邻域搜索算法的局部搜索能力融入到回溯搜索优化算法的全局搜索中,从而实现广度搜索和深度搜索的平衡。运用基于随机键的编码将用于求解连续问题的回溯搜索优化算法应用于离散组合优化问题,同时提出一种基于均衡双边负载的边选择策略和减少工位空闲时间的任务选择策略的解码方法,并将该方法同另外4种解码方法进行对比,以验证其优越性。标杆算例测试表明,所提出的算法具有可行性和有效性。

Solving stochastic two-sided assembly line balancing problem via hybrid backtracking search optimization algorithm

In this paper, a hybrid backtracking search optimization algorithm (HBSA) is proposed to solve the widespread stochastic two-sided assembly line balancing problem. The local search ability of the variable neighborhood search (VNS) is integrated into the global search ability of backtracking search optimization algorithm (BSA) so as to make the balancing between diversification and intensification. The random-key based encoding scheme is employed for successfully applying BSA which is originally proposed for continuous problem to discrete combinatorial optimization problem. A decoding scheme which is based on side and task selection strategies is used to balance the workload between workstations and reduce idle time related to sequence-dependence. And the performance of the proposed decoding scheme is demonstrated by comparison with four other decoding schemes which are based on different heuristic task selection strategies. The corresponding benchmark experiment results demonstrate that the proposed algorithm can solve the problem effectively.