In this paper a heuristic procedure is developed for solving the problem of planning machine replacements for a serially dependent production system. Given a finite planning horizon, the decision-maker wishes to decide (1) which periods, if any, that the entire production system must be shut down in order to make replacements, and (2) what specific machine or machines in the system should be scheduled for replacement during each of these downtime periods. The problem involves a balancing of costs. If the production system is brought down to make one or more replacements a fixed downtime cost is incurred; this cost is independent of the machines replaced during the downtime. In addition, other fixed coats are incurred for each of the machines replaced. Our motivation for scheduling these replacements is to realize lower variable costs for operating the machines. The variable operating costs are assumed to increase as the age or vintage of the machines increases. An optimal replacement policy is one in which the total of the present-value fixed and operating costs are minimized for the entire planning horizon. The paper also presents computational results using the heuristic to solve a large number of randomly generated test problems of varying numbers of machines and periods. These heuristic solutions are compared to known optimal solutions for a number of the problems. One of the important advantages of the heuristic procedure is that it is capable of producing several solutions to a given problem, all rank ordered by increasing cost. Thus, the decision-maker is afforded alternative choices from which he or she may select a replacement policy.