Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Solving Parallel Machine Scheduling Problems by Column Generation

Solving Parallel Machine Scheduling Problems by Column Generation 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png INFORMS Journal on Computing INFORMS

Solving Parallel Machine Scheduling Problems by Column Generation

INFORMS Journal on Computing , Volume 11 (1): 17 – Feb 1, 1999
17 pages

Loading next page...
 
/lp/informs/solving-parallel-machine-scheduling-problems-by-column-generation-60jUyrAG7q

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
INFORMS
Copyright
Copyright © INFORMS
Subject
Research Article
ISSN
1091-9856
eISSN
1526-5528
DOI
10.1287/ijoc.11.1.78
Publisher site
See Article on Publisher Site

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.

Journal

INFORMS Journal on ComputingINFORMS

Published: Feb 1, 1999

Keywords: Keywords : machine scheduling ; column generation ; integer programming ; parallel machine scheduling ; set partitioning ; Dantzig-Wolfe decomposition ; column generation ; branch and bound

References