Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
Tóm tắt
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||∑w
j
T
j
problem with up to 100 jobs, and having 2 or 4 machines. This is the first time that medium-sized instances of the P||∑w
j
T
j
have been solved to optimality.
Tài liệu tham khảo
Avella P., Boccia M., D’Auria B.: Near-optimal solutions of large scale single-machine scheduling problems. ORSA J. Comput. 17, 183–191 (2005)
Ben Amor H., Frangioni A., Desrosiers J.: On the choice of explicit stabilizing terms in column generation. Discrete Appl. Math. 157, 1167–1184 (2009)
Bigras L., Gamache M., Savard G.: Time-indexed formulations and the total weighted tardiness problem. INFORMS J. Comput. 1, 133–142 (2008)
Dash, S., Fukasawa, R., Gunluk, O.: On the generalized master knapsack polyhedron. In: Proceedings of the 12th IPCO Conference, Lecture Notes in Computer Science, vol. 4513, pp. 197–209 (2007)
Dyer M., Wolsey L.: Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math. 26, 255–270 (1990)
Fukasawa R., Longo H., Lysgaard J., Poggi de Aragão M., Reis M., Uchoa E., Werneck R.F.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. 106, 491–511 (2006)
Irnich S., Desaulniers G., Desrosiers J., Hadjar A.: Path-reduced costs for eliminating arcs in routing and scheduling. INFORMS J. Comput. 22, 297–313 (2010)
Lawler E.: A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Ann. Discrete Math. 1, 331–342 (1977)
Lemaréchal C.: Lagrangean relaxation. In: Juenger, M., Naddef, D. (eds) Computational Combinatorial Optimization, pp. 115–160. Springer, Berlin (2001)
du Merle O., Villeneuve D., Desrosiers J., Hansen P.: Stabilized column generation. Discrete Math. 194, 229–237 (1999)
Oukil A., Ben Amor H., Desrosiers J., El Gueddari H.: Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems. Comput. Oper. Res. 34, 817–834 (2007)
Pan Y., Shi L.: On the equivalence of the max- min transportation lower bound and the time-indexed lower bound for single machine scheduling problems. Math. Program. 110, 543–559 (2007)
Pessoa A., Poggi de Aragão M., Uchoa E.: Robust branch-cut-and-price algorithms for vehicle routing problems. In: Golden, B., Raghavan, S., Wasil, E. (eds) The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 297–326. Springer, Berlin (2008)
Pessoa A., Uchoa E., Poggi de Aragão M.: A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. Networks 54, 167–177 (2009)
Pessoa, A., Uchoa, E., Poggi de Aragão, M., Rodrigues, R.: Algorithms over arc-time indexed formulations for single and parallel machine scheduling problems. Tech. Rep. RPEP Vol.8 no.8, Universidade Federal Fluminense, Engenharia de Produção, Niterói, Brazil (2008)
Pinedo M.: Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, USA (2002)
Poggi de Aragão M., Uchoa E.: Integer program reformulation for robust branch-and-cut-and-price. In: Wolsey, L. (eds) Annals of Mathematical Programming in Rio, pp. 56–61. Búzios, Brazil (2003)
Potts C., Wassenhove L.: A branch-and-bound algorithm for the total weighted tardiness problem. Oper. Res. 32, 363–377 (1985)
Queyranne, M., Schulz, A.: Polyhedral approaches to machine scheduling. Tech. Rep. 408, University of Berlin (1997)
Rodrigues, R., Pessoa, A., Uchoa, E., Poggi de Aragão, M.: Heuristics for multi-machine weighted tardiness problems. Tech. Rep. RPEP Vol.8 no.11, Universidade Federal Fluminense, Engenharia de Produção, Niterói, Brazil (2008)
Sadykov, R.: Integer programming-based decomposition approaches for solving machine scheduling problems. Ph.D. thesis, Universite Catholique de Louvain (2006)
Souayah N., Kacem I., Haouari M., Chu C.: Scheduling on parallel identical machines to minimise the total weighted tardiness. Int. J. Adv. Oper. Manage. 1(1), 30–69 (2009)
Sourd F.: New exact algorithms for one-machine earliness-tardiness scheduling. INFORMS J. Comput. 21, 167–175 (2009)
Sousa J., Wolsey L.: A time indexed formulation of non-preemptive single machine scheduling problems. Math. Program. 54, 353–367 (1990)
Tanaka S., Araki M.: A branch and bound algorithm with lagrangian relaxation to minimize total tardiness on identical parallel machines. Int. J. Prod. Econ. 113, 446–458 (2008)
Tanaka S., Fujikuma S., Araki M.: An exact algorithm for single-machine scheduling without machine idle time. J. Sched. 12, 575–593 (2009)
Uchoa E., Fukasawa R., Lysgaard J., Pessoa A., Poggi de Aragão M., Andrade D.: Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Math. Program. 122, 443–472 (2008)
Van der Akker J., Hurkens C., Savelsbergh M.: Time-indexed formulations for machine scheduling problems: column generation. INFORMS J. Comput. 12(2), 111–124 (2000)
Van der Akker J., Van Hoesel C., Savelsbergh M.: A polyhedral approach to single-machine scheduling problems. Math. Program. 85, 541–572 (1999)
Wentges P.: Weighted dantzig-wolfe decomposition for linear mixed-integer programming. Int. Trans. Oper. Res. 4, 151–162 (1997)