An Estimation of Distribution Algorithm for Part Cell Formation Problem

An Estimation of Distribution Algorithm for Part Cell Formation Problem

Saber Ibrahim (University of Sfax, Tunisia), Bassem Jarboui (University of Sfax, Tunisia) and Abdelwaheb Rebaï (University of Sfax, Tunisia)
DOI: 10.4018/978-1-4666-1945-6.ch040
OnDemand PDF Download:


The aim of this chapter is to propose a new heuristic for Machine Part Cell Formation problem. The Machine Part Cell Formation problem is the important step in the design of a Cellular Manufacturing system. The objective is to identify part families and machine groups and consequently to form manufacturing cells with respect to minimizing the number of exceptional elements and maximizing the grouping efficacy. The proposed algorithm is based on a hybrid algorithm that combines a Variable Neighborhood Search heuristic with the Estimation of Distribution Algorithm. Computational results are presented and show that this approach is competitive and even outperforms existing solution procedures proposed in the literature.
Chapter Preview

Literature Review

A wide body of publications has appeared on the subject of Group Technology (GT) and Cellular Manufacturing Systems (CMS). The history of approaches that tried to solve this problem began with the classification and coding schemes. Several authors have proposed various ways trying to classify the methods of Cell Formation Problem. It includes descriptive methods, cluster analysis procedures, graph partitioning approaches, mathematical programming approaches, artificial intelligence approaches and other analytical methods.

Burbidge (1963) was the first who developed a descriptive method for identifying part families and machine groups simultaneously. In his work “Production Flow Analysis” (PFA). Burbidge has proposed an evaluative technique inspired from an analysis of the information given in route cards to find a total division into groups, without any need to buy additional machine tools.

Then, researchers applied array based clustering techniques which used a binary matrix A called “Part Machine Incidence Matrix” (PMIM) as input data. Given i and j the indexes of parts and machines respectively, an entry of 1 (aij) means that the part i is executed by the machine j whereas an entry of 0 indicates that it does not. The objective of the array based techniques is to find a block diagonal structure of the initial PMIM by rearranging the order of both rows and columns. Thus, the allocation of machines to cells and the parts to the corresponding families is trivial. McCornick et al. (1972) were the first who applied this type of procedure to the CFP. They developed the Bond Energy Analysis (BEA) which seeks to identify and display natural variable groups and clusters that occur in complex data arrays. Besides, their algorithm seeks to uncover and display the associations and interrelations of these groups with one another. King (1980) developed the Rank Order Clustering (ROC). In ROC algorithm, binary weights are assigned to each row and column of the PMIM. Then, the process tries to gather machines and parts by organizing columns and rows according to a decreasing order of their weights. Chan and Milner (1981) developed the Direct Clustering Algorithm (DCA) in order to form component families and machine groups by restructuring the machine component matrix progressively. A systematic procedure is used instead of relying on intuition in determining what row and column rearrangements are required to achieve the desired result. King & Nakornchai (1982) improved the ROC algorithm by applying a quicker sorting procedure which locates rows or columns having an entry of 1 to the head of the matrix. Chandrasekharan & Rajagopalan (1986a) proposed a modified ROC called MODROC, which takes the formed cells by the ROC algorithm and applies a hierarchical clustering procedure to them. Later, other array based clustering techniques are proposed namely the Occupancy Value method of Khator & Irani (1987), the Cluster Identification Algorithm (CIA) of Kusiak & Chow (1987) and the Hamiltonian Path Heuristic of Askin et al. (1991).

Complete Chapter List

Search this Book: