論文の概要: From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling
- arxiv url: http://arxiv.org/abs/2608.30419v1
- Date: Mon, 31 Aug 2026 08:17:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:31.303895
- Title: From Metaheuristics to Exact Methods: A CP-SAT Approach for Multi-Objective Healthcare Workforce Scheduling
- Title（参考訳）: メタヒューリスティクスからエクサクティヴメソッドへ:多目的ヘルスケアワークフォーススケジューリングのためのCP-SATアプローチ
- Abstract要約: 本稿では,マルチロール・マルチスキル医療スケジューリングのための制約プログラミング式CP-SATを提案する。
CP-SATは、規制違反がゼロであることを保証し、統一された重み付きペナルティ関数によって15のソフト目標を最適化する。
この定式化により、業界平均の約3倍の29の制約が課せられる。
- 参考スコア（独自算出の注目度）: 0.764671395172401
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Healthcare workforce scheduling is an NP-hard optimization problem requiring simultaneous satisfaction of labor regulations, coverage requirements, employee preferences and cost objectives. Existing approaches (genetic algorithms, integer programming, constraint programming) model 6-12 constraints at shift-level granularity and cannot guarantee regulatory compliance. They also lack support for multi-role, multi-skill heterogeneity, mandatory break scheduling with midpoint control, acuity-weighted workload equity, sub-shift granularity, inter-week stability, and cross-midnight shifts. This paper presents CP-SAT: a Constraint Programming formulation for multi-role, multi-skill healthcare scheduling. CP-SAT enforces 14 hard constraints guaranteeing zero regulatory violations, while optimizing 15 soft objectives via a unified weighted penalty function. Contributions include a shift-window decomposition enabling break scheduling with centrality control, acuity-weighted workload equity, multi-granularity resolution from 15 minutes to 1 day, inter-week stability, and grid-offset preprocessing mapping cross-midnight shifts into a single scheduling day without solver changes. CP-SAT is evaluated on 18 instances: five synthetic hospital units (10-33 nurses), 10 INRC-II benchmarks (5-80 nurses, up to 8-week horizons) and 3 NRP-23 compatible instances (10-25 nurses) with cross-midnight Night shifts. Results: zero hard-constraint violations across all 18 instances by construction; proven optimality on INRC-II n005w4 (objective 118, gap 0.0%, 104s); feasible schedules scaling to 179,800 variables and 351,425 constraints (80 nurses); service quality improved 50-67% over MOGA; and model size scaling near-linearly at approximately 4,400 variables per employee. The formulation enforces 29 total constraints (14 hard, 15 soft), nearly three times the industry average.
- Abstract（参考訳）: 医療従事者のスケジューリングは、労働規制、カバレッジ要件、従業員の好み、コスト目標を同時に満足させる必要があるNPハード最適化問題である。
既存のアプローチ(遺伝的アルゴリズム、整数プログラミング、制約プログラミング)は、シフトレベルの粒度で6-12の制約をモデル化し、規制の遵守を保証できない。
また、マルチロール、マルチスキルの不均一性、中点制御による必須ブレークスケジューリング、空力重み付きワークロードエクイティ、サブシフト粒度、週間間の安定性、ミッドナイトシフトのサポートも欠如している。
本稿では,マルチロール・マルチスキル医療スケジューリングのための制約プログラミング式CP-SATを提案する。
CP-SATは、規制違反がゼロであることを保証し、統一された重み付きペナルティ関数によって15のソフト目標を最適化する。
コントリビューションには、集中度制御によるブレークスケジューリングを可能にするシフトウインドウ分解、明度重み付けされたワークロードエクイティ、15分から1日の多粒度解決、週間間安定性、グリッドオフセット前処理マッピングを、解決者の変更なしに1つのスケジュール日へマッピングする、などが含まれる。
CP-SATは5つの総合病院ユニット(10-33看護師)、10つのINRC-IIベンチマーク(5-80看護師、最大8週間の地平線)、3つのNRP-23互換インスタンス(10-25看護師)と、真夜中のシフトを含む18のインスタンスで評価されている。
結果: 建設による18のインスタンスすべてに対するゼロのハード制約違反, INRC-II n005w4(オブジェクト118, ギャップ0.0%, 104s), 可能なスケジュールスケーリングが179,800変数, 351,425制約(80看護師), サービス品質がMOGAよりも50-67%向上し, モデルサイズがほぼ直線的に約4,400変数に向上した。
この定式化は、業界平均の3倍近い29の制約(硬い14、柔らかい15)を課している。
関連論文リスト
- ZGCM-1: A Fully Open and Extremely Efficient Foundation Model for Math and Agentic Search [54.43696074323815]
ZGCM-1は、極端なデータ、システム、アルゴリズムの効率でゼロから訓練された、完全にオープンな7Bファンデーションモデルである。
エージェントがクラスタ操作を自律的に管理する、AIネイティブなR&Dワークフローを確立します。
ZGCM-1-7Bは一般的なベンチマークで7Bモデルファミリ間で競合する。
論文 参考訳（メタデータ） (2026-09-11T17:18:04Z) - Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
有限オートマトンとして表現可能な任意の制約の下で,制約付き平均場後部からサンプリングする,正確かつトラクタブルなアルゴリズムを提案する。
このアプローチは、構築による制約満足度を保証し、欲求とサンプリングベースのデコーディングの両方をサポートし、並列およびブロックワイドデコーディングと互換性がある。
Dream-7B と LLaDA-8 の実証的な評価は、様々なタスクにおいてかなりの精度の向上を示した。
論文 参考訳（メタデータ） (2026-07-08T05:48:57Z) - CP-WSP: A Declarative CP-SAT Framework for Configurable Multi-Constraint Workforce Scheduling [0.764671395172401]
本稿では, CP-WSPについて, 14の厳密な制約を数学的に不可侵な要件として適用する宣言型CPフレームワークについて述べる。
主なコントリビューションは、Acuity-weighted Workload equityによる強制的なブレークスケジューリングを可能にするシフトウィンドウ変数、30分から2時間までの時間分解性、週間スケジュール安定性、グリッドオフセットによる中間シフト前処理技術である。
論文 参考訳（メタデータ） (2026-07-06T14:57:46Z) - RVPO: Risk-Sensitive Alignment via Variance Regularization [13.192921543523283]
本稿では, 利便集約時のリワード間分散をペナルティ化するリスクセンシティブなフレームワークであるReward-Variance Policy Optimization (RVPO)を提案する。
我々はTaylor拡張を通して、LogSumExp(SoftMin)オペレータがスムーズな分散ペナルティとして効果的に働くことを示す。
モデルがより簡単な目的を活かすために難しい制約を無視しないようにすることで、RVPOはHealthBenchの全体的なスコアを改善する。
論文 参考訳（メタデータ） (2026-05-07T06:43:05Z) - Optimizing Earth Observation Satellite Schedules under Unknown Operational Constraints: An Active Constraint Acquisition Approach [1.3097161185372153]
保守的制約獲得(英: conservative Constraint Acquisition, CCA)は、正当化された制約を効果的に識別するために設計されたドメイン固有の手続きである。
L&Oは、学習制約モデルの下で最適化をターゲットとするオラクルクエリと交換する対話型検索プロセスをサポートする。
CP-SAT参照が120年代に見つかった最良のソリューションである$n=50$では、L&Oは平均17.9%対20.3%)で改善され、100の代わりに21.3のメインクエリを使用する。
論文 参考訳（メタデータ） (2026-04-14T20:19:28Z) - Compact Constraint Encoding for LLM Code Generation: An Empirical Study of Token Economics and Constraint Compliance [0.0]
本研究では,コンパクトで構造化された制約ヘッダーが制約コンプライアンスを低下させることなく,トークンの迅速な消費を低減できるかどうかを検討する。
コンパクトヘッダーは、3ラウンドで複製された制約ポートトークンを約71%減らし、フルプロンプトトークンを25～30%減らした。
論文 参考訳（メタデータ） (2026-04-08T15:18:33Z) - CCTU: A Benchmark for Tool Use under Complex Constraints [66.87622847854337]
複雑な制約下での大規模言語モデル(LLM)を評価するためのベンチマークであるCCTUを紹介する。
ベンチマークは、さまざまなツール使用シナリオに対して、慎重にキュレートされ、挑戦的なテストケースが200から成っている。
ステップレベルの検証を行い、コンプライアンスを強制する実行可能な制約検証モジュールを開発する。
論文 参考訳（メタデータ） (2026-03-16T14:05:13Z) - Towards a Science of Scaling Agent Systems [79.64446272302287]
エージェント評価の定義を定式化し,エージェント量,コーディネーション構造,モデル,タスク特性の相互作用として,スケーリング法則を特徴付ける。
協調指標を用いて予測モデルを導出し,R2=0をクロスバリデーションし,未知のタスク領域の予測を可能にする。
ツールコーディネーショントレードオフ: 固定的な計算予算の下では, ツールヘビータスクはマルチエージェントのオーバーヘッドから不均衡に悩まされ, 2) 能力飽和: 調整が減少または負のリターンを, 単一エージェントのベースラインが45%を超えると達成できる。
論文 参考訳（メタデータ） (2025-12-09T06:52:21Z) - Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning [52.03884701766989]
オフライン強化学習(RL)アルゴリズムは、通常、アクション選択に制約を課す。
本稿では,Bellmanターゲットにおける行動選択を,データセットアクションの近傍の結合に制限する新しい地区制約を提案する。
我々は,この制約を満たす目標動作を用いてQ学習を行うための,単純で効果的なアルゴリズムであるAdaptive Neighborhood-Constrained Q Learning(ANQ)を開発した。
論文 参考訳（メタデータ） (2025-11-04T13:42:05Z) - A Multi-Objective Genetic Algorithm for Healthcare Workforce Scheduling [0.764671395172401]
本稿では,多目的遺伝的アルゴリズム (MOO-GA) を提案する。
コスト、患者ケアのカバレッジ、スタッフの満足度を客観的に定義することにより、GAは膨大な検索スペースをナビゲートし、高品質で非支配的なソリューションの集合を特定する。
論文 参考訳（メタデータ） (2025-08-28T16:16:10Z) - RAYEN: Imposition of Hard Convex Constraints on Neural Networks [47.494620411594624]
RAYENは、ニューラルネットワークにハード凸制約を課すフレームワークである。
最先端のアルゴリズムの20倍から7468倍の高速化を実現している。
論文 参考訳（メタデータ） (2023-07-17T09:12:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。