論文の概要: Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling
- arxiv url: http://arxiv.org/abs/2205.07537v1
- Date: Mon, 16 May 2022 09:33:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-17 16:46:18.443816
- Title: Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling
- Title（参考訳）: ジョブショップスケジューリングのための問題分解とマルチショットASP解決
- Authors: Mohammed M. S. El-Kholany, Martin Gebser and Konstantin Schekotihin
- Abstract要約: ジョブショップスケジューリング問題(JSP)は、よく知られた、挑戦的な最適化問題である。
本稿では,操作を逐次スケジュールし,最適化可能な時間ウィンドウへの問題分解を提案する。
マルチショット ASP 解決による逐次最適化が実行時限界内でのスケジュールを大幅に改善することを示す。
- 参考スコア（独自算出の注目度）: 5.070542698701157
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Job-shop Scheduling Problem (JSP) is a well-known and challenging
combinatorial optimization problem in which tasks sharing a machine are to be
arranged in a sequence such that encompassing jobs can be completed as early as
possible. In this paper, we propose problem decomposition into time windows
whose operations can be successively scheduled and optimized by means of
multi-shot Answer Set Programming (ASP) solving. Decomposition aims to split
highly complex scheduling tasks into better manageable sub-problems with a
balanced number of operations so that good quality or even optimal partial
solutions can be reliably found in a small fraction of runtime. Problem
decomposition must respect the precedence of operations within their jobs and
partial schedules optimized by time windows should yield better global
solutions than obtainable in similar runtime on the entire instance. We devise
and investigate a variety of decomposition strategies in terms of the number
and size of time windows as well as heuristics for choosing their operations.
Moreover, we incorporate time window overlapping and compression techniques
into the iterative scheduling process to counteract window-wise optimization
limitations restricted to partial schedules. Our experiments on JSP benchmark
sets of several sizes show that successive optimization by multi-shot ASP
solving leads to substantially better schedules within the runtime limit than
global optimization on the full problem, where the gap increases with the
number of operations to schedule. While the obtained solution quality still
remains behind a state-of-the-art Constraint Programming system, our multi-shot
solving approach comes closer the larger the instance size, demonstrating good
scalability by problem decomposition.
- Abstract（参考訳）: ジョブショップスケジューリング問題(jsp:job-shop scheduling problem)は、マシンを共有するタスクをできるだけ早く処理できるような順序に配置する、よく知られた挑戦的な組合せ最適化問題である。
本稿では,マルチショット応答集合プログラミング (asp) による処理の逐次スケジュールと最適化が可能な時間窓への問題分解を提案する。
分解の目的は、高度に複雑なスケジューリングタスクを、バランスのとれた操作数で管理可能なサブプロブレムに分割することで、優れた品質や最適な部分的なソリューションを、少数のランタイムで確実に見つけることにある。
問題分解は、ジョブ内のオペレーションの優先順位を尊重する必要があり、時間によって最適化された部分スケジュールは、インスタンス全体の同様のランタイムで得られるよりも優れたグローバルソリューションをもたらすべきである。
時間ウィンドウの数とサイズ、およびそれらの操作を選択するためのヒューリスティックの観点から、様々な分解戦略を考案し、検討する。
さらに,時間窓重なりと圧縮を反復スケジューリングプロセスに組み込むことにより,部分スケジュールに制限されたウィンドウ毎の最適化制限を克服する。
複数のサイズのJSPベンチマークセットに対する実験により、マルチショットASPによる逐次最適化により、全問題におけるグローバルな最適化よりも実行時限界内でのスケジュールが大幅に改善されることが示された。
得られたソリューションの品質は、まだ最先端の制約プログラミングシステムの背後にあるが、我々のマルチショット解決アプローチは、より大きなインスタンスサイズに近づき、問題分解による優れたスケーラビリティを示す。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。
本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。
Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
論文 参考訳（メタデータ） (2023-12-28T23:15:18Z) - An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling
Problems Based on Constraint Programming [5.070542698701157]
本稿では,CPと強化学習(Reinforcement Learning, RL)を用いてスケジューリング問題を解決する新しいエンドツーエンドアプローチを提案する。
当社のアプローチでは,既存のCPソルバを活用して,プライオリティ・ディスパッチ・ルール(PDR)を学ぶエージェントをトレーニングする。
論文 参考訳（メタデータ） (2023-06-09T08:24:56Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳（メタデータ） (2023-05-26T15:13:09Z) - Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep
Learning Method [44.4747903763245]
ジョブショップスケジューリング問題(Jobs shop Scheduling Problem、JSP)は、様々な産業目的のために日常的に解決される標準最適化問題である。
問題はNPハードであり、中規模のインスタンスでも計算が困難である。
本稿では,問題に対する効率的かつ正確な近似を提供するためのディープラーニングアプローチについて検討する。
論文 参考訳（メタデータ） (2021-10-12T21:15:19Z) - Generalized Conflict-directed Search for Optimal Ordering Problems [18.231677739397973]
本稿では,イベントの全順序を最適に生成する分枝順序付け法GCDOを提案する。
汎用的な紛争を推論する能力があるため、GCDOは以前の競合指向アプローチCDITOよりも高品質の総注文を見つけるのにはるかに効率的です。
論文 参考訳（メタデータ） (2021-03-31T18:46:48Z) - 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) - Solving a Multi-resource Partial-ordering Flexible Variant of the
Job-shop Scheduling Problem with Hybrid ASP [0.4511923587827302]
我々は、MPF-JSS(Multi-resource Partial-ordering Flexible Job-shop Scheduling)問題を検討する。
リソースは柔軟性があり、その特性に応じて1つ以上の操作を実行できる。
中規模半導体故障解析ラボから抽出された一組のインスタンスについて実験した結果,本手法は実世界の91インスタンス中87のスケジュールを見出すことができた。
論文 参考訳（メタデータ） (2021-01-25T15:21:32Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。