This paper deals with the production scheduling of multipurpose batch plants. A navel graph representation is proposed that takes into consideration the specific characteristics of chemical processes in scheduling. In this graphs, the nodes represent the production tasks and the arcs the precedence relationships among them. The representation is flexible enough to consider a great variety of production structures (recipes with branches, alternative units,...). Both NIS and UIS transfer policies can be considered simply by choosing the appropriate precedence relationships. This representation provides the opportunity of incorporating highly efficient graph algorithms together with an appropriate branch-and-bound (B&B) algorithm for serving multipurpose scheduling problems effectively. The B&B algorithm takes care of the combinatorial optimization problem involved in each scheduling problem, while the graph algorithms allow to obtain the lower bounds that control the branching strategy. The efficiency of the proposed method is established by comparing it with the application of a generic B&B solving an equivalent MILP scheduling model.