Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems |
| |
Authors: | Artur Pessoa Eduardo Uchoa Marcus Poggi de Aragão Rosiane Rodrigues |
| |
Institution: | 1. Departamento de Engenharia de Produ??o, Universidade Federal Fluminense, Niterói, Brazil 2. Departamento de Informática, PUC Rio de Janeiro, Rio de Janeiro, Brazil 3. Departamento de Ciência da Computa??o, Universidade Federal do Amazonas, Manaus, Brazil 4. COPPE-Engenharia de Sistemas e Computa??o, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|