抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
1||Σw_jU_j問題は,それぞれ自身の処理時間,重み,および今日まで,これらのジョブのための任意の単一マシン非プリエンプティブスケジュールにおける遅延ジョブの最小加重数によって,-ギブンnジョブを決定する。これはKnapsackとSubset Sumの両方を一般化する古典的スケジューリング問題である。LawlerとMoore[Management Science’69]による1||Σw_jU_jの最良の既知擬似多項式アルゴリズムは60年代後半に遡って,nがジョブの数であり,d_maxが今日まで最大であるO(d_maxn)の実行時間を持っている。Knapsackに対するCyganet al. ̄[ICALP’19]による最近の下限は,1||Σw_jU_jが,妥当な予測の下で,任意のΔΨ0に対して,O((n+d_max) ̄2-ε)時間で解くことができないことを示した。これは,この問題に対して最良の既知の下限と上限の間のギャップを依然として残す。本論文では,その主なツールとして(最大,+)畳込みを用いる1||Σw_jU_jの新しい簡単なアルゴリズムを設計し,いくつかのパラメータ範囲でLawlerとMooreアルゴリズムより優れている。特に,計算(最大,+)-畳込みの特定の方法に依存して,その実行時間は-O(n+d_#d_max ̄2)-O(d_#n+d ̄2_#d_maxw_max)-O(d_#n+d_#d_maxp_max)-O(n ̄2+d_maxw ̄2_max)-O(n ̄2+d_#(d_maxw_max) ̄1.5)によって制限できる。ここで,d_#は,事例における異なる日付日数を示し,p_maxはどのジョブの最大処理時間を意味し,w_maxはどのジョブの最大重みも示す。【JST・京大機械翻訳】
