論文の概要: Answer-Set Programming for Lexicographical Makespan Optimisation in
Parallel Machine Scheduling
- arxiv url: http://arxiv.org/abs/2212.09077v1
- Date: Sun, 18 Dec 2022 12:43:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-20 17:16:08.695554
- Title: Answer-Set Programming for Lexicographical Makespan Optimisation in
Parallel Machine Scheduling
- Title（参考訳）: 並列マシンスケジューリングにおけるレキシカルマインスパン最適化のためのアンサーセットプログラミング
- Authors: Thomas Eiter, Tobias Geibinger, Nysret Musliu, Johannes Oetsch, Peter
Skocovsky, Daria Stepanova
- Abstract要約: 我々は、シーケンス依存のセットアップ時間とリリース日を持つ並列マシン上で、困難なスケジューリング問題に対処する。
個々のマシンを非到達順に配置し、結果として生じるロバスト性を語彙的に最小化する。
実験の結果,ASPは実際にこの問題に対して有望なKRRパラダイムであり,最先端のCPおよびMIPソルバと競合していることがわかった。
- 参考スコア（独自算出の注目度）: 18.286430978487388
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We deal with a challenging scheduling problem on parallel machines with
sequence-dependent setup times and release dates from a real-world application
of semiconductor work-shop production. There, jobs can only be processed by
dedicated machines, thus few machines can determine the makespan almost
regardless of how jobs are scheduled on the remaining ones. This causes
problems when machines fail and jobs need to be rescheduled. Instead of
optimising only the makespan, we put the individual machine spans in
non-ascending order and lexicographically minimise the resulting tuples. This
achieves that all machines complete as early as possible and increases the
robustness of the schedule. We study the application of Answer-Set Programming
(ASP) to solve this problem. While ASP eases modelling, the combination of
timing constraints and the considered objective function challenges current
solving technology. The former issue is addressed by using an extension of ASP
by difference logic. For the latter, we devise different algorithms that use
multi-shot solving. To tackle industrial-sized instances, we study different
approximations and heuristics. Our experimental results show that ASP is indeed
a promising KRR paradigm for this problem and is competitive with
state-of-the-art CP and MIP solvers. Under consideration in Theory and Practice
of Logic Programming (TPLP).
- Abstract（参考訳）: 我々は, 半導体ワークショップ生産の実世界の応用から, シーケンス依存のセットアップ時間とリリース日を持つ並列マシンのスケジューリング問題に対処する。
そこでは、ジョブは専用のマシンでしか処理できないため、残りのマシンでどのようにジョブがスケジュールされているかに関わらず、マシンがメイスパンを決定することはほとんどない。
これはマシンが故障し、ジョブが再スケジュールされる必要がある場合に問題を引き起こす。
メースパンだけを最適化する代わりに、個々のマシンを非許容順序に分割し、結果として生じるタプルを語彙的に最小化する。
これにより、すべてのマシンが可能な限り早く完成し、スケジュールの堅牢性が向上する。
本稿では,この問題に対する解答集合プログラミング(asp)の応用について検討する。
aspはモデリングを容易にするが、タイミング制約と考慮対象関数の組み合わせは、現在の解決技術に挑戦する。
前者の問題は、差分ロジックによるASPの拡張によって解決される。
後者では、マルチショット解決を用いた異なるアルゴリズムを考案する。
産業規模の事例に取り組むため、異なる近似とヒューリスティックスを研究した。
実験の結果,ASPは実際にこの問題に対して有望なKRRパラダイムであり,最先端のCPおよびMIPソルバと競合していることがわかった。
論理プログラミングの理論と実践(tplp)における考察。
関連論文リスト
- Is the GPU Half-Empty or Half-Full? Practical Scheduling Techniques for LLMs [3.7758841366694353]
文献および実用サービスシステムからスケジューリング手法を調査する。
文献からのスケジューラは、しばしば優れたパフォーマンスを得るが、かなりの複雑さをもたらす。
対照的に、実際のデプロイメントにおけるスケジューラは、しばしばテーブルに簡単にパフォーマンス向上を残しますが、実装、デプロイ、設定が容易です。
論文 参考訳（メタデータ） (2024-10-23T13:05:46Z) - A mathematical model for simultaneous personnel shift planning and
unrelated parallel machine scheduling [3.0477617036157136]
本稿では,産業利用事例から得られた生産スケジューリング問題に対処する。
人件費制約を伴う非関連並列マシンスケジューリングに焦点を当てている。
機械間での人員共有を前提としており、作業処理中に機械の設置と監督に1人の人員を要している。
論文 参考訳（メタデータ） (2024-02-24T01:04:04Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
MAPF (Multi-Agent Path Finding) は、複数のエージェントが同時に移動し、与えられた目標地点に向かって共有領域を通って衝突しない経路を決定する。
最適解を見つけることは、しばしば計算不可能であり、近似的な準最適アルゴリズムを用いることが不可欠である。
本稿では、MAPFのスケーラブルな機構設計の問題を紹介し、MAPFアルゴリズムを近似した3つの戦略防御機構を提案する。
論文 参考訳（メタデータ） (2024-01-30T14:26:04Z) - SatLM: Satisfiability-Aided Language Models Using Declarative Prompting [68.40726892904286]
本研究では,大規模言語モデル (LLM) の推論能力を向上させるために,新しい満足度支援言語モデリング (SatLM) 手法を提案する。
我々はLLMを用いて命令型プログラムではなく宣言型タスク仕様を生成し、既製の自動定理証明器を利用して最終解を導出する。
我々はSATLMを8つの異なるデータセット上で評価し、命令パラダイムにおいてプログラム支援されたLMよりも一貫して優れていることを示す。
論文 参考訳（メタデータ） (2023-05-16T17:55:51Z) - Flexible Job Shop Scheduling via Dual Attention Network Based
Reinforcement Learning [73.19312285906891]
フレキシブルなジョブショップスケジューリング問題(FJSP)では、複数のマシンで操作を処理でき、操作とマシンの間の複雑な関係が生じる。
近年, 深層強化学習(DRL)を用いて, FJSP解決のための優先派遣規則(PDR)を学習している。
本稿では,Deep機能抽出のための自己注意モデルと,スケーラブルな意思決定のためのDRLの利点を生かした,エンドツーエンド学習フレームワークを提案する。
論文 参考訳（メタデータ） (2023-05-09T01:35:48Z) - ART: Automatic multi-step reasoning and tool-use for large language
models [105.57550426609396]
大規模言語モデル(LLM)は、数秒とゼロショットの設定で複雑な推論を行うことができる。
各推論ステップは、コアLLM機能を超えて計算をサポートする外部ツールに依存することができる。
プログラムとして中間推論ステップを自動生成するために凍結LDMを使用するフレームワークであるART(Automatic Reasoning and Tool-use)を導入する。
論文 参考訳（メタデータ） (2023-03-16T01:04:45Z) - Partitioning Distributed Compute Jobs with Reinforcement Learning and
Graph Neural Networks [58.720142291102135]
大規模な機械学習モデルは、幅広い分野に進歩をもたらしている。
これらのモデルの多くは、単一のマシンでトレーニングするには大きすぎるため、複数のデバイスに分散する必要がある。
スループットやブロッキングレートといったユーザクリティカルな指標に対して,並列化の最大化が準最適であることを示す。
論文 参考訳（メタデータ） (2023-01-31T17:41:07Z) - Single and Parallel Machine Scheduling with Variable Release Dates [0.0]
単一並列マシンと同一並列マシンの総重み付きフロータイム問題の単純拡張について検討する。
私たちの主な貢献は、単一マシンケースであっても問題のnp完全性を示すことです。
論文 参考訳（メタデータ） (2021-03-02T14:52:28Z) - Exact and heuristic methods for the discrete parallel machine scheduling
location problem [0.0]
問題は、有限個の候補の中から$p$マシンの位置を選択し、これらのマシン上の一連のジョブをスケジューリングすることである。
広範囲な計算実験によって評価される新しいアークフロー定式化,列生成,3つの手順を提案する。
論文 参考訳（メタデータ） (2020-06-09T00:10:18Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z) - Train Scheduling with Hybrid Answer Set Programming [1.4823899140444556]
ASP(Answer Set Programming)に基づく実世界の列車スケジューリング問題の解法を提案する。
要求される計画とスケジューリングの問題に対処するために、ハイブリッドASPシステムclingo[DL]がどのように使用できるのかを例に示す。
論文 参考訳（メタデータ） (2020-03-19T06:50:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。