Scheduling is widely studied in process systems engineering and is typically solved using mathematical programming. Although popular for many other optimization problems, evolutionary algorithms have not found wide applicability in such combinatorial optimization problems with large numbers of variables and constraints. Here we demonstrate that scheduling problems that involve a process network of units and streams have a graph structure which can be exploited to offer a sparse problem representation that enables efficient stochastic optimization. In the proposed structure adapted genetic algorithm, SAGA, only the subgraph of the process network that is active in any period is explicitly represented in the chromosome. This leads to a significant reduction in the representation, but additionally, most constraints can be enforced without the need for a penalty function. The resulting benefits in terms of improved search quality and computational performance are established by studying 24 different crude oil operations scheduling problems from the literature. © 2012 American Chemical Society.