Scheduling is crucial for effective implementations of production, manufacturing, and logistics. With rare exceptions of extremely simple cases, only mathematical programming, e.g., Mixed Integer Linear Programming (MILP), can guarantee the optimal answer to practical scheduling problems. Unfortunately, the applicability of general-purpose MILP solvers is limited by the required computational time. To achieve a sufficiently fast answer in practice by mathematical programming, a highly flexible solution procedure is needed that can be tailored to the problem under investigation. Solution methods utilizing graph theory in parallel with algebraic operations give more room for customization. Process Network Synthesis (PNS) and the P-graph framework were originally developed to design and optimize chemical engineering process structures with continuous operation. Time Constrained Process Network Synthesis (TCPNS) has made it capable to handle batch processes with time constraints and storage strategies. P-graph algorithms extended to TCPNS can solve the precedence-based MILP model formulation of scheduling problems and are highly customizable as well. The aim of the current research is to examine and find the most suitable decision variable selection strategy for P-graph framework’s optimization method to gain possible accelerations for different classes of scheduling problems.