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.展开更多
Two-sided assembly line is usually used for the assembly of large products such as cars,buses,and trucks.With the development of technical progress,the assembly line needs to be reconfigured and the cycle time of the ...Two-sided assembly line is usually used for the assembly of large products such as cars,buses,and trucks.With the development of technical progress,the assembly line needs to be reconfigured and the cycle time of the line should be optimized to satisfy the new assembly process.Two-sided assembly line balancing with the objective of minimizing the cycle time is called TALBP-2.This paper proposes an improved artificial bee colony(IABC)algorithm with the MaxTF heuristic rule.In the heuristic initialization process,the MaxTF rule defines a new task's priority weight.On the basis of priority weight,the assignment of tasks is reasonable and the quality of an initial solution is high.In the IABC algorithm,two neighborhood strategies are embedded to balance the exploitation and exploration abilities of the algorithm.The employed bees and onlooker bees produce neighboring solutions in different promising regions to accelerate the convergence rate.Furthermore,a well-designed random strategy of scout bees is developed to escape local optima.The experimental results demonstrate that the proposed MaxTF rule performs better than other heuristic rules,as it can find the best solution for all the 10 test cases.A comparison of the IABC algorithm and other algorithms proves the effectiveness of the proposed IABC algorithm.The results also denote that the IABC algorithm is efficient and stable in minimizing the cycle time for the TALBP-2,and it can find 20 new best solutions among 25 large-sized problem cases.展开更多
基金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.
文摘Two-sided assembly line is usually used for the assembly of large products such as cars,buses,and trucks.With the development of technical progress,the assembly line needs to be reconfigured and the cycle time of the line should be optimized to satisfy the new assembly process.Two-sided assembly line balancing with the objective of minimizing the cycle time is called TALBP-2.This paper proposes an improved artificial bee colony(IABC)algorithm with the MaxTF heuristic rule.In the heuristic initialization process,the MaxTF rule defines a new task's priority weight.On the basis of priority weight,the assignment of tasks is reasonable and the quality of an initial solution is high.In the IABC algorithm,two neighborhood strategies are embedded to balance the exploitation and exploration abilities of the algorithm.The employed bees and onlooker bees produce neighboring solutions in different promising regions to accelerate the convergence rate.Furthermore,a well-designed random strategy of scout bees is developed to escape local optima.The experimental results demonstrate that the proposed MaxTF rule performs better than other heuristic rules,as it can find the best solution for all the 10 test cases.A comparison of the IABC algorithm and other algorithms proves the effectiveness of the proposed IABC algorithm.The results also denote that the IABC algorithm is efficient and stable in minimizing the cycle time for the TALBP-2,and it can find 20 new best solutions among 25 large-sized problem cases.
