The resolution of combinatorial optimization problems, es-pecially in the area concerned with the sequencing of tasks (i.e., referred to as sequencing problems), is an important challenge. This domain covers a wide breadth of applications expressed as scheduling or routing problems. Such problems can be often optimally solved using Constraint Programming techniques; nevertheless, if a “good” solution is needed in a short amount of time, Constraint Programming techniques may simplynot be feasible.This paper explores the opportunities that the transitional semantics of Multi-valued Decision Diagrams (MDDs) offers in terms of modeling and efficiency. The paper explores the combination of MDDs with Large Neighborhood Search (LNS), as an effective local search strategy. The paper also demonstrates the use of GPU-based parallelism to enhance efficency in the exploration of the search space.The paper describes the integration of these techniques within a solver,focused on time-bounded search for high-quality solutions. The solver is evaluated on several classes of benchmarks, with positive outcomes in terms of time and solution quality compared to state-of-the-art constraint-based local search solvers.