論文の概要: Constraint programming model and biased random-key genetic algorithm for the single-machine coupled task scheduling problem with exact delays to minimize the makespan

• arxiv url: http://arxiv.org/abs/2512.23150v1
• Date: Mon, 29 Dec 2025 02:27:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-30 22:37:30.379918
• Title: Constraint programming model and biased random-key genetic algorithm for the single-machine coupled task scheduling problem with exact delays to minimize the makespan
• Title（参考訳）: 単一マシン結合タスクスケジューリング問題に対する制約プログラミングモデルとバイアスランダムキー遺伝的アルゴリズム
• Authors: Vítor A. Barbosa, Rafael A. Melo,
• Abstract要約: 本稿では,NP-ハード単一マシン結合型タスクスケジューリング問題について,スパンの最小化に正確な遅延を伴って検討する。 我々は制約プログラミング(CP)を用いて問題をモデル化し、バイアス付きランダムキー遺伝的アルゴリズム(BRKGA)を提案する。 我々のBRKGAは、初期解生成器、定期的な再起動と揺らぎ、局所的な探索アルゴリズムなど、文献において成功したいくつかのコンポーネントを組み合わせています。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the strongly NP-hard single-machine coupled task scheduling problem with exact delays to minimize the makespan. In this problem, a set of jobs has to be scheduled, each composed of two tasks interspersed by an exact delay. Given that no preemption is allowed, the goal consists of minimizing the completion time of the last scheduled task. We model the problem using constraint programming (CP) and propose a biased random-key genetic algorithm (BRKGA). Our CP model applies well-established global constraints. Our BRKGA combines some successful components in the literature: an initial solution generator, periodical restarts and shakes, and a local search algorithm. Furthermore, the BRKGA's decoder is focused on efficiency rather than optimality, which accelerates the solution space exploration. Computational experiments on a benchmark set containing instances with up to 100 jobs (200 tasks) indicate that the proposed BRKGA can efficiently explore the problem solution space, providing high-quality approximate solutions within low computational times. It can also provide better solutions than the CP model under the same computational settings, i.e., three minutes of time limit and a single thread. The CP model, when offered a longer running time of 3600 seconds and multiple threads, significantly improved the results, reaching the current best-known solution for 90.56% of these instances. Finally, our experiments highlight the importance of the shake and local search components in the BRKGA, whose combination significantly improves the results of a standard BRKGA.
• Abstract（参考訳）: 本稿では,NP-ハード単一マシン結合型タスクスケジューリング問題について,スパンの最小化に正確な遅延を伴って検討する。 この問題では、ジョブのセットをスケジュールし、それぞれが正確に遅延によって分散された2つのタスクで構成される必要がある。 プリエンプションが許されていないことを前提として、最終スケジュールタスクの完了時間を最小化する。 制約プログラミング(CP)を用いて問題をモデル化し、バイアス付きランダムキー遺伝的アルゴリズム(BRKGA)を提案する。 我々のCPモデルは、十分に確立されたグローバル制約を適用します。 我々のBRKGAは、初期解生成器、定期的な再起動と揺らぎ、局所的な探索アルゴリズムなど、文献において成功したいくつかのコンポーネントを組み合わせています。 さらに、BRKGAのデコーダは最適性よりも効率性を重視しており、解空間探索を加速させる。 最大100ジョブ(200タスク)のインスタンスを含むベンチマークセット上での計算実験により、提案したBRKGAが問題の解空間を効率的に探索し、低計算時間で高品質な近似解を提供することを示す。 また、CPモデルよりも3分間の時間制限と1スレッドという同じ計算条件下で優れたソリューションを提供することもできる。 CPモデルは、より長い実行時間3600秒と複数のスレッドを提供することで、結果を大幅に改善し、これらのインスタンスの90.56%で現在の最もよく知られているソリューションに到達した。 最後に、BRKGAにおける揺らぎ成分と局所探索成分の重要性を強調し、標準BRKGAの結果を大幅に改善した。

関連論文リスト

• Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
  本稿では,新しい無人航空機(UAV)による協調移動エッジコンピューティング(MEC)フレームワークを提案する。 システムコストを最小限に抑え、タスク消費とエネルギー消費のトレードオフを改善することを目的としている。 提案手法はシステムコストを大幅に削減し,タスク消費とエネルギー消費のトレードオフの改善を実現する。
  論文  参考訳（メタデータ） (2025-10-23T02:55:40Z)
• The Iterative Chainlet Partitioning Algorithm for the Traveling Salesman Problem with Drone and Neural Acceleration [27.475353583459263]
  ドローンによるトラベリングセールスマン問題(TSP-D)を解決するための反復連鎖分割(ICP)アルゴリズムとそのニューラルアクセラレーションについて紹介する。 ICPは、従来の最先端アルゴリズムよりも平均2.6%のソリューション品質向上を実現し、計算時間を91.3%削減した。 ICPと比較して、NICPは計算時間を28.6%削減し、目的関数値の増大は0.14%に制限される。
  論文  参考訳（メタデータ） (2025-04-21T14:51:15Z)
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling [33.04597339860113]
  本稿では,2つのスケジューリング問題に対して,ディジタル化された反断熱量子最適化(DCQO)アルゴリズムを提案する。 ジョブショップスケジューリング問題では,特定の制約下で複数のタスクを実行するロボットの最適なスケジュールを見つけることを目的としている。 旅行セールスパーソンの問題は、すべての都市をカバーし、最短の旅行距離と関連する経路を見つけることである。
  論文  参考訳（メタデータ） (2024-05-24T16:53:30Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Exact methods and lower bounds for the Oven Scheduling Problem [5.7485371212305685]
  Oven Scheduling Problem (OSP) は、電子部品製造の領域で発生する新しい並列バッチスケジューリング問題である。 オーブンの実行はエネルギー集約性の高いため、時間内にジョブを終了する以外に、すべてのオーブンの累積バッチ処理時間を最小化することが主な目的である。 本稿では、制約計画法(CP)と整数線形計画法(ILP)とそれに対応するモデルを用いて、このNPハードスケジューリング問題を解決することを提案する。
  論文  参考訳（メタデータ） (2022-03-23T16:28:05Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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