Fugu-MT 論文翻訳(概要): Solving workflow scheduling problems with QUBO modeling

論文の概要: Solving workflow scheduling problems with QUBO modeling

arxiv url: http://arxiv.org/abs/2205.04844v1
Date: Tue, 10 May 2022 12:38:17 GMT
ステータス: 処理完了
システム内更新日: 2023-02-13 17:52:39.981366
Title: Solving workflow scheduling problems with QUBO modeling
Title（参考訳）: QUBOモデリングによるワークフロースケジューリング問題の解法
Authors: A. I. Pakhomchik, S. Yudin, M. R. Perelshtein, A. Alekseyenko, S. Yarkoni
Abstract要約: スケジューリング問題を表す新しいQUBOを開発し、入力問題に対する複雑性にQUBOがどのように依存するかを示す。我々は、この複雑さを軽減するために、この特定の応用の分解法を導出し、提示する。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper we investigate the workflow scheduling problem, a known NP-hard class of scheduling problems. We derive problem instances from an industrial use case and compare against several quantum, classical, and hybrid quantum-classical algorithms. We develop a novel QUBO to represent our scheduling problem and show how the QUBO complexity depends on the input problem. We derive and present a decomposition method for this specific application to mitigate this complexity and demonstrate the effectiveness of the approach.
Abstract（参考訳）: 本稿では,スケジューリング問題の既知のnpハードクラスであるワークフロースケジューリング問題について検討する。問題インスタンスを産業的なユースケースから導き出し,いくつかの量子,古典,ハイブリッド量子古典アルゴリズムと比較する。スケジューリング問題を表す新しいQUBOを開発し、QUBOの複雑性が入力問題にどのように依存するかを示す。本稿では, この複雑性を緩和し, アプローチの有効性を実証するために, この特定の応用の分解法を考案し, 提案する。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
QISS: Quantum Industrial Shift Scheduling Algorithm [1.2746940882175868]
産業シフトスケジューリングのための量子アルゴリズムの設計と実装について述べる。問題に存在する複数の制約を組み込んだGroverのオラクルの明示的な回路構成を与える。 Onanneriet.com/anneriet/QISS.comのコードをオープンソースリポジトリに提供しています。
論文参考訳（メタデータ） (2024-01-15T15:20:41Z)
A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文参考訳（メタデータ） (2023-06-15T15:28:12Z)
Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文参考訳（メタデータ） (2023-05-26T15:13:09Z)
A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
本稿では,一般に局所的に制約された最適化問題に対する量子インスパイアされたテンソルネットワークに基づくアルゴリズムを提案する。我々のアルゴリズムは、興味のある問題に対してハミルトニアンを構築し、量子問題に効果的にマッピングする。本研究は,本手法の有効性と応用の可能性を示すものである。
論文参考訳（メタデータ） (2022-03-29T05:44:07Z)
Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
論文参考訳（メタデータ） (2021-06-23T16:33:33Z)
A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文参考訳（メタデータ） (2021-03-10T03:16:12Z)
Learning to solve the single machine scheduling problem with release times and sum of completion times [0.76146285961466]
我々は,機械学習の分野とスケジューリング理論の手法を組み込んだ新しいアルゴリズムによる,ハードシングルマシンスケジューリング問題の解に着目する。これらは、ハード問題のインスタンスを最適性に解決された単純なインスタンスに変換します。
論文参考訳（メタデータ） (2021-01-04T16:40:18Z)
Metaheuristics for the Online Printing Shop Scheduling Problem [0.0]
この実際のスケジューリング問題は、現代の印刷業界で現れたもので、シークエンシングの柔軟性を備えたフレキシブルなジョブショップスケジューリング問題に対応している。この問題に対する局所探索戦略とメタヒューリスティックアプローチを提案し,評価した。フレキシブルなジョブショップスケジューリング問題における古典的事例を用いた数値実験により,本事例に適用した場合,導入手法も競争力を持つことが示された。
論文参考訳（メタデータ） (2020-06-22T15:38:00Z)
A Novel Multi-Agent System for Complex Scheduling Problems [2.294014185517203]
本稿では,様々な問題領域に適用可能なマルチエージェントシステムの概念と実装について述べる。提案手法の有効性を示すため,NP-hardスケジューリング問題をシミュレートする。本稿では,レイアウトの複雑さの低減,複雑なシステムの制御の改善,拡張性など,エージェントベースのアプローチの利点を強調した。
論文参考訳（メタデータ） (2020-04-20T14:04:58Z)
Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文参考訳（メタデータ） (2020-03-06T16:17:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。