22-Mec-B4 Integrated Manufacturing Systems · December 2016

Question 5 of 6: Group Technology Cell Formation from a Machine-Part Matrix

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Paper format. 07-Mec-B4 — Integrated Manufacturing Systems, National Exams December 2016. Three hours, open book, any non-communicating calculator permitted. Six questions are printed; any five constitute a complete paper and all questions are of equal value, so each is worth 20 marks on a five-question basis. Only the first five questions appearing in the answer book are marked. All six are solved here.

Reference texts. The paper draws on the operations and facilities side of manufacturing engineering rather than on process metal cutting, so the useful shelf is:

E. S. Buffa and R. K. Sarin, Modern Production / Operations Management, 8th ed. — facility layout and operation sequence analysis, materials handling, inventory systems, production planning and control, dispatching.
M. P. Groover, Automation, Production Systems, and Computer-Integrated Manufacturing, 5th ed. — group technology, cellular manufacturing and rank order clustering (Ch. 15).
R. B. Chase and F. R. Jacobs, Operations and Supply Chain Management, 16th ed. — forecasting model selection, inventory control, statistical quality control.
S. Nahmias and T. L. Olsen, Production and Operations Analysis, 7th ed. — economic order quantity, order intervals, safety stock.
D. C. Montgomery, Introduction to Statistical Quality Control, 8th ed. — inspection strategy, quality information systems, process capability.

Canadian practice is assumed throughout: handling and lifting design is governed by the applicable provincial occupational health and safety regulation and by CSA standards (for example CSA B335 for lift trucks), and quality records are kept to satisfy ISO 9001 as adopted by CSA.

Question 5: Group Technology Cell Formation from a Machine-Part Matrix (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A four-by-four machine-part incidence matrix, one machine of each type, and a requirement for two cells.

Machine-part incidence matrix as printed
	M1	M2	M3	M4
p1	1	0	1	0
p2	0	1	1	1
p3	0	1	0	1
p4	1	0	1	0

Find. A two-cell group technology layout obtained by reordering rows and columns, the exceptional elements it leaves, a measure of how good the grouping is, and a general algorithm that produces such a grouping from any incidence matrix.

Approach. Apply King's rank order clustering, which reads each row and each column of the binary matrix as a binary number and sorts alternately on rows and columns until the order stops changing; the converged matrix is block-diagonal to the extent that the data permit, and the blocks are the cells.

Read the part routings off the matrix. Row by row, p1 requires M1 and M3; p2 requires M2, M3 and M4; p3 requires M2 and M4; and p4 requires M1 and M3. There are nine ones in all. Two observations are already available without any algorithm: p1 and p4 have identical routings, and M3 is wanted by three of the four parts, which makes it a candidate bottleneck machine.
Give each row a binary weight and sort the rows. Reading the columns from left to right as the bits of a binary number, with M1 as the most significant, the row values are $p_{1}=1010_{2}=10$, $p_{2}=0111_{2}=7$, $p_{3}=0101_{2}=5$ and $p_{4}=1010_{2}=10$. Sorting in descending order puts the rows in the sequence p1, p4, p2, p3.
Give each column a binary weight and sort the columns. Now read down each column with the new row order, the top row being the most significant bit, so the weights are 8 for p1, 4 for p4, 2 for p2 and 1 for p3. That gives $M_{1}=8+4=12$, $M_{2}=2+1=3$, $M_{3}=8+4+2=14$ and $M_{4}=2+1=3$. Sorting in descending order puts the columns in the sequence M3, M1, M2, M4.
Iterate until the order stops changing. Recomputing the row values against the new column order gives $p_{1}=p_{4}=1100_{2}=12$, $p_{2}=1011_{2}=11$ and $p_{3}=0011_{2}=3$, which reproduces the row order p1, p4, p2, p3; recomputing the column values reproduces M3, M1, M2, M4. Both orders are stable, so the algorithm has converged after one full pass.
Read the cells off the converged matrix. In the rearranged matrix shown below, two diagonal blocks stand out: machines M1 and M3 together serve parts p1 and p4, and machines M2 and M4 together serve parts p2 and p3. The recommended layout is therefore $\boxed{\text{Cell 1}=\{M1,\,M3\}\ \text{making}\ \{p1,\,p4\};\ \text{Cell 2}=\{M2,\,M4\}\ \text{making}\ \{p2,\,p3\}}$, with each cell laid out as a small flow line in the order the parts visit the machines.
Identify what does not fit. One entry lies outside the two blocks: p2 belongs to Cell 2 by the bulk of its routing, but also needs M3, which sits in Cell 1. That single 1 is the exceptional element of the grouping, and because it is the only one, the solution is a very good one. There are no voids at all, meaning neither block contains a zero, so no machine in a cell is idle with respect to that cell's own parts.
Measure the quality of the grouping. The standard measure is the grouping efficacy, $$\tau=\frac{e-e_{0}}{e+e_{v}}=\frac{9-1}{9+0}$$ where $e$ is the number of ones, $e_{0}$ the number outside the blocks and $e_{v}$ the number of zeros inside them. This gives $\boxed{\tau=8/9=0.889}$. Exhaustive enumeration of every way of splitting four machines and four parts into two cells of two confirms that no other two-cell partition scores higher, so the rank order clustering result is in fact optimal here.
Deal with the exceptional element. Because there is only one machine of each type, M3 cannot simply be duplicated into Cell 2, so three practical options remain. The first is to accept an intercell move: p2 is made in Cell 2 and travels to Cell 1 for its M3 operation, which is acceptable if p2 is a low-volume part. The second is to treat M3 as a shared bottleneck machine sited between the two cells rather than inside either, which is the usual physical resolution and costs only a slightly longer path for p1 and p4. The third is to re-engineer the process so that p2's M3 operation is performed on a machine already in Cell 2, which removes the problem permanently but costs process development. If a second M3 were ever bought, duplicating it would make the grouping perfect, raising the efficacy to 1.000.
Set out the general algorithm. Rank order clustering generalises directly and is the answer to the last part of the question. Given any binary machine-part matrix: (i) compute for each row the binary number formed by its entries and sort the rows in decreasing order; (ii) compute for each column the binary number formed by its entries under the new row order and sort the columns in decreasing order; (iii) repeat until neither order changes, which is guaranteed to happen because each sort cannot decrease the matrix's binary value and the value is bounded; (iv) read the diagonal blocks as cells and classify the remaining ones as exceptional elements. The method needs no parameters and runs in a few passes even on industrial matrices of hundreds of rows.
Note the alternatives and their trade-offs. Rank order clustering is sensitive to the order in which ties are broken and gives no control over cell size, so three families of alternative are worth knowing. Direct clustering starts from the row and column sums and moves the densest rows and columns to the top left, which converges faster and is easier to do by hand. Similarity-coefficient methods compute a coefficient between every pair of machines, most commonly Jaccard's $s_{ij}=n_{ij}/(n_{i}+n_{j}-n_{ij})$ where $n_{ij}$ counts the parts visiting both machines, and then apply hierarchical clustering, which has the advantage that the dendrogram can be cut wherever the desired number of cells is obtained. Mathematical programming formulations, such as the p-median model or a binary program minimising intercell moves subject to cell-size limits, give a provably optimal grouping and can carry real constraints such as capacity, machine cost and permitted duplication, at the price of much heavier computation. In industrial practice the matrix methods are used to propose a grouping and the programming methods to refine it.

Matrix after rank order clustering, rows p1, p4, p2, p3 and columns M3, M1, M2, M4. The two cells appear as diagonal blocks; the shaded entry is the single exceptional element.
	M3	M1	M2	M4
p1	1	1	0	0
p4	1	1	0	0
p2	1	0	1	1
p3	0	0	1	1

The physical layout that follows is two compact cells. Cell 1 holds M1 and M3 side by side and runs the family {p1, p4}, whose members have identical routings and can therefore be scheduled as a single group with one set-up. Cell 2 holds M2 and M4 and runs the family {p2, p3}. M3 is positioned on the boundary between the cells so that p2 can reach it with a short move rather than a trip across the shop, which is the standard treatment of a bottleneck machine when duplication is not affordable.

Final results — Question 5
Quantity	Value
Converged row order	p1, p4, p2, p3
Converged column order	M3, M1, M2, M4
Cell 1	Machines M1, M3 — parts p1, p4
Cell 2	Machines M2, M4 — parts p2, p3
Exceptional elements	1 (part p2 requires M3 in Cell 1)
Voids inside the blocks	0
Grouping efficacy	0.889 (proved optimal for two cells by enumeration)
General algorithms	Rank order clustering; direct clustering; similarity-coefficient hierarchical clustering; p-median or binary programming

Topic. Group technology, cell formation from a machine-part incidence matrix, and the algorithms that produce it.

Key relations. Rank order clustering by alternate binary sorting of rows and columns; grouping efficacy $\tau=(e-e_{0})/(e+e_{v})$; Jaccard similarity $s_{ij}=n_{ij}/(n_{i}+n_{j}-n_{ij})$ for machine-pair clustering.

Why this works. Group technology exploits the fact that a job shop making many part numbers is usually making a small number of part families, and that families share machines. Sorting rows by their binary value pushes parts with similar routings together; sorting columns then pushes machines used by those parts together; alternating the two drives the ones toward the leading diagonal, and the procedure terminates because each sort weakly increases the binary value of the whole matrix, which is bounded above. What emerges is a partition into cells, each of which behaves like a small flow line: set-ups fall because the parts in a family are similar, material moves shrink because the machines are adjacent, and throughput time and work in process fall with them.

Common pitfall. The first is to stop at the first rearrangement rather than iterating to convergence, which frequently leaves an avoidable exceptional element. The second is to report the cells and ignore the exceptional element entirely; the whole practical difficulty of cellular manufacturing lies in what to do about the parts and machines that do not fit, and an answer that does not address the bottleneck machine has not answered the question.

Source. Groover, Automation, Production Systems, and Computer-Integrated Manufacturing, 5th ed., Ch. 15 (group technology and cellular manufacturing; rank order clustering, part families, composite part method); Buffa and Sarin, Modern Production / Operations Management, 8th ed., layout chapter on group layout.

← Question 4 Next: Question 6 →