Solving parallel machine scheduling problems by column generation

被引:150
作者
Chen, ZL [1 ]
Powell, WB
机构
[1] Univ Penn, Dept Syst Engn, Philadelphia, PA 19104 USA
[2] Princeton Univ, Dept Civil Engn & Operat Res, Princeton, NJ 08544 USA
关键词
D O I
10.1287/ijoc.11.1.78
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
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-hound 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.
引用
收藏
页码:78 / 94
页数:17
相关论文
共 37 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]  
[Anonymous], THESIS GEORGIA I TEC
[3]  
Baker K. R., 1994, INTRO SEQUENCING SCH
[4]  
Barnes J. W., 1977, AIIE Transactions, V9, P25, DOI 10.1080/05695557708975117
[5]  
Barnhart C., 1994, MATH PROGRAMMING STA, P186
[6]   SCHEDULING IDENTICAL PARALLEL MACHINES TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME [J].
BELOUADAH, H ;
POTTS, CN .
DISCRETE APPLIED MATHEMATICS, 1994, 48 (03) :201-218
[7]  
Bondy J., 1976, Graph Theory
[8]   A DUAL ASCENT AND COLUMN GENERATION HEURISTIC FOR THE DISCRETE LOTSIZING AND SCHEDULING PROBLEM WITH SETUP TIMES [J].
CATTRYSSE, D ;
SALOMON, M ;
KUIK, R ;
VANWASSENHOVE, LN .
MANAGEMENT SCIENCE, 1993, 39 (04) :477-486
[9]  
CHAN LMA, 1995, MACHINE SCHEDULING L
[10]  
CHEN ZL, 1996, DECOMPOSITION APPROA