PROPERTY OF THE OPTIMUM RELAXED SOLUTION FOR PROBLEM TO SCHEDULE INDEPENDENT TASKS ON UNRELATED PROCESSORS

スポンサーリンク

概要

• 論文の詳細を見る

• The linear programming relaxation of the zero-one optimization problem to schedule n independent tasks nonpreemptively on m unrelated processors with the objective of minimizing the maximum completion time is considered. This relaxed problem is solved by mapping tasks into m-1 dimensional unit simplex A_<m-1> and by dividing it into m sub-simplexes (hyper cones), where each processor processes the tasks or the fractions of tasks whose images locate inside (including boundaries) of corresponded sub-simplex. The properties of the division of A_<m-1> (the associated partition of tasks) which generates the optimum relaxed solution and the existence of such a division are shown as two Theorems. They are proved, first, abstractly using Duality Theorem, and then directly. The latter elementary but intuitive proofs give helpful informations to find the optimum division of A_<m-1> directly. Finally applications of these theorems are discussed.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Numata K

  Department Of Computer Science And Information Mathematics The University Of Electro-communications

• Numata Kazumiti

  Department of Computer Science and Information Mathematics, The University of Electro-Communications

関連論文

• Prostatic carcinosarcoma: A case report and review of literature
• PROPERTY OF THE OPTIMUM RELAXED SOLUTION FOR PROBLEM TO SCHEDULE INDEPENDENT TASKS ON UNRELATED PROCESSORS

スポンサーリンク