Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems

被引：75
作者：
Pessoa A. [1 ]
Uchoa E. [1 ]
de Aragão M.P. [2 ]
Rodrigues R. [3 ,4 ]
机构：
[1] Departamento de Engenharia de Produção, Universidade Federal Fluminense, Niterói
[2] Departamento de Informática, PUC Rio de Janeiro, Rio de Janeiro
[3] Departamento de Ciência da Computação, Universidade Federal do Amazonas, Manaus
[4] COPPE-Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro
来源：
Mathematical Programming Computation | 2010年 / 2卷 / 3-4期
关键词：
90C10; 90C57;
D O I：
10.1007/s12532-010-0019-z
中图分类号：
学科分类号：
摘要：
This paper presents an exact algorithm for the identical parallel machine scheduling problem over a formulation where each variable is indexed by a pair of jobs and a completion time.We show that such a formulation can be handled, in spite of its huge number of variables, through a branch cut and price algorithm enhanced by a number of practical techniques, including a dynamic programming procedure to fix variables by Lagrangean bounds and dual stabilization. The resulting method permits the solution of many instances of the P{double pipe}Σwj Tj problem with up to 100 jobs, and having 2 or 4 machines. This is the first time that medium-sized instances of the P{double pipe}Σwj Tj have been solved to optimality. © Springer and Mathematical Optimization Society 2010.
引用
收藏
页码：259 / 290
页数：31
相关论文
共 30 条
[1]  
Avella P., Boccia M., D'Auria B., Near-optimal solutions of large scale single-machine scheduling problems, ORSA J. Comput., 17, pp. 183-191, (2005)
[2]  
Ben Amor H., Frangioni A., Desrosiers J., On the choice of explicit stabilizing terms in column generation, Discrete Appl. Math., 157, pp. 1167-1184, (2009)
[3]  
Bigras L., Gamache M., Savard G., Time-indexed formulations and the total weighted tardiness problem, INFORMS J. Comput., 1, pp. 133-142, (2008)
[4]  
Dash S., Fukasawa R., Gunluk O., On the generalized master knapsack polyhedron, Proceedings of the 12th IPCO Conference, Lecture Notes in Computer Science, 4513, pp. 197-209, (2007)
[5]  
Dyer M., Wolsey L., Formulating the single machine sequencing problem with release dates as a mixed integer program, Discrete Appl. Math., 26, pp. 255-270, (1990)
[6]  
Fukasawa R., Longo H., Lysgaard J., Poggi de Aragao M., Reis M., Uchoa E., Werneck R.F., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math. Program., 106, pp. 491-511, (2006)
[7]  
Irnich S., Desaulniers G., Desrosiers J., Hadjar A., Path-reduced costs for eliminating arcs in routing and scheduling, INFORMS J. Comput., 22, pp. 297-313, (2010)
[8]  
Lawler E., A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness, Ann. Discrete Math., 1, pp. 331-342, (1977)
[9]  
Lemarechal C., Lagrangean relaxation, Computational Combinatorial Optimization, pp. 115-160, (2001)
[10]  
du Merle O., Villeneuve D., Desrosiers J., Hansen P., Stabilized column generation, Discrete Math., 194, pp. 229-237, (1999)
123