文章基本信息

标题：Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
其他标题：Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
本地全文：下载
作者：Pessoa, Artur ; Uchoa, Eduardo ; de Aragão, Marcus Poggi 等
期刊名称：Mathematical Programming Computation
印刷版ISSN：1867-2957
出版年度：2010
卷号：3
期号：2
页码：259-290
DOI：10.1007/mpc.v3i2.42
语种：English
出版社：Mathematical Programming Computation
摘要：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||\sum{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||\sum{wj Tj} have been solved to optimality.
关键词：90C10; 90C57