論文の概要: A new neighborhood structure for job shop scheduling problems

• arxiv url: http://arxiv.org/abs/2109.02843v1
• Date: Tue, 7 Sep 2021 03:52:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-08 14:41:28.359596
• Title: A new neighborhood structure for job shop scheduling problems
• Title（参考訳）: ジョブショップスケジューリング問題に対する新しい近隣構造
• Authors: Jin Xie, Xinyu Li, Liang Gao, Lin Gui
• Abstract要約: ジョブショップスケジューリング問題(JSP)はNP完全最適化問題として広く研究されている。 既存の地区構造は、臨界ブロック内での臨界操作の移動のみを考慮したものである。 本稿では, 臨界ブロック外における臨界操作の移動を考慮した新しいN8地区構造を提案する。
• 参考スコア（独自算出の注目度）: 18.722173824986307
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Job shop scheduling problem (JSP) is a widely studied NP-complete combinatorial optimization problem. Neighborhood structures play a critical role in solving JSP. At present, there are three state-of-the-art neighborhood structures, i.e., N5, N6, and N7. Improving the upper bounds of some famous benchmarks is inseparable from the role of these neighborhood structures. However, these existing neighborhood structures only consider the movement of critical operations within a critical block. According to our experiments, it is also possible to improve the makespan of a scheduling scheme by moving a critical operation outside its critical block. According to the above finding, this paper proposes a new N8 neighborhood structure considering the movement of critical operations within a critical block and the movement of critical operations outside the critical block. Besides, a neighborhood clipping method is designed to avoid invalid movement, reducing the computational time. Tabu search (TS) is a commonly used algorithm framework combined with neighborhood structures. This paper uses this framework to compare the N8 neighborhood structure with N5, N6, and N7 neighborhood structures on four famous benchmarks. The experimental results verify that the N8 neighborhood structure is more effective and efficient in solving JSP than the other state-of-the-art neighborhood structures.
• Abstract（参考訳）: ジョブショップスケジューリング問題(JSP)はNP完全組合せ最適化問題として広く研究されている。 近隣構造はJSPの解決に重要な役割を果たしている。 現在、最先端の3つの近傍構造、すなわちN5、N6、N7が存在する。 いくつかの有名なベンチマークの上界を改善することは、これらの近傍構造の役割とは区別できない。 しかし、これらの既存の近傍構造は臨界ブロック内の臨界演算の移動のみを考慮する。 また,本実験では,クリティカルブロックの外にクリティカル操作を移動させることにより,スケジューリング方式の整合性を向上させることができる。 そこで本研究では,臨界ブロック内における臨界操作の移動と臨界ブロック外における臨界操作の移動を考慮した新しいN8地区構造を提案する。 また,不正な動きを回避し,計算時間を短縮する近傍クリッピング法を考案した。 Tabu Search(TS)は、近隣構造と組み合わせたアルゴリズムフレームワークである。 本稿では,N8近傍構造とN5,N6,N7近傍構造を4つの有名なベンチマークで比較する。 実験の結果, n8近傍構造は他の最先端の近傍構造よりも効率的にjspを解くことが確認された。

関連論文リスト

• Hierarchical Neural Constructive Solver for Real-world TSP Scenarios [27.986011761759567]
  本稿では,産業環境に関連する現実的なトラベリングセールスマン問題(TSP)について紹介する。 我々の階層的アプローチは、古典的モデルと最近のトランスモデルの両方と比較して優れたパフォーマンスをもたらす。
  論文  参考訳（メタデータ） (2024-08-07T06:44:47Z)
• TFNet: Tuning Fork Network with Neighborhood Pixel Aggregation for Improved Building Footprint Extraction [11.845097068829551]
  深層セマンティックセグメンテーションのための新しいチューニングフォークネットワーク(TFNet)の設計を提案する。 TFNetの設計は、トレーニングプロセス中にタイル境界に周辺情報を組み込む新しい手法と組み合わせられている。 パフォーマンス比較では、SpaceNet2とWHUのデータセットと、密接な接続された建物をキャプチャするパキスタンのラホールのエリアからのデータセットを使用します。
  論文  参考訳（メタデータ） (2023-11-05T10:52:16Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• GNAS: A Generalized Neural Network Architecture Search Framework [0.0]
  実際には、nas(neural architecture search)のトレーニングで発生する問題は単純ではないが、いくつかの困難の組み合わせがしばしば直面する。 本論文では,NASの単一問題のみを解決するこれまでの研究の参考と改善を行い,それを実用的技術フローに組み合わせる。
  論文  参考訳（メタデータ） (2021-03-19T06:51:22Z)
• Learning Diverse-Structured Networks for Adversarial Robustness [143.3451672724794]
  本稿では,検索空間のサイズを大幅に削減する多様構造ネットワーク(DS-Net)を提案する。 低レベルの操作の代わりに、原子ブロックがタイムテストされたビルディングブロックである、事前定義された原子ブロックのみを考慮する。 アトミックブロックは数ブロックしかないので、DS-Netの検索ブロックで最高のブロックを見つけるのではなく、全てのアトミックブロックを重み付けることができる。
  論文  参考訳（メタデータ） (2021-02-03T05:52:11Z)
• Should Graph Convolution Trust Neighbors? A Simple Causal Inference Method [114.48708191371524]
  グラフ畳み込みネットワーク(GCN)は情報検索(IR)アプリケーションのための新興技術である。 この研究は、ほとんど精査されていないテストノードの局所的な構造差に焦点を当てている。 本稿では,GCNの動作メカニズムを因果グラフを用いて解析し,ノードの局所構造による因果効果を推定する。
  論文  参考訳（メタデータ） (2020-10-22T15:21:47Z)
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods [77.34726150561087]
  本研究では,階層型コミュニティ検出の効率向上のために,局所構造ネットワーク特性をプロキシとして利用する方法について検討する。 また,ネットワークプルーニングの性能への影響を,階層的コミュニティ検出をより効率的にするための補助的手法として検証する。
  論文  参考訳（メタデータ） (2020-09-15T00:16:12Z)
• Tree Optimization Based Heuristics and Metaheuristics in Network Construction Problems [0.0]
  本稿では,建設作業員が交通ネットワークのエッジを構築する必要のある,近年導入されたネットワーク構築問題について考察する。 各種の利害関係が動作した時の非減少機能を最小限に抑える建設スケジュールを見つける必要がある。 木質効率のよいネットワーク構築問題の解法として,汎用的な局所探索手法と2つのメタヒューリスティック手法を開発した。
  論文  参考訳（メタデータ） (2020-07-03T18:40:45Z)
• Neighborhood Matching Network for Entity Alignment [71.24217694278616]
  Neighborhood Matching Network (NMN)は、新しいエンティティアライメントフレームワークである。 NMNは、トポロジカル構造と近傍差の両方を捉えるために、エンティティ間の類似性を推定する。 まず、新しいグラフサンプリング法を用いて、各エンティティの識別的近傍を蒸留する。 その後、クロスグラフの近傍マッチングモジュールを採用し、与えられたエンティティペアの近傍差を共同で符号化する。
  論文  参考訳（メタデータ） (2020-05-12T08:26:15Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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