多类约束下的随机混流U型拆卸线平衡排序问题优化

The Stochastic Mixed-Model U-Shaped Disassembly Line Balancing and Sequencing Optimization Problem with Multiple Constraints

为提高混流产品拆卸效率,针对固定工作站数量约束、位置约束、优先关系约束,考虑任务操作完成时间的不确定性,建立了以最小化循环时间(Cycle Time,CT)和最小化工作站平均空闲时间为目标的混流U型拆卸线平衡排序问题的数学模型。结合混流拆卸线的具体特点,提出了一种改进的并行邻域搜索算法(Improved Parallel Neighborhood Search,IPNS),该算法定义两类不同的邻域结构,采用动态搜索策略,通过独立搜索以及直接交换邻域的方式以最大限度寻找最优解。最后,通过多个算例验证了算法的有效性。

To improve the disassembly efficiency of mixed-model products,a mathematic model was established aiming at minimizing cycle time(CT) and ensuing similar idle time at each workstation for the mixed model U-shaped disassembly line balancing and sequencing problem with stochastic task times under the constraints of fixed number of workstations,positional constraint and precedence relationships.An improved parallel neighborhood search algorithm(IPNS) was proposed according to the model.In IPNS,two different kinds of neighborhood structure were defined,dynamic search strategy was adopted and paralleling was implemented by two different kinds of independent searches.Moreover,direct neighborhood exchanging was introduced to search the optimal solution.Finally,the robustness of proposed algorithm was demonstrated by the better results of benchmark instances.