A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts

Elmi A., Solimanpur M., Topaloglu S., Elmi A.

COMPUTERS & INDUSTRIAL ENGINEERING, vol.61, no.1, pp.171-178, 2011 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 61 Issue: 1
  • Publication Date: 2011
  • Doi Number: 10.1016/j.cie.2011.03.007
  • Journal Name: COMPUTERS & INDUSTRIAL ENGINEERING
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.171-178
  • Keywords: Cellular manufacturing, Scheduling, Simulated annealing, Job shop, FLOWLINE MANUFACTURING CELL, SETUP TIMES, METAHEURISTICS, HEURISTICS, MAKESPAN, DESIGN, SYSTEM
  • Gazi University Affiliated: Yes

Abstract

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. (C) 2011 Elsevier Ltd. All rights reserved.