Integer programming and heuristic methods for the cell formation problem with part machine sequencing

Cell formation has received much attention from academicians and practitioners because of its strategic importance to modern manufacturing practices. Existing research on cell formation problems using integer programming (IP) has achieved the target of solving problems that simultaneously optimise machine-cell allocation and partmachine allocation. This thesis presents extensions of an IP model where part-machine assignment and cell formation are addressed simultaneously, and integration of inter-cell movements of parts and machine set-up costs within the objective function is taking place together with the inclusion of an ordered part machine operation sequence. The latter is identified as a neglected parameter for the Cell Formation problem. Due to the nature of the mathematical IP modelling for Cell Formation two main drawbacks can be identified: (a) Cell Formation is considered to be a complex and difficult combinatorial optimisation problem or in other words NP-hard (Non-deterministic Polynomial time hard) problem and (b) because of the deterministic nature of mathematical programming the decision maker is required to specify precisely goals and constraints. The thesis describes a comprehensive study of the cell formation problem where fuzzy set theory is employed for measuring uncertainty. Membership functions are used to express linguistically the uncertainty involved and aggregation operators are employed to transform the fuzzy models into mathematical programming models. The core of the research concentrates on the investigation and development of heuristic and . metaheuristic approaches. A three stage randomly generated heuristic approach for producing an efficient initial solution for the CF together with an iterative heuristic are first developed. Numerous data sets are employed which prove their effectiveness. Moreover, an iterative tabu search algorithm is implemented where the initial solution fed in is the same as that used in the descent heuristic. The first iterative procedure and the tabu search algorithm are compared and the results produced show the superiority of the latter over the former in stability, computational times and clustering results.