Machine Scheduling

An important subclass of resource allocation problems fall under the general category of machine scheduling. These problems arise when there are resources that must be assigned to tasks over time. The machine scheduling literature focuses on problems where the “machines” (resources) are few and relatively (or completely) homogeneous.


D. R. Ronconi and W. B. Powell, “Minimizing Total Tardiness in a Single Machine Scheduling Problem using Approximate Dynamic Programming,” Journal of Scheduling. Vol. 13, No. 6, pp. 597-607 (2010). DOI: 10.1007/s10951-009-0160-6.

The paper uses approximate dynamic programming to help decide whether a job should be scheduled for today or some day in the future.

(click here to download paper)

Chen, Z.-L. and W.B. Powell, “Solving Parallel Machine Scheduling Problems by Column Generation,” Informs Journal of Computing, Vol. 11, No. 1, Winter 1999. (c) Informs

This is the first paper to use column generation for parallel machine scheduling problems. Optimal solutions are presented demonstrating the computational efficiency of the technique.

(click here to download paper)

Chen, Z.-L. and W.B. Powell, Chen, Z.-L. and W.B. Powell, “A Column-Generation Based Decomposition Algorithm for a Parallel Machine Just-In-Time Scheduling Problem,” European Journal of Operations Research, Vol. 116, pp. 220-232 (1999).

(click here to download paper)

Chen, Z.L. and W.B. Powell, “Exact Algorithms for Scheduling Multiple Families of Jobs on Parallel Machines,” Naval Research Logistics, Vol. 50, No. 7, pp. 823-840, 2003.