| Capital assets provide operating capacity for most industries and entities, which manufacture products or provide services to meet their individual objectives. Acquisition, operating, maintenance and disposal costs of these assets strongly influence the performance of these entities. Thus, effective utilization and timely replacement of these assets is essential for efficient operations.; In this thesis, we study the parallel replacement problem (PRP) with economies of scale, in which there are both fixed and variable costs associated with replacing existing assets. We formulate the problem as an integer program and show it is a difficult combinatorial problem.; After introducing some basic rules and solution characteristics of the PRP problem, we propose two kinds of cutting planes, i.e lower triangle cuts and network flow inequalities, which are designed to enforce the NSR rule in the literature. We also develop a heuristic algorithm to get a tighter upper bound for the LP relaxation of the PRP problem. Our later computational experiments show the effectiveness of the branch-and-cut algorithm that implements these techniques. Further, we show that the same procedure can be easily adapted to solve more generalized PRP problems, such as non-decreasing demand PRP problem and heterogeneous assets PRP problem.; We also discuss a special case of PRP problem, the infinite horizon case, of which we define an error bounded solution horizon and propose an iterative method to solve this special problem. The computational experiments show the effectiveness of the algorithm over the traditional approaches. |
