Optimal scheduling of tasks to be performed in different unit operations is of paramount importance in the batch processes. The pressure toward sustainable operation has warranted more attentions to be paid to the issues of heat integration to reduce the utility consumption. This paper presents a new approach for incorporating heat integration in batch process scheduling. The method is based on a sequential framework, where the overall problem is decomposed into two sequentially solved problems of scheduling and heat integration. First, the schedule is optimized to meet the economic objective such as makespan or profit. Next, alternate schedules are generated through a stochastic search-based integer cut procedure that adds further constraints to the scheduling formulation. Such schedules may be the alternate optima of the scheduling problem. Finally, heat integration analysis coupled with the time average model (TAM) and time slice model (TSM) is applied to each of the resulting schedules to establish the minimum utility targets. The approach is based on the precept that opportunities for heat integration between tasks are higher in near-optimal schedules where tasks are temporally clustered together. The method differs from other sequential approaches published in the literature in that the heat integration problem is solved with the intent to retain the optimality of the scheduling solution. The proposed method has the ability to handle problems too complex to be solved using simultaneous optimization approaches. It has been applied to two literature case studies. The first one involves profit maximization as the objective function. The second one entails a more complex scenario involving makespan and utilities. The results from both case studies demonstrate the effectiveness of the approach. © 2009 American Chemical Society.