Complexity of Bilevel Scheduling Problems with Machine-Dependent Processing Times: Classical, Parameterized, and Approximation Perspectives

Bilevel scheduling captures hierarchical decision-making where a leader assigns jobs to machines and a follower sequences them, each optimizing distinct objectives. We provide a comprehensive complexity analysis for unrelated parallel machines with machine-dependent processing times, examining the problem through three complementary lenses: classical complexity, parameterized complexity, and approximability. Our main results establish that pessimistic bilevel scheduling is Σ₂ᴾ-complete, placing it at the second level of the polynomial hierarchy where no compact integer programming formulation exists unless unlikely complexity-theoretic collapses occur. We prove that the problem is W[1]-hard when parameterized by the number of machines, yet fixed-parameter tractable when parameterized by both machine count and maximum processing time. For the optimistic variant, we design a polynomial-time approximation scheme and prove APX-hardness, precisely characterizing its approximability. We identify polynomial-time solvable special cases including fixed machine count and agreeing processing time orders. These results bridge bilevel optimization, scheduling theory, and parameterized complexity, revealing how the hierarchical structure interacts with machine heterogeneity to determine computational tractability.