論文の概要: Comprehensive Benchmarking Environment for Worker Flexibility in Flexible Job Shop Scheduling Problems
- arxiv url: http://arxiv.org/abs/2501.16159v1
- Date: Mon, 27 Jan 2025 15:56:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-28 13:58:58.375983
- Title: Comprehensive Benchmarking Environment for Worker Flexibility in Flexible Job Shop Scheduling Problems
- Title(参考訳): フレキシブルジョブショップスケジューリング問題における作業者フレキシビリティの総合的ベンチマーク環境
- Authors: David Hutter, Thomas Steinberger, Michael Hellwig,
- Abstract要約: 生産スケジューリングにおいて、フレキシブルジョブショップスケジューリング問題(FJSSP)は、一連の操作を最適化し、それぞれの処理時間を異なるマシンに割り当てることを目的としている。
結果として生じる問題はFlexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W)と呼ばれる。
本稿では、一般に受け入れられているFJSSPインスタンス402のコレクションを示し、労働者の柔軟性で拡張するアプローチを提案する。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: In Production Scheduling, the Flexible Job Shop Scheduling Problem (FJSSP) aims to optimize a sequence of operations and assign each to an eligible machine with varying processing times. For integration of the workforce, each machine also requires a worker to be present to process an operation which additionally affects the processing times. The resulting problem is called Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W). The FJSSP has been approached with various problem representations, including Mixed Integer Linear Programming (MILP), Constrained Programming (CP), and Simulation-based Optimization (SBO). In the latter area in particular, there exists a large number of specialized Evolutionary Algorithms (EA) like Particle Swarm Optimization (PSO) or Genetic Algorithms (GA). Yet, the solvers are often developed for single use cases only, and validated on a few selected test instances, let alone compared with results from solvers using other problem representations. While suitable approaches do also exist, the design of the FJSSP-W instances is not standardized and the algorithms are hardly comparable. This calls for a systematic benchmarking environment that provides a comprehensive set of FJSSP(-W) instances and supports targeted algorithm development. It will facilitate the comparison of algorithmic performance in the face of different problem characteristics. The present paper presents a collection of 402 commonly accepted FJSSP instances and proposes an approach to extend these with worker flexibility. In addition, we present a detailed procedure for the evaluation of scheduling algorithms on these problem sets and provide suitable model representations for this purpose. We provide complexity characteristics for all presented instances as well as baseline results of common commercial solvers to facilitate the validation of new algorithmic developments.
- Abstract(参考訳): 生産スケジューリングにおいて、フレキシブルジョブショップスケジューリング問題(FJSSP)は、一連の操作を最適化し、それぞれの処理時間を異なるマシンに割り当てることを目的としている。
作業員の統合には、各機械が作業時間にさらに影響を及ぼす操作を行うために作業員を配置する必要がある。
結果として生じる問題はFlexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W)と呼ばれる。
FJSSPは、MILP(Mixed Integer Linear Programming)、CP(Constrained Programming)、シミュレーションベースの最適化(SBO)など、様々な問題表現でアプローチされてきた。
特に後者の領域では、Particle Swarm Optimization (PSO) や Genetic Algorithms (GA) のような専門的な進化的アルゴリズム (EA) が多数存在する。
しかし、解法はしばしば単一のユースケースでのみ開発され、いくつかの選択されたテストインスタンスで検証される。
適切なアプローチも存在しているが、JSSP-Wインスタンスの設計は標準化されておらず、アルゴリズムはほとんど比較にならない。
これにより、JSSP(-W)インスタンスの包括的なセットを提供し、ターゲットとするアルゴリズム開発をサポートする、システマティックなベンチマーク環境が要求される。
異なる問題特性に直面したアルゴリズム性能の比較を容易にする。
本稿では、一般的なFJSSPインスタンス402のコレクションを提示し、労働者の柔軟性で拡張するアプローチを提案する。
さらに,これらの問題集合上でのスケジューリングアルゴリズムの評価を行うための詳細な手順を提案し,その目的に適したモデル表現を提供する。
提案する全インスタンスの複雑性特性と,新しいアルゴリズム開発の検証を容易にするために,共通商用解決器のベースライン結果を提供する。
関連論文リスト
- Federated Conditional Stochastic Optimization [110.513884892319]
条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。
本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-10-04T01:47:37Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳(メタデータ) (2023-05-26T15:13:09Z) - Flexible Job Shop Scheduling via Dual Attention Network Based
Reinforcement Learning [73.19312285906891]
フレキシブルなジョブショップスケジューリング問題(FJSP)では、複数のマシンで操作を処理でき、操作とマシンの間の複雑な関係が生じる。
近年, 深層強化学習(DRL)を用いて, FJSP解決のための優先派遣規則(PDR)を学習している。
本稿では,Deep機能抽出のための自己注意モデルと,スケーラブルな意思決定のためのDRLの利点を生かした,エンドツーエンド学習フレームワークを提案する。
論文 参考訳(メタデータ) (2023-05-09T01:35:48Z) - Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling [7.977161233209228]
ジョブショップスケジューリング問題(JSP、Job-shop Scheduling Problem)は、ジョブを含むタスクをできるだけ早く完了するように、マシンを共有するタスクをシーケンスに配置する、よく知られた、困難な最適化問題である。
本稿では,ASP(Multi-shot Answer Set Programming)の解法を用いて,操作を逐次スケジュールし,最適化可能な時間窓への問題分解について検討する。
論文 参考訳(メタデータ) (2022-05-16T09:33:00Z) - Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep
Learning Method [44.4747903763245]
ジョブショップスケジューリング問題(Jobs shop Scheduling Problem、JSP)は、様々な産業目的のために日常的に解決される標準最適化問題である。
問題はNPハードであり、中規模のインスタンスでも計算が困難である。
本稿では,問題に対する効率的かつ正確な近似を提供するためのディープラーニングアプローチについて検討する。
論文 参考訳(メタデータ) (2021-10-12T21:15:19Z) - 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) - Solving a Multi-resource Partial-ordering Flexible Variant of the
Job-shop Scheduling Problem with Hybrid ASP [0.4511923587827302]
我々は、MPF-JSS(Multi-resource Partial-ordering Flexible Job-shop Scheduling)問題を検討する。
リソースは柔軟性があり、その特性に応じて1つ以上の操作を実行できる。
中規模半導体故障解析ラボから抽出された一組のインスタンスについて実験した結果,本手法は実世界の91インスタンス中87のスケジュールを見出すことができた。
論文 参考訳(メタデータ) (2021-01-25T15:21:32Z) - A global-local neighborhood search algorithm and tabu search for
flexible job shop scheduling problem [3.946442574906068]
この研究はGLNSA(Global-local neighborhood search algorithm)と呼ばれる新しいメタヒューリスティックアルゴリズムを提案する。
提案アルゴリズムは,Nopt1地区の簡易版を実装したタブ検索と補完する。
実験の結果,提案アルゴリズムの性能は,最近発表された他のアルゴリズムと比較すると良好であった。
論文 参考訳(メタデータ) (2020-10-23T23:08:51Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Metaheuristics for the Online Printing Shop Scheduling Problem [0.0]
この実際のスケジューリング問題は、現代の印刷業界で現れたもので、シークエンシングの柔軟性を備えたフレキシブルなジョブショップスケジューリング問題に対応している。
この問題に対する局所探索戦略とメタヒューリスティックアプローチを提案し,評価した。
フレキシブルなジョブショップスケジューリング問題における古典的事例を用いた数値実験により,本事例に適用した場合,導入手法も競争力を持つことが示された。
論文 参考訳(メタデータ) (2020-06-22T15:38:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。