In this paper, the operational planning problem for utility systems is formulated as a mixed-integer linear program (MILP). For multiperiod operation with piecewise constant varying demands for utilities, the optimal choice of units for each period is determined. The objective function accounts for both the operating costs for each period and changeover costs for startup/shutdown of units each between periods of operation. A two-stage approach is proposed that requires the solution of MILP subproblems coupled with a shortest path algorithm, resulting in orders of magnitude reduction in computation time as compared to a direct MILP solution using branch and bound enumeration. The computational requirements of the algorithm are linear with respect to the number of periods and global solution of the MILP is guaranteed. Solution of three sample problems yield savings up to 5% in total annual cost of operation with the main advantage being the simplicity of the proposed plan (few startups and shutdowns).