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

G Gutin (gutincs.rhul.ac.uk)
A Rafiey (arashcs.rhul.ac.uk)
A Yeo (anderscs.rhul.ac.uk)
M Tso (mike.tsoumist.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