1B2 AN APPROXIMATION ALGORITHM FOR MAXIMIZING WEIGHTED NUMBER OF JUST-IN-TIME JOBS ON UNRELATED PARALLEL MACHINES(Technical session 1B: Machine and shop scheduling)

スポンサーリンク

概要

• 論文の詳細を見る

• We are concerned with a scheduling problem, in which jobs are scheduled non-preemptively on unrelated parallel machines, with the objective to maximize the weighted number of jobs that are completed exactly at their due dates, i.e., just-in-time jobs. We propose an approximation algorithm for solving this problem. It achieves approximation ratio k/m and runs in time O(m^kn^(k+1)), where n is the number of jobs, m is the number of machines, and k ∈ {1, ... , m} is a parameter of the proposed algorithm.

• 2011-07-02

著者

• Sung Shao-Chin

  Department of Industrial and Systems Engineering, Aoyama Gakuin University

• Shigezumi Takeya

  Department of Industrial and Systems Engineering, Aoyama Gakuin University

• Furuya Yuichi

  Department of Industrial and Systems Engineering, Aoyama Gakuin University

• Yamazaki Kiyotaka

  Department of Industrial and Systems Engineering, Aoyama Gakuin University

• Watanabe Kouhei

  Department of Industrial and Systems Engineering, Aoyama Gakuin University

関連論文

• DS-1-7 Scale Free Interval Graphs
• 1B2 AN APPROXIMATION ALGORITHM FOR MAXIMIZING WEIGHTED NUMBER OF JUST-IN-TIME JOBS ON UNRELATED PARALLEL MACHINES(Technical session 1B: Machine and shop scheduling)

スポンサーリンク