This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Kalagnanam, J. R. Articles by Lee, H. S. Search for Related Content

The Surplus Inventory Matching Problem in the Process Industry

International Business Machines, T. J. Watson Research Center, Yorktown Heights, NY 10598
International Business Machines, T. J. Watson Research Center, Yorktown Heights, NY 10598
International Business Machines, T. J. Watson Research Center, Yorktown Heights, NY 10598
International Business Machines, T. J. Watson Research Center, Yorktown Heights, NY 10598
jayant{at}us.ibm.com
milind{at}us.ibm.com
trumbo{at}us.ibm.com
hslee{at}us.ibm.com

We introduce a new problem that arises from operations planning in the process industry. This problem involves matching an order book against surplus inventory before production planning. It can be formulated by generalizing the multiple knapsack problem along three dimensions: (i) adding assignment restrictions on items that can be assigned to a knapsack, (ii) adding a new attribute (called "color" in this paper) to an item and then adding the associated "color" constraints that restrict the number of distinct colors that can be assigned to a knapsack, and (iii) considering multiple objectives for optimization. We formulate the problem, provide a result regarding its complexity, and report on our computational experience with solving a set of real instances based on data from the operations of a large steel plant. We then propose a network-flow—based heuristic that yields solutions within 3% of optimal (or the best known feasible solution). This system has been successfully deployed and is now used daily in the mill operations.

Subject classifications: Production/scheduling: applications; planning, approximations/heuristics; Inventory/production: approximations/heuristics, applications; Industry, mining, metals.

This article has been cited by other articles:

				C. Clifton, A. Iyer, R. Cho, W. Jiang, M. Kantarcioglu, and J. Vaidya An Approach to Securely Identifying Beneficial Collaboration in Decentralized Logistics Systems MSOM, January 1, 2008; 10(1): 108 - 125. [Abstract] [PDF]

				J. J. H. Forrest, J. Kalagnanam, and L. Ladanyi A Column-Generation Approach to the Multiple Knapsack Problem with Color Constraints INFORMS Journal on Computing, January 1, 2006; 18(1): 129 - 134. [Abstract] [PDF]

				M. Dawande, J. Kalagnanam, H. S. Lee, C. Reddy, S. Siegel, and M. Trumbo The Slab-Design Problem in the Steel Industry Interfaces, May 1, 2004; 34(3): 215 - 225. [Abstract] [PDF]

				B. Denton, D. Gupta, and K. Jawahir Managing Increasing Product Variety at Integrated Steel Mills Interfaces, March 1, 2003; 33(2): 41 - 53. [Abstract] [PDF]

				A. Balakrishnan and J. Geunes Production Planning with Flexible Product Specifications: An Application to Specialty Steel Manufacturing Operations Research, January 1, 2003; 51(1): 94 - 112. [Abstract] [PDF]