Solving in Imagination: Multi-Step Latent Planning for Combinatorial Scheduling

Neural constructive policies have attracted increasing attention for combinatorial scheduling by learning to construct schedules through sequential decisions. However, existing methods primarily optimize representations for immediate action selection and recompute them by re-encoding the exact state after each action rather than explicitly modeling how decision-relevant representations evolve across successive scheduling steps. Moreover, repeatedly re-encoding the evolving partial schedule introduces substantial redundant computation during inference. To address these limitations, we introduce the Multi-Step Latent Planning Model (MSLPM) for constructive combinatorial scheduling. We develop a solve-then-imagine training scheme that first jointly trains an Encoder and Actor to establish a decision-relevant latent space, and then freezes both modules while learning Dynamics to propagate this fixed representation under scheduling actions through latent alignment and decision-consistency supervision. Building on these learned latent dynamics, we introduce a multi-step latent planning mechanism that recursively generates an $H$-step action prefix from a single exact-state encoding by alternating the Actor and Dynamics, while exact scheduling operators maintain feasibility. Across three benchmarks, i.e., PFSP, JSSP, and FJSP, MSLPM achieves lower average gaps than the greedy neural baselines considered, while multi-step latent planning substantially reduces inference time by replacing intermediate re-encoding with latent transitions.The code will be publicly released upon acceptance.