Optimization Online


Note: A Graph-Theoretical Approach to Level of Repair Analysis

G Gutin (gutin***at***cs.rhul.ac.uk)
A Rafiey (arash***at***cs.rhul.ac.uk)
A Yeo (anders***at***cs.rhul.ac.uk)
M Tso (mike.tso***at***umist.ac.uk)

Abstract: Level of Repair Analysis (LORA) is a prescribed procedure for defence logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels of indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize overall life-cycle costs. We consider the LORA optimization problem (LORAP) introduced by Barros (1998) and Barros and Riley (2001) who solved LORAP using branch-and-bound heuristics. The surprising result of this paper is that LORAP is, in fact, polynomial-time solvable. We prove it by reducing LORAP to the maximum weight independent set problem on a bipartite graph.

Keywords: Level of Repair Analysis; Independent Sets; Bipartite Graphs

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Category 3: Network Optimization

Citation: Submitted

Download: [PDF]

Entry Submitted: 08/29/2004
Entry Accepted: 08/30/2004
Entry Last Modified: 08/29/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society