文献

J-GLOBAL ID：202202225969330051   整理番号：22A0888001

構造化集合システムにおける確率的メイクスパン最小化【JST・京大機械翻訳】

Stochastic makespan minimization in structured set systems

著者 (4件)： Gupta Anupam (Carnegie Mellon University, Pittsburgh, PA, USA) ,  Kumar Amit (Indian Institute of Technology Delhi, New Delhi, India) ,  Nagarajan Viswanath (University of Michigan, Ann Arbor, MI, USA) ,  Shen Xiangkun (Yahoo! Research, NYC, New York, NY, USA)
資料名： Mathematical Programming  (Mathematical Programming)
巻： 192  号： 1-2  ページ： 597-630  発行年： 2022年 
JST資料番号： B0847B  ISSN： 0025-5610  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 目的は,期待最大負荷(すなわち,メイクスパン)を最小化するための確率的組合せ最適化問題を研究した。このフレームワークでは,各タスクjが資源のいくつかの部分集合を使用する,一連のnタスクとmリソースを持つ。タスクはランダムサイズの[数式:原文を参照]を持ち,著者らの目標は,任意の資源iの負荷がiを使用するすべての選択されたタスクの全体のサイズである,すべてのリソース上の期待した最大負荷を最小化するために,非適応的にtタスクを選択することである。例えば,資源が点であり,タスクがラインの間隔である場合,[数式:原文を参照]近似アルゴリズムを得る。提案手法は,タスクと資源間の関係におけるいくつかの幾何学的構造の他の問題にも適用可能である。例えば,充填経路,長方形,および「脂肪」オブジェクトである。本手法では,ランダム変数のキュムラント生成関数を用いた強いLP緩和を用いた。また,このLPは,線上の間隔を選択する問題に対してさえ,[数式:原文を参照]積分ギャップを持つことを示す。ここでは,[数式:原文を参照]は反復対数関数である。Copyright Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 線形計画法 ,  母関数 ,  *作業時間 ,  *ピーク負荷 ,  対数関数 ,  緩和現象 ,  キュムラント ,  組合せ最適化問題
準シソーラス用語： *メイクスパン ,  近似アルゴリズム ,  ランダム変数 , 【Automatic Indexing@JST】

著者キーワード (4件)： 確率的最適化 ,  近似アルゴリズム ,  幾何学的パッキング ,  線形計画法

分類 (3件)： 工程管理  (KB03030P) ,  計算機網  (JC03000K) ,  オペレーティングシステム  (JD03020J)

タイトルに関連する用語 (5件)： 構造化 ,  集合 ,  確率 ,  メイクスパン ,  最小化