A graph theoretical approach is proposed for the optimal scheduling of multipurpose batch plants when constraints on intermediate storage allocation are met. The novel S-graph representation is extended and combined with a set of rationales to consider intermediate storage policy in production scheduling. This set of rationales accelerates the optimization procedure, reducing the searching tree from the very beginning, without losing optimality. It is assumed that the storage units can be commonly used throughout the plant to achieve maximum plant flexibility. Therefore, the problem solved suggests the more general batch-process transfer strategy, common intermediate storage policy (CIS). This policy is suggested for more flexible use of intermediate storage units. The accuracy of this proposed algorithm is tested with an exhaustive B&B search algorithm. The methodology is compared with other CIS algorithms and is applied to solve several case studies. The benefits of considering this kind of storage coupled with the use of the proposed algorithm are discussed through motivating examples. (C) 2004 American Institute of Chemical Engineers.