Greedy Algorithm for Aggregate Planning

Consider the aggregate planning problem given in Example 2.14, where no shortages are allowed and weekly demands must be satisfied at all times. Solve the transportation problem using the greedy algorithm. 

The transportation formulation given in Table 2.14 is reproduced in Table 2.16, where the warehouses represent the regular (RT)/overtime (OT) production each week and the markets are the weekly demands. 

Applying the greedy algorithm to Example 2.15 (Table 2.16), we get the following steps  

Step 1 Begin with week 1. The lowest cost cell is X. Assign X a value as large as possible consistent with the supply at warehouse 1 and demand of market 1. Thus Xu = max (700, 300) = 300. This means that week Ts demand is satisfied and the remaining supply in warehouse 1 is now 400. Hence, we set the values of the remaining cells under column 1 to zero, namely X,i = 0 for i = 2,6. 

Step 3 Go to week 3. Even though the lowest cost cell in colmnn 3 is X23, it has already been assigned a value zero in step 2 and hence cannot be used to meet week 3 s demand. The next lowest cost cell that has not been assigned is X43. Set X43 = min (700, 900) = 700. Warehouse 3 s capacity is exhausted and X44 is set to zero. The remaining demand for week 3 is 900 - 700 = 200. The next lowest cost cell in column 3 is X13. Set X13 = min (400, 200) = 200. Week 3 s demand is reduced to zero and the capacity of warehouse 1 is reduced to 200. 

---