論文の概要: Two-Stage Learning For the Flexible Job Shop Scheduling Problem
- arxiv url: http://arxiv.org/abs/2301.09703v1
- Date: Mon, 23 Jan 2023 20:23:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-25 14:58:20.807052
- Title: Two-Stage Learning For the Flexible Job Shop Scheduling Problem
- Title(参考訳): フレキシブルなジョブショップスケジューリング問題の2段階学習
- Authors: Wenbo Chen, Reem Khir and Pascal Van Hentenryck
- Abstract要約: 本稿では,フレキシブルジョブショップスケジューリング問題に対して,ディープラーニングフレームワークを用いて高速かつ正確な近似を生成する可能性について検討する。
本稿では,FJSP決定の階層的性質を明示的にモデル化する2段階学習フレームワークを提案する。
その結果、2SL-FJSPはミリ秒で高品質なソリューションを生成でき、最先端の強化学習手法よりも優れていることがわかった。
- 参考スコア(独自算出の注目度): 18.06058556156014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Flexible Job-shop Scheduling Problem (FJSP) is an important combinatorial
optimization problem that arises in manufacturing and service settings. FJSP is
composed of two subproblems, an assignment problem that assigns tasks to
machines, and a scheduling problem that determines the starting times of tasks
on their chosen machines. Solving FJSP instances of realistic size and
composition is an ongoing challenge even under simplified, deterministic
assumptions. Motivated by the inevitable randomness and uncertainties in supply
chains, manufacturing, and service operations, this paper investigates the
potential of using a deep learning framework to generate fast and accurate
approximations for FJSP. In particular, this paper proposes a two-stage
learning framework 2SLFJSP that explicitly models the hierarchical nature of
FJSP decisions, uses a confidence-aware branching scheme to generate
appropriate instances for the scheduling stage from the assignment predictions
and leverages a novel symmetry-breaking formulation to improve learnability.
2SL-FJSP is evaluated on instances from the FJSP benchmark library. Results
show that 2SL-FJSP can generate high-quality solutions in milliseconds,
outperforming a state-of-the-art reinforcement learning approach recently
proposed in the literature, and other heuristics commonly used in practice.
- Abstract(参考訳): フレキシブルジョブショップスケジューリング問題(FJSP)は、製造やサービス設定で発生する重要な組合せ最適化問題である。
FJSPは2つのサブプロブレムと、タスクをマシンに割り当てる代入問題と、選択したマシン上のタスクの開始時間を決定するスケジューリング問題で構成される。
fjspインスタンスの現実的なサイズと構成の解決は、シンプルで決定論的仮定の下でも進行中の課題である。
本稿では,サプライチェーン,製造,サービス運用における必然的ランダム性と不確実性から,FJSPの高速かつ正確な近似を生成するためのディープラーニングフレームワークの可能性について検討する。
特に,fjsp決定の階層的性質を明示的にモデル化する2段階学習フレームワーク2slfjspを提案し,信頼度に着目した分岐スキームを用いて割り当て予測からスケジューリングステージの適切なインスタンスを生成し,新しい対称性を破る定式化を利用して学習可能性を向上させる。
2SL-FJSPは、FJSPベンチマークライブラリのインスタンスで評価される。
その結果、2SL-FJSPはミリ秒で高品質なソリューションを生成でき、最近論文で提案された最先端の強化学習手法と、実際に一般的に用いられている他のヒューリスティックスよりも優れていることがわかった。
関連論文リスト
- Decoupled Adversarial Contrastive Learning for Self-supervised
Adversarial Robustness [69.39073806630583]
頑健な表現学習のための対人訓練(AT)と教師なし表現学習のための自己教師型学習(SSL)は2つの活発な研究分野である。
Decoupled Adversarial Contrastive Learning (DeACL) と呼ばれる2段階のフレームワークを提案する。
論文 参考訳(メタデータ) (2022-07-22T06:30:44Z) - Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
我々は構造化出力予測(SOP)のための予測層を設計する。
予測が事前に定義されたシンボリック制約のセットと一致していることを保証するため、任意のニューラルネットワークにプラグインすることができる。
我々のセマンティック確率層(SPL)は、構造化された出力空間上で複雑な相関や制約をモデル化することができる。
論文 参考訳(メタデータ) (2022-06-01T12:02:38Z) - Neur2SP: Neural Two-Stage Stochastic Programming [3.5417030119735045]
我々はニューラルネットワークを介して期待値関数を近似する新しい方法Neur2SPを開発した。
Neur2SPはすべての問題に対して1.66秒未満で、シナリオの数が増えても高品質なソリューションを実現する。
論文 参考訳(メタデータ) (2022-05-20T22:09:22Z) - Hybrid intelligence for dynamic job-shop scheduling with deep
reinforcement learning and attention mechanism [28.28095225164155]
我々は、DJSPをマルコフ決定過程(MDP)として定式化し、強化学習(RL)に対処する。
本稿では,分割グラフを状態とするフレキシブルなハイブリッドフレームワークを提案する。
我々は、有名なOR-Libraryに基づく公開ベンチマークであるGymjspを紹介し、RLおよびDJSP研究コミュニティのための標準化されたオフザシェルフ施設を提供する。
論文 参考訳(メタデータ) (2022-01-03T09:38:13Z) - An actor-critic algorithm with deep double recurrent agents to solve the
job shop scheduling problem [0.0]
ジョブショップスケジューリング問題(JSSP)に対する深層強化学習手法を提案する。
目的は、ジョブやマシンの数によって異なるJSSPインスタンスのディストリビューションについて学べるgreedyのようなものを構築することである。
予想通り、モデルはある程度は、トレーニングで使用されるものと異なる分布から生じるより大きな問題やインスタンスに一般化することができる。
論文 参考訳(メタデータ) (2021-10-18T07:55:39Z) - 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) - 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) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep
Reinforcement Learning [102.78958681141577]
SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。
SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
論文 参考訳(メタデータ) (2020-07-09T17:08:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。