ナーススケジューリング問題の構造とソルバアプローチ

 ＜制約の構造は二つに分けられる＞

一つは、ナースのシフトに関する制約で、各ナースに関するものです。もう一つは、各日に関する制約で、必要なナース人数に関する制約です。表現を変えれば、各ナース個人に関する制約と各日に関する組織制約となります。

＜線形制約どうかの視点でいうと＞

線形制約とは、ax+bのように、一次関数の形式で表現できる制約のことです。一般にナース個人の制約は、線形では表現できません。演算子ANDや、OR、NOTを用いて表現することになりますが、これらは、ax+bの形式ではありませんので、線形制約ではありません。

これに対して、各Day制約は、夜勤3人、日勤10人以上とか、一般に線形制約となります。ペア制約のペア禁止制約もΣx<=1という具合に、線形制約で表現できます。唯一の非線形制約は、ペア制約：AならばB制約です。ですので、これを除けば、皆Day制約は、線形制約になります。

＜ナーススケジューリング問題は、ハイブリット構造をしている＞

基本的には、各個人に関する非線形制約と各Dayに関する線形制約から成ります。例外は、ペア制約：AならばB制約のみです。アカデミックベンチマーク群では、ペア制約は一切現れません。

実務問題では、ペア制約は、よく現れますが、少なくともアカデミックベンチマーク群では現れません。つまり、問題構造の基礎部分は、いずれも、各ナースに関する非線形制約と各Dayに関する線形制約のハイブリッド構造をしていることが分かります。

それを基礎として、ペア制約等をその上に構築していくことが分かりやすいと思います。一般にペア制約AならばB制約が入ると、LBを求めるのはさらに困難となります。なので、まずは、基礎的な構造部分でLBを求められるようにすることが、ソルバとして必要不可欠なのです。

＜ソルバのアプローチ方法＞

問題の構造は、明快です。組織の制約は、ほぼ線形制約が主なので、リニアソルバを使うことが理に適っています。つまり、解はリニア解近辺にある、と暗黙の前提に立ちます。その前提は本当に合っているのか？というご質問には、「少なくともアカデミックベンチマーク群は、その前提でほぼ全て解けました。」という回答になります。

https://schedule-nurse.blogspot.com/2026/09/blog-post_17.html

ここで、リニアソルバは、Simplex,Barrier,First Orderと種類がありますが、得意な規模領域によって使い分けることが適切なアプローチとなります。

一方、各ナースの表現は、論理演算は勿論ですが、シフト回数制約等、線形制約もあります。特に、この線形制約が加わることにより、各ナースだけでもRCSP（Resource　Constraint Shortest　Path 　Probelm）となり、NP困難なシステムになることが分かっています。

つまり、組織ではリニアソルバ、各ナースではRCSPソルバを使うことが、最も理に敵ったアプローチとなります。

＜整数化＞

リニアソルバで解が求まったにしても、その解は、浮動小数点です。例えば、人が0.3人という解は、整数解にする必要があります。浮動小数点空間から、整数空間にマッピングするのは、自明ではありません。（単純にroundしても、制約を満たす解にはなりません。）分枝限定法と呼ばれる手法で、整数化がなされますが、一般には、時間がかかりすぎる傾向があります。そこでSATソルバを用いた手法を併用します。

＜まとめ＞

ナーススケジューリング問題の組織制約は、リニア制約が主であり、解も線形解近辺にあると思われる。ナースシフトパターン制約は、専用のRCSPソルバを使い、リニア解を求めたあとに、分枝限定＋SATソルバにより高速求解することが理に敵ったアプローチということになります。

現代的なナーススケジューリング問題ソルバの構造と、技術領域分野について解説しました。

＜参考＞

こちらもAIによる挿絵を追加したのでよろしかったら御覧ください。

https://schedule-nurse.blogspot.com/2026/10/blog-post_29.html

コードチューニングのための時間計測

 C++でコード実行時間をナノ秒(ns)単位で計測する場合は、通常 std::chrono::steady_clock を使います。

#include <chrono>

#include <iostream>

 

int main()

{

auto start = std::chrono::steady_clock::now();

 

// 計測対象

volatile int sum = 0;

for (int i = 0; i < 1000000; ++i)

sum += i;

 

auto end = std::chrono::steady_clock::now();

 

auto ns = std::chrono::duration_cast<std::chrono::nanoseconds>(

end - start).count();

 

std::cout << ns << " ns\n";

}

関数化

template<class F>

long long measure_ns(F&& func)

{

auto start = std::chrono::steady_clock::now();

 

func();

 

auto end = std::chrono::steady_clock::now();

 

return std::chrono::duration_cast<

std::chrono::nanoseconds>(end - start).count();

}

使用例:

auto ns = measure_ns([]{

volatile int x = 0;

for (int i = 0; i < 1000000; ++i)

x += i;

});

 

std::cout << ns << " ns\n";

注意点

極めて短いコード（数ns～100ns程度）を計測する場合、

_mm_store_si128(...)

1回だけの計測ではタイマ精度やOS割込みの影響が大きくなります。

そのため、

constexpr int N = 1000000;

 

auto start = std::chrono::steady_clock::now();

 

for (int i = 0; i < N; ++i)

{

target_code();

}

 

auto end = std::chrono::steady_clock::now();

 

double ns_per_call =

std::chrono::duration_cast<std::chrono::nanoseconds>(

end - start).count()

/ static_cast<double>(N);

のように大量ループして1回当たりの時間を求める方が正確です。

さらにSIMD命令やCPUサイクル単位で測るなら、RDTSC/RDTSCP を使う方法もあります。

#include <x86intrin.h>

 

uint64_t t0 = __rdtsc();

 

target_code();

 

uint64_t t1 = __rdtsc();

 

std::cout << (t1 - t0) << " cycles\n";

ただし __rdtsc() は命令の並べ替えの影響を受けるため、ベンチマーク用途では通常

_mm_lfence();

t0 = __rdtsc();

 

target_code();

 

unsigned aux;

t1 = __rdtscp(&aux);

_mm_lfence();

のように LFENCE + RDTSC + RDTSCP + LFENCE を組み合わせます。

SSE/AVXレベルの最適化を評価するなら、chrono よりも RDTSCP で「サイクル数」を測定する方が有用です。例えば _mm_store_si128 と memcmp の比較などでは、nsよりcyclesの方が差が見えやすくなります。

サイクル数を時間に換算するには？

CPUサイクル数から時間への換算は、

$$\text{時間[s]}=\frac{\text{cycles}}{\text{CPU周波数[Hz]}}$$時間[s]=CPU周波数[Hz]cycles​

です。

例えば 4.0GHz のCPUで、

400 cycles

なら

$$400\mathrm{/}(4.0\times {10}^9)=100𝑛𝑠$$400/(4.0×109)=100ns

となります。

nsへ直接換算

$$\text{時間[ns]}=\frac{\text{cycles}\times {10}^9}{\text{CPU周波数[Hz]}}$$時間[ns]=CPU周波数[Hz]cycles×109​

4GHzなら

double ns = cycles / 4.0;

になります。

なぜなら4 GHz = 4 cycles/ns

だからです。

---

実際にはTurboで周波数が変わる

最近のCPUは

3.0GHz → 5.3GHz

のように動的に変化します。

そのため

cycles / CPU_GHz

で計算しても誤差があります。

ベンチマークでは通常、

cycles

のまま比較します。

実装A : 12 cycles

実装B : 18 cycles

のように。

---

TSCがInvariantの場合

最近のIntel/AMDでは TSC(Time Stamp Counter) が一定速度です。

例えば

t0 = __rdtsc();

sleep(1);

t1 = __rdtsc();

なら

t1 - t0 ≒ TSC周波数

です。

TSC周波数は実クロックとは異なり、

Base Clock

に固定されていることが多いです。

---

正確な換算方法

chrono と rdtsc を同時に計測して較正します。

auto t0 = std::chrono::steady_clock::now();

uint64_t c0 = __rdtsc();

 

std::this_thread::sleep_for(std::chrono::milliseconds(100));

 

auto t1 = std::chrono::steady_clock::now();

uint64_t c1 = __rdtsc();

 

double sec =

std::chrono::duration<double>(t1 - t0).count();

 

double tsc_hz = (c1 - c0) / sec;

すると

C++

ns = cycles * 1e9 / tsc_hz;

で高精度に換算できます。

SIMDコード（_mm_store_si128、memcmp、8byte比較など）の性能評価なら、ユーザーさんの用途では ns換算せず cycles のまま比較するのが一般的 です。CPU周波数変動の影響を受けず、

Plain Text

実装A : 3.2 cycles

実装B : 5.8 cycles

のように直接性能差が分かります。さらに命令単位で評価する場合は、ループ展開して「cycles/iteration」または「cycles/op」を見るのが定番です。

インクリメンタル アクセスとデクリメンタルアクセス

データ構造を作り直すことにしました。ついては、アクセス方法の違いについて聞きました。 

インクリメンタル　アクセスとデクリメンタルアクセスで、キャッシュヒット特性に差はありますか？

インクリメンタルアクセス（アドレスが順方向に増加）とデクリメンタルアクセス（アドレスが逆方向に減少）では、キャッシュヒット特性に明らかな差が出ることがあります。

この差は主に、現代のプロセッサに搭載されているハードウェアプリフェッチャ（事前読み込み機能）の挙動や設計に起因します。

主な違いと特性は以下の通りです。

---

1. ハードウェアプリフェッチャの対応度

現代のCPUは、次にアクセスされるデータを予測してキャッシュに先読みします。

• インクリメンタル（順方向）：
  • ほぼすべてのプロセッサのプリフェッチャが完璧に対応しています。
  • 連続的な順方向アクセス（A, A+1, A+2...）を検出すると、自動的に先読みが行われるため、キャッシュヒット率は非常に高くなります。
• デクリメンタル（逆方向）：
  • 多くの近代的なCPU（IntelやAMD、ARMの高性能コアなど）は逆方向のストライド（A, A-1, A-2...）も検出できます。
  • しかし、古いアーキテクチャや、低消費電力向けの簡易なプロセッサ（一部の組み込み向けコアなど）では、逆方向のプリフェッチに対応していない、あるいは順方向に比べて検出の優先度が低い場合があります。この場合、デクリメンタルアクセスではキャッシュミスが多発します。

---

2. 空間局所性とキャッシュラインのマッピング

メモリは「キャッシュライン（一般的に64バイト）」という単位でキャッシュに読み込まれます。

• インクリメンタル：
  • キャッシュラインの先頭（オフセット0）から末尾に向かってアクセスが進むため、1度のキャッシュミスで読み込んだラインをフルに活用できます。
• デクリメンタル：
  • キャッシュラインの末尾から先頭に向かって逆順にアクセスします。
  • プリフェッチが効かない環境では、「新しいキャッシュラインにまたがった瞬間（境界を越えたとき）」に必ずキャッシュミス（レイテンシ）が発生し、その後そのラインの残りのデータを逆向けに消化していく形になります。データの利用効率自体は同じですが、ミスの発生するタイミングやプリフェッチの起動タイミングが狂いやすくなります。

---

まとめ（比較表）

特性	インクリメンタルアクセス (順方向)	デクリメンタルアクセス (逆方向)
一般的なヒット率	非常に高い（安定）	高〜中（CPUのプリフェッチ能力に依存）
ハードウェア先読み	確実に動作する	CPUによっては動作しない・遅れる場合がある
不利益を被る環境	特になし	古いCPU、組み込み向けCPU、GPUの一部など

結論として：
最新のPCやサーバー向けCPUであれば、どちらも高いヒット率を維持できるよう設計されていますが、ハードウェアの最適化は常に「インクリメンタル（順方向）」を最優先に設計されているため、迷った場合はインクリメンタルなアクセス経路（例：多次元配列をループさせる際の順序など）を選択するのが安全です。