We study two classes of dynamic scheduling problems termed as "allocation" and "advanced" scheduling. In allocation scheduling, arriving jobs either wait in queue, are rejected, or served immediately, while in advanced scheduling, they are scheduled to time slots such as days in a booking horizon. We develop approximate dynamic programming (ADP) based on direct search that approximately solves the underlying Markov decision process models. We compare the performance of the proposed technique against the myopic policy under various scenarios. Numerical results demonstrate that the direct-search based ADP yields significant improvements over the myopic policy in all of the problem sets.