論文の概要: Integrated Offline and Online Learning to Solve a Large Class of Scheduling Problems

• arxiv url: http://arxiv.org/abs/2501.04253v1
• Date: Wed, 08 Jan 2025 03:35:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-09 14:56:23.802094
• Title: Integrated Offline and Online Learning to Solve a Large Class of Scheduling Problems
• Title（参考訳）: 大規模スケジューリング問題の解決のためのオフライン統合とオンライン学習
• Authors: Anbang Liu, Zhi-Long Chen, Jinyang Jiang, Xi Chen,
• Abstract要約: 我々は、単一マシンスケジューリング問題に対する高品質なソリューションを予測するために、統合機械学習(ML)アプローチを開発する。 我々は、考慮された問題のクラス全体がタイムインデックスの定式化として定式化できるという事実を活用する。 これらの問題のNPハードの性質を考えると、ラベル(すなわち最適解)は訓練のために生成し難い。
• 参考スコア（独自算出の注目度）: 5.36210189158563
• License:
• Abstract: In this paper, we develop a unified machine learning (ML) approach to predict high-quality solutions for single-machine scheduling problems with a non-decreasing min-sum objective function with or without release times. Our ML approach is novel in three major aspects. First, our approach is developed for the entire class of the aforementioned problems. To achieve this, we exploit the fact that the entire class of the problems considered can be formulated as a time-indexed formulation in a unified manner. We develop a deep neural network (DNN) which uses the cost parameters in the time-indexed formulation as the inputs to effectively predict a continuous solution to this formulation, based on which a feasible discrete solution is easily constructed. The second novel aspect of our approach lies in how the DNN model is trained. In view of the NP-hard nature of the problems, labels (i.e., optimal solutions) are hard to generate for training. To overcome this difficulty, we generate and utilize a set of special instances, for which optimal solutions can be found with little computational effort, to train the ML model offline. The third novel idea we employ in our approach is that we develop an online single-instance learning approach to fine tune the parameters in the DNN for a given online instance, with the goal of generating an improved solution for the given instance. To this end, we develop a feasibility surrogate that approximates the objective value of a given instance as a continuous function of the outputs of the DNN, which then enables us to derive gradients and update the learnable parameters in the DNN. Numerical results show that our approach can efficiently generate high-quality solutions for a variety of single-machine scheduling min-sum problems with up to 1000 jobs.
• Abstract（参考訳）: 本稿では, 単機スケジューリング問題に対して, 非減少最小目的関数をリリース時間の有無で予測する, 統一機械学習(ML)アプローチを開発する。 MLアプローチは3つの大きな側面において新規です。 まず,上記の問題のクラス全体を対象として,本手法を開発した。 これを達成するために、検討された問題のクラス全体が、統一された方法でタイムインデックス化された定式化として定式化できるという事実を利用する。 本研究では,時間差分定式化におけるコストパラメータを入力として用いて,この定式化に対する連続解を効果的に予測するディープニューラルネットワーク(DNN)を開発した。 このアプローチの第2の斬新な側面は、DNNモデルのトレーニング方法にあります。 これらの問題のNPハードの性質を考えると、ラベル(すなわち最適解)は訓練のために生成し難い。 この難しさを克服するために、私たちは、MLモデルをオフラインでトレーニングするために、計算の少ない最適解を見つけることのできる、一連の特別なインスタンスを生成し、利用します。 私たちがアプローチで採用している3つ目の新しいアイデアは、あるオンラインインスタンスに対してDNNのパラメータを微調整する、オンラインの単一インスタンス学習アプローチを開発することです。 この目的のために、DNNの出力の連続関数として与えられたインスタンスの目的値を近似した実現可能性サロゲートを開発し、それによってDNNの勾配を導出し、学習可能なパラメータを更新することができる。 計算結果から, 最大1000ジョブの単一マシンスケジューリング min-sum 問題に対して, 高品質な解を効率よく生成できることが示唆された。

関連論文リスト

• Towards An Unsupervised Learning Scheme for Efficiently Solving Parameterized Mixed-Integer Programs [6.1860817947800655]
  教師なし学習方式でバイナリ変数の自動エンコーダを訓練する。 オフライン学習AEのデコーダパラメータから平面制約を切断するクラスを構築する戦略を提案する。 原始的なMIP問題への統合は、実現可能な領域を縮小したMIPの強化につながる。
  論文  参考訳（メタデータ） (2024-12-23T14:48:32Z)
• Optimization Proxies using Limited Labeled Data and Training Time -- A Semi-Supervised Bayesian Neural Network Approach [2.943640991628177]
  制約のある最適化問題は、在庫管理電力グリッドのような様々なエンジニアリングシステムで発生する。 本研究では,ベイジアンネットワーク(BNN)を用いて,制限されたデータと制限されたモデル時間の下での制約付き最適化問題の解法を提案する。 提案手法は,従来のBNNおよびディープニューラルネットワーク(DNN)アーキテクチャよりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-04T02:10:20Z)
• Machine Learning and Constraint Programming for Efficient Healthcare Scheduling [0.8287206589886879]
  看護スケジューリング問題(NSP)に取り組む 暗黙の問題解決アプローチでは、学習パターンに埋め込まれる可能性のある制約や目的を通じて、過去のデータを使って新しいソリューションを学習し、生成する機械学習手法を頼りにしています。 提案手法では, 制約や目的が具体的に見えるものではないことを考慮し, 暗黙的アプローチに関する不確実性を補うために, 制約満足度問題フレームワークを用いてまずNSPをモデル化する明示的アプローチを提案する。 我々の暗黙的アプローチは生成したソリューションの実現可能性や最適性を保証するものではないため、データ駆動型アプローチを提案し、NSPを制約として受動的に学習する。
  論文  参考訳（メタデータ） (2024-09-11T18:09:25Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
  論文  参考訳（メタデータ） (2023-09-02T11:01:16Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
  混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。 近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。 本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
  論文  参考訳（メタデータ） (2022-02-07T18:52:56Z)
• RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
  入力出力クエリの静的データセットからブラックボックス目的関数を最大化する入力を探索する問題を考える。 この問題を解決するための一般的なアプローチは、真の客観的関数を近似するプロキシモデルを維持することである。 ここでの大きな課題は、検索中に逆最適化された入力を避ける方法である。
  論文  参考訳（メタデータ） (2021-10-27T05:37:12Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。 本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
  論文  参考訳（メタデータ） (2020-04-30T01:50:37Z)

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

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