首页    期刊浏览 2024年12月05日 星期四
登录注册

文章基本信息

  • 标题: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
国家哲学社会科学文献中心版权所有