A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts
A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts
复制标题
DOI：
10.1016/j.cie.2011.03.007
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
Atabak Elmi;M. Solimanpur;Seyda Topaloglu;Afshin Elmi
中科院分区：
文献类型：
--
作者：
Atabak Elmi;M. Solimanpur;Seyda Topaloglu;Afshin Elmi
研究了车间单元制造系统中的零件调度问题，考虑了需要访问不同单元中机器的例外零件和需要以非连续方式多次访问某些机器的可重入零件。首先，整数线性规划（ILP）模型提出的问题，以最大限度地减少完工时间，它考虑到细胞间的移动和非连续的多个加工的零件在一台机器上。由于模型的复杂性，模拟退火（SA）的解决方案的方法来解决这个问题。为了提高搜索算法的效率，应用了基于块概念的邻域结构。随后，ILP模型的效率和建议SA的性能进行了评估，从文献中的一组问题的实例。在Lingo 8.0中对所提出的ILP模型进行编码，并将所提出的SA获得的解与最优值进行比较。计算结果表明，所提出的ILP模型和SA算法是有效的和高效的。
This paper addresses the problem of scheduling parts in job shop cellular manufacturing systems by considering exceptional parts that need to visit machines in different cells and reentrant parts which need to visit some machines more than once in non-consecutive manner. Initially, an integer linear programming (ILP) model is presented for the problem to minimize the makespan, which considers intercellular moves and non-consecutive multiple processing of parts on a machine. Due to the complexity of the model, a simulated annealing (SA) based solution approach is developed to solve the problem. To increase the efficiency of the search algorithm, a neighborhood structure based on the concept of blocks is applied. Subsequently, the efficiency of the ILP model and the performance of the proposed SA are assessed over a set of problem instances taken from the literature. The proposed ILP model was coded in Lingo 8.0 and the solution obtained by the proposed SA was compared to the optimal values. The computational results demonstrate that the proposed ILP model and SA algorithm are effective and efficient for this problem.