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

• Numata Kazumiti

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

抄録

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.

収録刊行物

• 日本オペレーションズ・リサーチ学会論文誌

  日本オペレーションズ・リサーチ学会論文誌 32 (2), 233-259, 1989

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

• Management Science and Operations Research
• General Decision Sciences

詳細情報

• CRID: 1390282679087361152
• NII論文ID: 110001184275
• DOI: 10.15807/jorsj.32.233
• ISSN: 21888299
• ISSN: 04534514
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/32/2/32_KJ00001202674/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可