論文の概要: Data-driven Algorithm for Scheduling with Total Tardiness
- arxiv url: http://arxiv.org/abs/2005.05579v1
- Date: Tue, 12 May 2020 07:16:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-03 18:14:30.746650
- Title: Data-driven Algorithm for Scheduling with Total Tardiness
- Title（参考訳）: トータルターゲットを考慮したデータ駆動型スケジューリングアルゴリズム
- Authors: Michal Bou\v{s}ka, Anton\'in Nov\'ak, P\v{r}emysl \v{S}\r{u}cha,
Istv\'an M\'odos, and Zden\v{e}k Hanz\'alek
- Abstract要約: 本稿では,古典的なNP-Hard単一マシンスケジューリング問題に対するディープラーニングの適用について検討する。
我々は、与えられたジョブセットの基準を学習し、予測するディープニューラルネットワークを含む回帰器を設計した。
データ駆動型アプローチは、トレーニングフェーズからかなり大きなインスタンスへの情報を効率的に一般化することができます。
- 参考スコア（独自算出の注目度）: 0.6606016007748989
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we investigate the use of deep learning for solving a
classical NP-Hard single machine scheduling problem where the criterion is to
minimize the total tardiness. Instead of designing an end-to-end machine
learning model, we utilize well known decomposition of the problem and we
enhance it with a data-driven approach. We have designed a regressor containing
a deep neural network that learns and predicts the criterion of a given set of
jobs. The network acts as a polynomial-time estimator of the criterion that is
used in a single-pass scheduling algorithm based on Lawler's decomposition
theorem. Essentially, the regressor guides the algorithm to select the best
position for each job. The experimental results show that our data-driven
approach can efficiently generalize information from the training phase to
significantly larger instances (up to 350 jobs) where it achieves an optimality
gap of about 0.5%, which is four times less than the gap of the
state-of-the-art NBR heuristic.
- Abstract（参考訳）: 本稿では,従来のnp-hard single machine scheduling問題を解くためのディープラーニングの利用について検討する。
エンド・ツー・エンドの機械学習モデルを設計する代わりに、よく知られた問題を分解し、データ駆動アプローチで強化する。
我々は、与えられたジョブセットの基準を学習し、予測するディープニューラルネットワークを含む回帰器を設計した。
このネットワークは、ローラーの分解定理に基づく単一パススケジューリングアルゴリズムで使用される基準の多項式時間推定器として機能する。
基本的に、回帰器はアルゴリズムを誘導し、各ジョブに最適な位置を選択する。
実験結果から,データ駆動型アプローチは,トレーニングフェーズから大幅に大きなインスタンス(最大350ジョブ)への情報を効率的に一般化でき,最適なギャップは約0.5%であり,最先端のnbrヒューリスティックのギャップの4分の4以下であることがわかった。
関連論文リスト
- Deep learning-driven scheduling algorithm for a single machine problem
minimizing the total tardiness [0.0]
単一パススケジューリングアルゴリズムで用いられる基準値の分解時間推定器として機能するディープニューラルネットワークを提案する。
機械学習によるアプローチは、トレーニングフェーズからかなり大きなインスタンスへの情報を効率的に一般化できることを示します。
論文 参考訳（メタデータ） (2024-02-19T15:34:09Z) - Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。
私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。
以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
論文 参考訳（メタデータ） (2023-05-18T13:59:02Z) - 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) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。
SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。
本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。
ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文 参考訳（メタデータ） (2021-09-13T18:10:52Z) - Learning to Hash Robustly, with Guarantees [79.68057056103014]
本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。
理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。
我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
論文 参考訳（メタデータ） (2021-08-11T20:21:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Continual Learning using a Bayesian Nonparametric Dictionary of Weight
Factors [75.58555462743585]
訓練されたニューラルネットワークは、シーケンシャルなタスク設定で破滅的な忘れを経験する傾向がある。
Indian Buffet Process (IBP) に基づく原則的非パラメトリック手法を提案する。
連続学習ベンチマークにおける本手法の有効性を実証し、トレーニングを通して重み要因の配分と再利用方法を分析する。
論文 参考訳（メタデータ） (2020-04-21T15:20:19Z) - Fast local linear regression with anchor regularization [21.739281173516247]
高速アンカー正規化局所線形法(FALL)と呼ばれる,単純で効果的な局所モデルトレーニングアルゴリズムを提案する。
合成および実世界のデータセットの実験を通じて、FALLは最先端のネットワークLassoアルゴリズムと精度の面で好適に比較できることを示した。
論文 参考訳（メタデータ） (2020-02-21T10:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。