シフトスケジューリング問題
以下のシフトスケジューリング問題を考えてみましょう。この問題は、総労働者コストを最小化するスケジュールを見つけることを目的としています。
- 労働者は6名、計画期間は31日間（1日目から31日目まで）である。 簡略化のため、全労働者は0日目と32日目に休暇中であると仮定する。
- 1日目から31日目までの各日において、正確に4名の労働者をスケジュールに組み込む必要がある。
- 各労働者に対して以下の制約を満たす必要がある：
- 20日または21日間勤務すること
- 連続6日を超えて働かない、
- 連続3日以上は勤務する、
- 孤立した休日を持たないこと（休日は連続していなければならない）。
シフトスケジューリング問題のQUBO定式化
QUBO定式化では、$6\times 33$の二値変数行列$X=(x_{i,j})$（$0\leq i\leq 5, 0\leq i\leq 32$）を用いる。ここで、労働者$i$が日$j$に勤務するのは$x_{i,j}=1$の場合に限る。
全作業員が0日目と32日目に休むため、以下を固定する
\[\begin{aligned} x_{i,0}=x_{i,32}=0 & &(0\leq i\leq 5). \end{aligned}\]制約条件は以下のように定式化する。
日次人員配置制約
各日に正確に4人の労働者を配置しなければならない：
\[\begin{aligned} \sum_{i=0}^{5} x_{i,j} = 4& &(1\leq j\leq 31) \end{aligned}\]総労働日数制約
各作業員は20日または21日のいずれかで勤務しなければならない：
\[\begin{aligned} 20\leq \sum_{j=0}^{32} x_{i,j} \leq 21& &(0\leq i\leq 5) \end{aligned}\]最大連続勤務日数制約
労働者は6日以上連続して勤務してはならない：
\[\begin{aligned} x_{i,j}x_{i,j+1}x_{i,j+2}x_{i,j+3}x_{i,j+4}x_{i,j+5}x_{i,j+6} = 0 & &(0\leq i\leq 5, 0\leq j\leq 26)\\ \end{aligned}\]最小連続就業日数制約
各勤務期間は少なくとも3日間の連続勤務で構成されなければならない：
\[\begin{aligned} (1-x_{i,j})x_{i,j+1}x_{i,j+2}(1-x_{i,j+3}) = 0 & &(0\leq i\leq 5, 0\leq j\leq 29)\\ (1-x_{i,j})x_{i,j+1}(1-x_{i,j+2}) = 0 & & (0\leq i\leq 5, 0\leq j \leq 30) \end{aligned}\]孤立した休日を許さない制約
労働者は2つの就業日の間に単一の休日を持つことはできない：
\[\begin{aligned} x_{i,j}(1-x_{i,j+1})x_{i,j+2} = 0 & &(0\leq i\leq 5, 0\leq j\leq 30)\\ \end{aligned}\]総労働者コスト
コストベクトル $C=(c_i)$ を定義する。ここで $c_i$ は労働者 $i$ を割り当てた場合の日次コストを示す。 総労働者コストは次のように定式化される：
\[\begin{aligned} \sum_{i=0}^5\sum_{j=0}^{32} c_i x_{i,j} \end{aligned}\]この目的関数は、上記の制約条件の下で最小化される。
シフトスケジューリングのためのQUBO++プログラム
上記で定義したシフトスケジューリング問題は、QUBO++を用いて以下のように定式化・解くことができる：
#include "qbpp.hpp"
#include "qbpp_easy_solver.hpp"
int main() {
const size_t days = 31;
const qbpp::Vector<int> worker_cost = {13, 13, 12, 12, 11, 10};
const size_t workers = worker_cost.size();
auto x = qbpp::var("x", workers, days + 2);
auto workers_each_day = qbpp::vector_sum(qbpp::transpose(x));
auto each_day_4_workers = qbpp::toExpr(0);
for (size_t j = 1; j <= days; ++j) {
each_day_4_workers += workers_each_day[j] == 4;
}
auto workers_working_days = qbpp::vector_sum(x);
auto work_20_21_days = qbpp::sum(20 <= workers_working_days <= 21);
auto no_more_than_6_consecutive_working_days = qbpp::toExpr(0);
for (size_t w = 0; w < workers; ++w) {
for (size_t j = 0; j <= days - 5; ++j) {
no_more_than_6_consecutive_working_days +=
x[w][j] * x[w][j + 1] * x[w][j + 2] * x[w][j + 3] * x[w][j + 4] *
x[w][j + 5] * x[w][j + 6];
}
}
auto no_less_than_3_consecutive_working_days = qbpp::toExpr(0);
for (size_t w = 0; w < workers; ++w) {
for (size_t j = 0; j < days - 1; ++j) {
no_less_than_3_consecutive_working_days +=
(1 - x[w][j]) * x[w][j + 1] * x[w][j + 2] * (1 - x[w][j + 3]);
}
for (size_t j = 0; j < days; ++j) {
no_less_than_3_consecutive_working_days +=
(1 - x[w][j]) * x[w][j + 1] * (1 - x[w][j + 2]);
}
}
auto no_single_day_off = qbpp::toExpr(0);
for (size_t w = 0; w < workers; ++w) {
for (size_t j = 0; j <= days - 1; ++j) {
no_single_day_off += x[w][j] * (1 - x[w][j + 1]) * x[w][j + 2];
}
}
auto total_worker_cost = qbpp::sum(worker_cost * workers_working_days);
auto constraints = work_20_21_days + no_less_than_3_consecutive_working_days +
no_more_than_6_consecutive_working_days +
no_single_day_off + each_day_4_workers;
auto f = total_worker_cost + 10000 * constraints;
qbpp::MapList ml;
for (size_t i = 0; i < workers; ++i) {
ml.push_back({x[i][0], 0});
ml.push_back({x[i][days + 1], 0});
}
auto g = qbpp::replace(f, ml);
g.simplify_as_binary();
workers_working_days.replace(ml);
auto solver = qbpp::easy_solver::EasySolver(g);
solver.time_limit(5.0);
solver.target_energy(0);
auto sol = solver.search();
for (size_t i = 0; i < workers; ++i) {
std::cout << "Worker " << i << ": " << sol(workers_working_days[i])
<< " days worked: ";
for (size_t j = 1; j <= days; ++j) {
std::cout << sol(x[i][j]);
}
std::cout << std::endl;
}
std::cout << "Workers each day : ";
for (size_t d = 1; d <= days; ++d) {
std::cout << sol(workers_each_day[d]);
}
std::cout << std::endl;
auto sol_f = qbpp::Sol(f);
sol_f.set(ml);
sol_f.set(sol);
std::cout << "Total worker cost: " << sol_f(total_worker_cost) << std::endl;
std::cout << "Constraints violations: " << sol_f(constraints) << std::endl;
}
このプログラムでは、変数と式は以下のように定義される：
x: 6×33の二値変数行列workers_each_day: 各列の合計を含むベクトルx各日に割り当てられた作業員数を表すeach_day_4_workers: 各日に正確に4人の労働者が割り当てられた場合にのみ最小値0となる制約式。workers_working_days: 行ごとの合計値のベクトルx各労働者の総労働日数を表す。work_20_21_days: 各労働者が20日または21日のいずれかで働く場合にのみ最小値0となる制約式。no_more_than_6_consecutive_working_days: 7日以上連続して勤務する労働者が存在しない場合にのみ最小値0となる制約式。no_less_than_3_consecutive_working_days: すべての勤務期間が少なくとも3連続勤務日で構成される場合にのみ最小値0を達成する制約式。no_single_day_off: 2つの労働日の間に1日も休みを取らない労働者が存在しない場合にのみ最小値0となる制約式。constraints: 全ての制約式の和。total_worker_cost: 労働者総コストを表す式。
QUBOの構築と解法
合計することで total_worker_cost と constraints にペナルティ係数10000を乗じて和を計算することで、
式 fが得られ、これはシフトスケジューリング問題のQUBO表現となる。
A qbpp::MapList オブジェクト ml は、日0および日32に対応する変数の値を固定するために使用される。
関数 qbpp::replace() 関数を f を適用すると ml すると、新しい式 g.
その後、イージーソルバーが gに適用され、得られた解は solに格納される。
得られた解は以下の通りである：
Worker 0: 20 days worked: 0001111001110011111001111001111
Worker 1: 20 days worked: 1111001111110001111110011110000
Worker 2: 21 days worked: 0000111100111110011111100111111
Worker 3: 21 days worked: 1111110011111100111000111111000
Worker 4: 21 days worked: 1111100111001111000111000111111
Worker 5: 21 days worked: 1110011110001111100111111000111
Workers each day : 4444444444444444444444444444444
Total worker cost: 1465
Constraints violations: 0
総労働者コストが 1465 が得られ、全ての制約条件が満たされていることが確認できる。
最終更新日: 2026.01.05