A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

被引:65
作者
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
关键词
parallel machine scheduling; just-in-time; set partitioning; Dantzig-Wolfe decomposition; column generation; branch and bound;
D O I
10.1016/S0377-2217(98)00136-2
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig-Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound tract solution algorithm is developed for the problem, In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:220 / 232
页数:13
相关论文
共 31 条
[1]  
[Anonymous], THESIS GEORGIA I TEC
[2]  
BAKER KR, 1990, OPERATIONS RES, V38
[3]  
Barnhart C., 1994, MATH PROGRAMMING STA, P186
[4]   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
[5]  
CHAN LMA, 1995, MACHINE SCHEDULING L
[6]  
CHEN ZL, IN PRESS INFORMS J C
[7]  
CHENG TCE, 1994, J OPER RES SOC, V45, P685, DOI 10.1057/jors.1994.106
[8]  
CHENG TCE, 1989, J OPER RES SOC, V40, P1129, DOI 10.1057/palgrave.jors.0401208
[9]   DECOMPOSITION PRINCIPLE FOR LINEAR-PROGRAMS [J].
DANTZIG, GB ;
WOLFE, P .
OPERATIONS RESEARCH, 1960, 8 (01) :101-111
[10]  
DAVIS JS, 1993, NAV RES LOG, V40, P85, DOI 10.1002/1520-6750(199302)40:1<85::AID-NAV3220400106>3.0.CO