Solving parallel machine scheduling problems by column generation

We consider a class of problems of scheduling n jobs on m identical, unifor m, or unrelated parallel machines with an objective of minimizing an additi ve criterion. We propose a decomposition approach for solving these problem s exactly. The decomposition approach first formulates these problems as an integer program, and then reformulates the integer program, using Dantzig- Wolfe decomposition, as a set partitioning problem. Based on this set parti tioning formulation, branch-and-hound exact solution algorithms can be desi gned for these problems. In such a branch and-bound tree, each node is the linear relaxation problem of a set partitioning problem. This linear relaxa tion problem is solved by a column generation approach where each column re presents a schedule on one machine and is generated by solving a single mac hine subproblem. Branching is conducted on variables in the original intege r programming formulation instead of variables in the set partitioning form ulation such that single machine subproblems are more tractable. We apply t his decomposition approach to two particular problems: the total weighted c ompletion time problem and the weighted number of tardy jobs problem. The c omputational results indicate that the decomposition approach is promising and capable of solving large problems.