Scheduling in a cellular manufacturing system: a simulated annealing approach

The problem of scheduling in a cellular manufacturing system is considered with the objective of minimizing the sum of completion times (or total flow time) of jobs. A correct formulation of recursive equation for the flowline-based cellular manufacturing system is first proposed. Subsequently a heuristic is developed to obtain a sequence that minimizes total flow time in a flowline cell. The proposed heuristic makes use of the simulated annealing technique and is developed in two stages. A good initial heuristic seed sequence obtained in the first stage is improved upon by a proposed new variant of the simulated annealing technique wherein three different perturbation schemes have been experimented with. One of the perturbation schemes is newly proposed in this paper and is called the Adjacent interchange scheme. The proposed simulated annealing algorithm has been compared with the existing heuristics for minimizing flow time and has shown consistently good and superior solutions.