In Example 5.1 , a solution to the single-row layout problem was generated using MST. Apply
2-opt algorithm to improve the solution (if possible). What is the new OFV?

 

Transcribed Image Text:

Example 5.1 Using the following flow data for six machines and their lengths in Figure 5.1, develop a layout using the MST algorithm. Assume that the clearance between each pair of machines must be at least 2 meters. Solution Step 1: First, compute the adjacency weight matrix [C] as in Figure 5.2, where -d, +0.5+1)). Step 2: Find the largest element and connect machines 1 and 6. Set ---- Step 3: Select the largest elements, and, in rows 1 and 6, respectively. Because f select arbitrarily. Connect 2 to 1 and remove row 1 and column 1 from matrix II. Set --- Step 4: Because all machines are not connected yet, repeat step 3. Repeating the aforementioned steps, we see that machine 4 is connected to machine 6, machine 3 is connected to machine 4, and machine 5 is connected to machine 2 in subsequent steps. A layout generated for this sequence is shown in Figure 5.3. Notice that the clearance between machines Machine 1 2 3 4 5 6 Machine lengths (meter) 12 6 20 0 20 2 12 5 5 5 0 10 3 3 5 - 10 4 2 16 4 6- 5 10 5 0 5 4 2 2 12 20 6 10 200 12 6 FIGURE 5.1 Flow and length data for six machines. Machine 2 204 2 3 4 204 60 132 0 9 3 60 25 75 85 559 C 4 132 85 200 10 6 340 60 0 200 60 90 1 5 0 60 60 34 6 A 340 0 30 204 FIGURE 5.2 Adjacency weight matrix. Basic Algorithms and Software for the Layout Problem 34 204 2 2 1 6 + FIGURE 5.3 Layout generated using the sequence produced by MST. 72 107 Example 5.1 Using the following flow data for six machines and their lengths in Figure 5.1, develop a layout using the MST algorithm. Assume that the clearance between each pair of machines must be at least 2 meters. Solution Step 1: First, compute the adjacency weight matrix [C] as in Figure 5.2, where -d, +0.5+1)). Step 2: Find the largest element and connect machines 1 and 6. Set ---- Step 3: Select the largest elements, and, in rows 1 and 6, respectively. Because f select arbitrarily. Connect 2 to 1 and remove row 1 and column 1 from matrix II. Set --- Step 4: Because all machines are not connected yet, repeat step 3. Repeating the aforementioned steps, we see that machine 4 is connected to machine 6, machine 3 is connected to machine 4, and machine 5 is connected to machine 2 in subsequent steps. A layout generated for this sequence is shown in Figure 5.3. Notice that the clearance between machines Machine 1 2 3 4 5 6 Machine lengths (meter) 12 6 20 0 20 2 12 5 5 5 0 10 3 3 5 - 10 4 2 16 4 6- 5 10 5 0 5 4 2 2 12 20 6 10 200 12 6 FIGURE 5.1 Flow and length data for six machines. Machine 2 204 2 3 4 204 60 132 0 9 3 60 25 75 85 559 C 4 132 85 200 10 6 340 60 0 200 60 90 1 5 0 60 60 34 6 A 340 0 30 204 FIGURE 5.2 Adjacency weight matrix. Basic Algorithms and Software for the Layout Problem 34 204 2 2 1 6 + FIGURE 5.3 Layout generated using the sequence produced by MST. 72 107