Methods for solving batch process scheduling problems have gone through a vast development in the last 2 decades. Most of the published approaches are based on a mixed integer programming formulation. Since the difficulty of scheduling is originated from its combinatorial nature, graphs and combinatorial algorithms are more adequate to represent and solve the problem. Although, combinatorial algorithms and data structures have an enormous literature, these algorithms can not be directly applied to scheduling and further elaboration is needed. In the present work, the combinatorial nature of batch scheduling problems is analyzed. Several combinatorial algorithms are listed that can be considered for the scheduling of batch processes. Their proper adaptation is illustrated via the S-graph framework, in which the main emphasis lies on the combinatorial tools. Furthermore, Place Petri Nets and Timed Automata are also briefly described. An S-graph algorithm has been extensively compared with well-known MILP formulations.