An Estimation of Distribution Algorithm for Part Cell Formation Problem

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 (a_ij) 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).