論文の概要: Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method

• arxiv url: http://arxiv.org/abs/2110.06365v1
• Date: Tue, 12 Oct 2021 21:15:19 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-14 13:39:05.568558
• Title: Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method
• Title（参考訳）: ジョブショップスケジューリングのための高速近似:ラグランジアン二重ディープラーニング法
• Authors: James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck
• Abstract要約: ジョブショップスケジューリング問題(Jobs shop Scheduling Problem、JSP)は、様々な産業目的のために日常的に解決される標準最適化問題である。 問題はNPハードであり、中規模のインスタンスでも計算が困難である。 本稿では,問題に対する効率的かつ正確な近似を提供するためのディープラーニングアプローチについて検討する。
• 参考スコア（独自算出の注目度）: 44.4747903763245
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Jobs shop Scheduling Problem (JSP) is a canonical combinatorial optimization problem that is routinely solved for a variety of industrial purposes. It models the optimal scheduling of multiple sequences of tasks, each under a fixed order of operations, in which individual tasks require exclusive access to a predetermined resource for a specified processing time. The problem is NP-hard and computationally challenging even for medium-sized instances. Motivated by the increased stochasticity in production chains, this paper explores a deep learning approach to deliver efficient and accurate approximations to the JSP. In particular, this paper proposes the design of a deep neural network architecture to exploit the problem structure, its integration with Lagrangian duality to capture the problem constraints, and a post-processing optimization to guarantee solution feasibility.The resulting method, called JSP-DNN, is evaluated on hard JSP instances from the JSPLIB benchmark library. Computational results show that JSP-DNN can produce JSP approximations of high quality at negligible computational costs.
• Abstract（参考訳）: ジョブスショップスケジューリング問題(Jobs shop Scheduling Problem、JSP)は、様々な産業目的のために日常的に解決される標準組合せ最適化問題である。 特定の処理時間に対して、個々のタスクが所定のリソースへの排他的アクセスを必要とする固定順序の操作の下で、複数のタスクシーケンスの最適スケジューリングをモデル化する。 問題はnpハードで、中規模のインスタンスでも計算が難しい。 本稿では,生産チェーンの確率性の向上を動機として,JSPに効率的かつ正確な近似を提供するためのディープラーニングアプローチを提案する。 特に,問題構造を利用するディープニューラルネットワークアーキテクチャの設計,問題制約を捉えるためのラグランジアン双対性の統合,および解の実現性を保証するための後処理最適化を提案する。JSPLIBベンチマークライブラリのハードJSPインスタンス上でJSP-DNNと呼ばれる手法が評価されている。 計算結果から、JSP-DNNは無視可能な計算コストで高い品質のJSP近似を生成できることが示された。

関連論文リスト

• Developing an Algorithm Selector for Green Configuration in Scheduling Problems [0.8151943266391491]
  ジョブショップスケジューリング問題(JSP)は、業務研究の中心である。 ジョブショップスケジューリング問題(JSP)は、業務研究の中心である。
  論文  参考訳（メタデータ） (2024-09-13T08:58:24Z)
• Learning to Solve Job Shop Scheduling under Uncertainty [1.3002317221601185]
  ジョブショップスケジューリング問題(JSSP、Job-Shop Scheduling Problem)は、タスクをマシン上でスケジュールする必要がある最適化問題である。 本稿では,Dreep Reinforcement Learning (DRL) 技術を利用してロバストなソリューションを探索する手法を提案する。
  論文  参考訳（メタデータ） (2024-03-04T08:38:55Z)
• Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem [8.398387430247201]
  ジョブショップスケジューリング問題(Job-shop scheduling problem、JSP)は、製造業などで広く使われている数学最適化問題である。 本稿では,FJSPの解法に対する残差スケジューリングという新しい手法を提案する。 20台のマシンで150以上のジョブ数を持つ50のインスタンスで49のギャップに到達しています。
  論文  参考訳（メタデータ） (2023-09-27T09:33:56Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
  論文  参考訳（メタデータ） (2023-09-02T11:01:16Z)
• Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning [73.19312285906891]
  フレキシブルなジョブショップスケジューリング問題(FJSP)では、複数のマシンで操作を処理でき、操作とマシンの間の複雑な関係が生じる。 近年, 深層強化学習(DRL)を用いて, FJSP解決のための優先派遣規則(PDR)を学習している。 本稿では,Deep機能抽出のための自己注意モデルと,スケーラブルな意思決定のためのDRLの利点を生かした,エンドツーエンド学習フレームワークを提案する。
  論文  参考訳（メタデータ） (2023-05-09T01:35:48Z)
• A Reinforcement Learning Approach for Scheduling Problems With Improved Generalization Through Order Swapping [0.0]
  JSSP は NP-hard COP のカテゴリに分類される。 近年,COPの解法にDRLを用いる研究が注目され,解の質や計算効率の面で有望な結果が示されている。 特に、制約されたジョブのディスパッチにおいてよく機能すると考えられるポリシ・グラディエントパラダイムを採用するPPOアルゴリズムを採用する。
  論文  参考訳（メタデータ） (2023-02-27T16:45:04Z)
• Two-Stage Learning For the Flexible Job Shop Scheduling Problem [18.06058556156014]
  本稿では,フレキシブルジョブショップスケジューリング問題に対して,ディープラーニングフレームワークを用いて高速かつ正確な近似を生成する可能性について検討する。 本稿では,FJSP決定の階層的性質を明示的にモデル化する2段階学習フレームワークを提案する。 その結果、2SL-FJSPはミリ秒で高品質なソリューションを生成でき、最先端の強化学習手法よりも優れていることがわかった。
  論文  参考訳（メタデータ） (2023-01-23T20:23:35Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。 $nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2021-12-01T22:55:23Z)
• 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)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。