6A2 A BRANCH-AND-BOUND ALGORITHM BASED ON LARGRANGIAN RELAXATION FOR SINGLE-MACHINE SCHEDULING(Technical session 6A: Machine and shop scheduling 1)

スポンサーリンク

概要

• 論文の詳細を見る

• This study proposes a branch-and-bound algorithm for the single-machine scheduling problem where lower bounds are computed by the Lagrangian relaxation of the number of job occurrences. We propose a method to improve this lower bound by introducing a constraint on adjacent jobs. Then, branch-and-bound algorithms for the general single-machine problem and for the total weighted tardiness problem are constructed. Computational results show that more than 90% of the total weighted tardiness problem instances with 100 jobs can be optimally solved by our algorithm.

• 一般社団法人日本機械学会の論文
• 2006-07-18

著者

• Tanaka Shunji

  Graduate School Of Electrical Engineering Kyoto University

• Fujikuma Shuji

  Graduate School of Electrical Engineering, Kyoto University

• Araki Mituhiko

  Matsue National College of Technology

• Araki Mituhiko

  Matsue College Of Technology

• Fujikuma Shuji

  Graduate School Of Electrical Engineering Kyoto University

関連論文

• 6A2 A BRANCH-AND-BOUND ALGORITHM BASED ON LARGRANGIAN RELAXATION FOR SINGLE-MACHINE SCHEDULING(Technical session 6A: Machine and shop scheduling 1)
• 2B2 TWO TYPES OF BRANCH-AND-BOUND ALGORITHMS FOR THE SCHEDULING PROBLEM TO MINIMIZE TOTAL TARDINESS ON IDENTICAL PARALLEL MACHINES(Technical session 2B : Combinatorics 1)
• 2B2 AN IMPROVED ALGORITHM FOR THE SINGLE-MACHINE TOTAL WEIGHTED TARDINESS PROBLEM WITH SEQUENCE-DEPENDENT SETUP TIMES

スポンサーリンク