Inventory Application Problem

The Inventory Application Problem (IAP) in the steel industry is to find a matching of orders and material (steel slabs and/or coils). In the steel industry, a lot of surplus inventory is produced for various reasons. Examples include when orders are cancelled after materials have been produced, or when some of the finished products are below the quality levels required for the orders. To make use of surplus inventory, daily production planning is typically divided into two main steps. In the first step, the plan tries to satisfy orders as far as possible with existing materials (typically surplus inventory). Then, in the second step, the plan designs production units for the manufacture of the remaining parts of the orders. The IAP is the problem for the first step of the order fulfillment process (see figure below). In the IAP, it is often the case that the materials are not actually surplus inventory. For example, the materials may include work-in-process goods. Sometimes the tentative plan includes non-optimal allocations, such as allocating higher quality materials to cover an order for lower quality goods, so it may also be better to release the current allocations and to reallocate products while solving the IAP.

The left side of the following figure shows an instance of an IAP. The materials are given weights and the orders are given their required quantities. For example, in the figure below, the material with ID 1 has a weight of 28 units and the order A requires 22 units. The material which is connected with orders in the left side of the following figure can be allocated to those orders. For example, the material with ID 3 could not be allocated to order B, but it could be allocated to orders A, C, D, or E. When we allocate a batch of materials to an order, the materials must be cut into the pieces of sizes within the range specified by the order (a unit weight constraint). For example, in the figure below, the materials which are allocated to order B must be cut into sizes in the range from 6 to 8. This constraint makes the IAP difficult to solve. The right side of the figure shows an example of allocations. The figure shows that the material with ID 1 is cut into a size 6 piece and two size 11 pieces, and the figure shows that the size 6 piece is allocated to the order B and the two size 11 pieces are allocated to the order A, which satisfies the unit weight constraints. The objective of the IAP is to find the best allocations of orders and materials with respect to an objective function that takes into account the due dates of orders, preferences for matches, total allocated weights, total surplus weights of materials, and other constraints.

Our approach is based on a Variable Neighborhood Search (VNS) strategy. VNS combines local search with systematic changes of neighborhood and escape phases from local optimums. The search explores a small neighborhood around the current solution first, and allows an exchange with the current solution if a better one has been found. This process continues until the search fails to find a better solution. If the search failed to find a better solution, then it explores distant neighborhoods from the current solution and continues the process.

Our algorithm creates an initial solution by using an LP relaxation technique. Then it applies 9 types of neighborhood searches. They include well-known and powerful search techniques such as ejection chain search and include our special technique for reducing the surpluses. Our algorithm yielded considerable cost reductions in a real steel works.

• Hiroki Yanagisawa, "Two-Variable Integer Programming Neighbourhood Search for Material Allocation Problem," IBM Tokyo Research Laboratory Technical Report RT0632, 2005.