Embodiments of the invention provide a method for reducing instability in a heterogeneous job plan of a stream processing application. In one embodiment, a job manager may be configured to select a job plan with the objective of minimizing the potential instability of the job plan. Each job plan may provide a directed graph connecting processing elements (both native and non-native). That is, each job plan illustrates data flow through the stream application framework. The job plan may be selected from multiple available job plans, or may be generated by replacing processing elements of a given job plan. Further, the job plan may be selected on the basis of other objectives in addition to an objective of minimizing the potential instability of the job plan, such as minimizing cost, minimizing execution time, minimizing resource usage, etc.