論文の概要: Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness

• arxiv url: http://arxiv.org/abs/2402.14847v1
• Date: Mon, 19 Feb 2024 15:34:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-03 19:26:36.076198
• Title: Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness
• Title（参考訳）: 完全ターダネスを最小化する単一機械問題の深層学習型スケジューリングアルゴリズム
• Authors: Michal Bou\v{s}ka, P\v{r}emysl \v{S}\r{u}cha, Anton\'in Nov\'ak, Zden\v{e}k Hanz\'alek
• Abstract要約: 単一パススケジューリングアルゴリズムで用いられる基準値の分解時間推定器として機能するディープニューラルネットワークを提案する。 機械学習によるアプローチは、トレーニングフェーズからかなり大きなインスタンスへの情報を効率的に一般化できることを示します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we investigate the use of the deep learning method for solving a well-known NP-hard single machine scheduling problem with the objective of minimizing the total tardiness. We propose a deep neural network that acts as a polynomial-time estimator of the criterion value used in a single-pass scheduling algorithm based on Lawler's decomposition and symmetric decomposition proposed by Della Croce et al. Essentially, the neural network guides the algorithm by estimating the best splitting of the problem into subproblems. The paper also describes a new method for generating the training data set, which speeds up the training dataset generation and reduces the average optimality gap of solutions. The experimental results show that our machine learning-driven approach can efficiently generalize information from the training phase to significantly larger instances. Even though the instances used in the training phase have from 75 to 100 jobs, the average optimality gap on instances with up to 800 jobs is 0.26%, which is almost five times less than the gap of the state-of-the-art heuristic.
• Abstract（参考訳）: 本稿では,np-hard 単一マシンスケジューリング問題を解くための深層学習法について,全ターダネスを最小化することを目的として検討する。 della croceらによって提唱されたローラーの分解と対称分解に基づく単一パススケジューリングアルゴリズムで使用される基準値の多項式時間推定器として機能するディープニューラルネットワークを提案する。 本質的に、ニューラルネットワークは問題の最良の分割をサブプロブレムに推定することでアルゴリズムを導く。 また、トレーニングデータセットの生成を高速化し、ソリューションの平均最適性ギャップを減らし、トレーニングデータセットを生成する新しい方法についても述べる。 実験の結果,機械学習によるアプローチは,学習段階からはるかに大きなインスタンスへの情報を効率的に一般化できることがわかった。 トレーニングフェーズで使用されるインスタンスは75から100までだが、最大800ジョブのインスタンスの平均最適化ギャップは0.26%であり、最先端のヒューリスティックのギャップの約5倍である。

関連論文リスト

• Taking the human out of decomposition-based optimization via artificial intelligence: Part II. Learning to initialize [0.0]
  提案手法は解時間を大幅に短縮することができる。 アクティブかつ教師付き学習は、計算性能を予測する代理モデルを学ぶために使用される。 その結果,提案手法が解時間を大幅に短縮する可能性が示唆された。
  論文  参考訳（メタデータ） (2023-10-10T23:49:26Z)
• 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)
• Algorithms that Approximate Data Removal: New Results and Limitations [2.6905021039717987]
  本研究では,経験的リスク最小化を用いて学習した機械学習モデルからユーザデータを削除することの問題点について検討する。 計算とメモリ効率を両立させるオンラインアンラーニングアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-09-25T17:20:33Z)
• Federated Learning with a Sampling Algorithm under Isoperimetry [9.990687944474738]
  フェデレーション学習は、機械学習アルゴリズムのトレーニングを複数のデバイスに効率的に分散するために、一連のテクニックを使用する。 本稿では,Langevinvin のサンプル Aafteri の通信効率のよい変種を提案する。
  論文  参考訳（メタデータ） (2022-06-02T08:19:03Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Data-driven Algorithm for Scheduling with Total Tardiness [0.6606016007748989]
  本稿では,古典的なNP-Hard単一マシンスケジューリング問題に対するディープラーニングの適用について検討する。 我々は、与えられたジョブセットの基準を学習し、予測するディープニューラルネットワークを含む回帰器を設計した。 データ駆動型アプローチは、トレーニングフェーズからかなり大きなインスタンスへの情報を効率的に一般化することができます。
  論文  参考訳（メタデータ） (2020-05-12T07:16:43Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• Subset Sampling For Progressive Neural Network Learning [106.12874293597754]
  プログレッシブニューラルネットワーク学習は、ネットワークのトポロジを漸進的に構築し、トレーニングデータに基づいてパラメータを最適化するアルゴリズムのクラスである。 段階的なトレーニングステップ毎にトレーニングデータのサブセットを活用することで,このプロセスの高速化を提案する。 オブジェクト,シーン,顔の認識における実験結果から,提案手法が最適化手順を大幅に高速化することを示す。
  論文  参考訳（メタデータ） (2020-02-17T18:57:33Z)
• Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
  本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。 我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。 計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
  論文  参考訳（メタデータ） (2020-01-12T15:54:20Z)

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

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