Solving Parallel Machine Scheduling Problems by Column Generation
- 1 February 1999
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 11 (1), 78-94
- https://doi.org/10.1287/ijoc.11.1.78
Abstract
We consider a class of problems of scheduling n jobs on m identical, uniform, or unrelated parallel machines with an objective of minimizing an additive criterion. We propose a decomposition approach for solving these problems 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 partitioning formulation, branch-and-bound exact solution algorithms can be designed for these problems. In such a branch-and-bound tree, each node is the linear relaxation problem of a set partitioning problem. This linear relaxation problem is solved by a column generation approach where each column represents a schedule on one machine and is generated by solving a single machine subproblem. Branching is conducted on variables in the original integer programming formulation instead of variables in the set partitioning formulation such that single machine subproblems are more tractable. We apply this decomposition approach to two particular problems: the total weighted completion time problem and the weighted number of tardy jobs problem. The computational results indicate that the decomposition approach is promising and capable of solving large problems.Keywords
This publication has 25 references indexed in Scilit:
- Minimizing the number of tardy jobs for m parallel machinesEuropean Journal of Operational Research, 1995
- Weighted flow time bounds for scheduling identical processorsEuropean Journal of Operational Research, 1995
- Solving binary cutting stock problems by column generation and branch-and-boundComputational Optimization and Applications, 1994
- A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problemsEuropean Journal of Operational Research, 1993
- A state-of-the-art review of parallel-machine scheduling researchEuropean Journal of Operational Research, 1990
- An improved branching scheme for the branch and bound procedure of schedulingnjobs onmparallel machines to minimize total weighted flowtimeInternational Journal of Production Research, 1988
- A new approach for crew pairing problems by column generation with an application to air transportationEuropean Journal of Operational Research, 1988
- An Improved Algorithm for Scheduling Jobs on Identical MachinesA I I E Transactions, 1977
- Scheduling Jobs on a Number of Identical MachinesA I I E Transactions, 1974
- Various optimizers for single‐stage productionNaval Research Logistics Quarterly, 1956