一般化非関連機械スケジューリング問題【JST・京大機械翻訳】

Deng Shichuan; Li Jian; Rabani Yuval

プレプリント

J-GLOBAL ID：202202216375311175 整理番号：22P0288904

一般化非関連機械スケジューリング問題【JST・京大機械翻訳】

Generalized Unrelated Machine Scheduling Problem

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2022年02月13日プレプリントサーバーでの情報更新日： 2022年02月13日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

nジョブを与える一般化負荷平衡(GLB)問題を研究し,その各々は,処理時間{p_ij}を持つm関係のない機械の1つに割り当てる必要がある。ジョブ割当σの下では,各機械iの負荷はψ_i(p_i[σ])であり,そこではψ_i:R ̄n→R_≧0は対称単調ノルムであり,p_i[σ]はn次元ベクトル{p_ij.1[σ(j)=i]}_j∈[n]である。著者らの目標は,φ:R ̄m→R_≧0が他の対称単調ノルムであり,荷重(σ)がm次元マシン負荷ベクトルである一般化メイクスパンφ(負荷(σ))を最小化することである。この問題は,多くの古典的最適化問題,例えばメイクスパン最小化,集合カバー,最小ノルム負荷平衡などを一般化する。O(logn)の近似因子を達成する多項式時間ランダム化アルゴリズムを得て,一定因子までの集合カバーの下限を整合させた。変数の指数数による新しい配置LP緩和を丸めることによりこれを達成した。構成LPを近似的に解くために,その二重プログラムのための近似分離オラクルを設計した。特に,分離オラクルは,線形制約(NormLin)問題でノルム最小化に低減でき,そのために多項式時間近似スキーム(PTAS)を考案し,それは独立した興味の可能性がある。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

オペレーティングシステム , 工程管理

前のページに戻る