ģ-opt algorithm Step 1: Let S be the initial solution and z its OFV Set S*=S, z*=z, i=1 j=i+1 k=j+1. Otherwise, return S* as the best solution to the user. If i < mn, repeat step 2 otherwise, go to step 3. If j < mn, set j=j+1 otherwise, set i=i+1, j=I+1. If the exchange results in a solution S’ that has an OFV z’< z, set z*=z’ and S*=S’. Step 2: Consider the exchange between the positions of departments i and j in the solution S.Step 1: Let S be the initial solution provided by the user and z its OFV.* Based on the result that the maximum number of arcs in a planar graph with n nodes 3n-6 Repeat Step 5 until all the nodes have been included in the PAG. Step 5: Arbitrarily select one of the faces formed and go to Step 4. Update PAG by placing the corresponding node within the selected face and connect it to nodes of the face.

Select the column for which this sum is the largest. Step 4: For each column of the flow matrix corresponding to a node not present in the PAG, examine the sum of flow entries in the rows corresponding to the nodes of the triangular face selected in step 3. Step 3: Update PAG by connecting the selected node to those in Step 2.

Step 2: From the rows corresponding to the connected nodes in the flow matrix, select the node which is not yet in the PAG and has the largest flows with the connected nodes. Place the corresponding nodes in a new PAG and connect them. Graph Theoretic Method* Step 1: Identify the department-pair in the flow matrix with the maximum flow. The sequence of machines obtained determines the arrangement of machines.Įxample 1 M a c h i n e Lengths (in feet) Step 4: Repeat step 3 until all machines are connected.Otherwise, connect l to j*, remove row j*, column j* from matrix and set j* = l. Step 3:ğind the largest element f’i*k,f’j*l in row i*, j* of matrix If f’i*k*>f’j*l* connect k to i*, remove row i*, column i* from matrix and set i* = k.Step 2:ğind the largest element in and the corresponding i, j.

Step 1: Given the flow matrix, clearance matrix and machine lengths li, compute an adjacency weight matrix where: f’ij = (fij)(dij+0.5(li+lj)).Basic Algorithms and Software for the Layout Problem Chapter 5

Corelap Layout Software