Abstract: In this work, we focus on general multi-objective scheduling problems that can be modeled using a Petri net framework. Due to their generality, Petri nets are a useful abstraction that captures multiple characteristics of real-life processes. To provide a general solution procedure for the abstraction, we propose three alternative approaches using an indirect scheme to represent the solution: (1) a genetic algorithm that combines two objectives through a weighted fitness function, (2) a non dominated sorting genetic algorithm (NSGA-II) that explicitly addresses the multi-objective nature of the problem and (3) a multi-objective local search approach that simultaneously explores multiple candidate solutions. These algorithms are tested in an extensive computational experiment showing the applicability of this general framework to obtain quality solutions.