Skip to main content

2013 | Buch

Cell Formation in Industrial Engineering

Theory, Algorithms and Experiments

verfasst von: Boris Goldengorin, Dmitry Krushinsky, Panos M. Pardalos

Verlag: Springer New York

Buchreihe : Springer Optimization and Its Applications

insite
SUCHEN

Über dieses Buch

This book focuses on a development of optimal, flexible, and efficient models and algorithms for cell formation in group technology. Its main aim is to provide a reliable tool that can be used by managers and engineers to design manufacturing cells based on their own preferences and constraints imposed by a particular manufacturing system. This tool could potentially lower production costs by minimizing other costs in a number of areas, thereby increasing profit in a manufacturing system.

In the volume, the cell formation problem is considered in a systematic and formalized way, and several models are proposed, both heuristic and exact. The models are based on general clustering problems, and are flexible enough to allow for various objectives and constraints. The authors also provide results of numerical experiments involving both artificial data from academic papers in the field and real manufacturing data to certify the appropriateness of the models proposed.

The book was intended to suit the broadest possible audience, and thus all algorithmic details are given in a detailed description with multiple numerical examples and informal explanations are provided for the theoretical results. In addition to managers and industrial engineers, this book is intended for academic researchers and students. It will also be attractive to many theoreticians, since it addresses many open problems in computer science and bioinformatics.

Inhaltsverzeichnis

Frontmatter
Chapter 1. The Problem of Cell Formation: Ideas and Their Applications
Abstract
This chapter provides a general overview of the cell formation problem, including the origins of the problem, a discussion on the relevance of a cellular layout together with its advantages and drawbacks, and an overview of the solution approaches. The notions of dissimilarity and performance measures are also considered in this chapter. Furthermore, the outline of the book is provided at the end of this chapter.
Boris Goldengorin, Dmitry Krushinsky, Panos M. Pardalos
Chapter 2. The p-Median Problem
Abstract
This chapter focuses on the p-median problem (PMP) and its properties. We consider a pseudo-Boolean formulation of the PMP, demonstrate its advantages and derive the most compact MILP formulation for the PMP within the class of mixed-Boolean linear programming formulations. Further, we develop two applications of the pseudo-Boolean approach: a construction of PMP instances that are expected to be complex for any solution algorithm and a definition of an equivalence relation for PMP instances. By equivalence we mean that solving one instance gives a solution for all the instances from its equivalence class. The proposed equivalence relation can be extended to any other problem modelled via the PMP, for example, the cell formation problem.
Boris Goldengorin, Dmitry Krushinsky, Panos M. Pardalos
Chapter 3. Application of the PMP to Cell Formation in Group Technology
Abstract
This chapter focuses on the p-median problem based approach to cell formation. A PMP-based model is described in detail and its performance is analysed theoretically and experimentally, both in terms of the solution quality and running times.
Boris Goldengorin, Dmitry Krushinsky, Panos M. Pardalos
Chapter 4. The Minimum Multicut Problem and an Exact Model for Cell Formation
Abstract
In this chapter we consider an exact model for cell formation, i.e. the model that directly minimises the amount of intercell movement. We show that the exact model is equivalent to the minimum multicut problem defined on an appropriate graph. Two MILP formulations are proposed and their performance is analysed using instances from the literature and an industrial case. Several types of realistic constraints are also considered and introduced into the model.
Boris Goldengorin, Dmitry Krushinsky, Panos M. Pardalos
Chapter 5. Multiobjective Nature of Cell Formation
Abstract
This chapter discusses the appropriateness of the standard objective of minimising intercell movement, and considers possible alternative objectives for cell formation, including maximisation of intracell movement, minimisation of cross-training costs and minimisation of set-up times. The viable ways of combining several objectives in one formulation are briefly discussed.
Boris Goldengorin, Dmitry Krushinsky, Panos M. Pardalos
Chapter 6. Pattern-Based Heuristic for the Cell Formation Problem in Group Technology
Abstract
In this chapter we introduce a new pattern-based approach within the Linear Assignment Model with the purpose to design heuristics for a combinatorial optimization problem (COP). We assume that the COP has an additive (separable) objective function and the structure of a feasible (optimal) solution to the COP is predefined by a collection of cells (positions) in an input file. We define a pattern as a collection of positions in an instance problem represented by its input file (matrix). We illustrate the notion of pattern by means of some well known problems in combinatorial optimization, including the Linear Ordering Problem, the Cell Formation Problem, just to mention a few. The CFP is defined on a Boolean input matrix, the rows of which represent machines and columns–parts. The CFP consists in finding three optimal objects: a block-diagonal collection of rectangles, a rows (machines) permutation, and a columns (parts) permutation so that the grouping efficacy is maximized. The suggested heuristic combines two procedures: the pattern-based procedure to build an initial solution and an improvement procedure to obtain a final solution with high grouping efficacy for the CFP. Our computational experiments with the most popular set of 35 benchmark instances show that our heuristic outperforms all well known heuristics and returns either the best known or improved solutions to the CFP.
Boris Goldengorin, Dmitry Krushinsky, Panos M. Pardalos
Chapter 7. Two Models and Algorithms for Bi-Criterion Cell Formation
Abstract
In this chapter we propose a bi-criterion branch-and-bound algorithm for the cell formation problem. We demonstrate the performance of the algorithm by solving problems from the literature and comparing the results with complete enumeration as well as with the results of metaheuristic algorithms from the literature.
Boris Goldengorin, Dmitry Krushinsky, Panos M. Pardalos
Chapter 8. Summary and Conclusions
Abstract
The book is focused on relevant and effective mathematical models for solving the cell formation (CF) problem, i.e., grouping machines into manufacturing cells such that the principles of group technology are implemented. Despite its long history and hundreds of published papers, very few attempts of solving the problem to optimality are known. At the same time, in today’s highly competitive environment, any noticeable improvement in performance is critical to the company’s survival.
Boris Goldengorin, Dmitry Krushinsky, Panos M. Pardalos
Backmatter
Metadaten
Titel
Cell Formation in Industrial Engineering
verfasst von
Boris Goldengorin
Dmitry Krushinsky
Panos M. Pardalos
Copyright-Jahr
2013
Verlag
Springer New York
Electronic ISBN
978-1-4614-8002-0
Print ISBN
978-1-4614-8001-3
DOI
https://doi.org/10.1007/978-1-4614-8002-0