0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@deepblue_angel

大学生活のスケジュール管理をOR-Toolsでやってみる

0
Posted at

はじめに

以前OR toolsでシフトの作成を行う記事を執筆しました。
今回はそれを発展させて、個人のスケジュール管理を行うプログラムを作ってみます。

モチベーション

タイムマネジメントの方法の１つとして、タイムボクシング（Time boxing）というものがあります。これは、区切られた時間枠=タイムボックスを作成し、そのタイムボックスにタスクを振り分けることでスケジュールを管理するやり方です1。

当初、筆者は紙のノートでタイムボクシングを試みたのですが、作成や修正が困難で続かず。オペレーションズ・リサーチの技法で自動化できないかと考え、スケジュール作成のプログラムを作ることにしました。

※以下はChatGPTを用いて生成したコードの例とその解説です。

サンプルコード

# ------------------
# 1. ライブラリのインポート
# ------------------
from ortools.sat.python import cp_model

# ------------------
# 2. 時間ブロックの作成
# ------------------
def generate_slots(day, start_hour, end_hour):
    slots = []
    t = int(start_hour * 2)
    end = int(end_hour * 2)
    while t < end:
        h = t // 2
        m = "00" if t % 2 == 0 else "30"
        slots.append(f"{day}_{h:02d}:{m}")
        t += 1
    return slots

slots_day1 = generate_slots("Day1", 9, 23.5)
slots_day2 = generate_slots("Day2", 9, 23)
slots = slots_day1 + slots_day2

# スロット→index（高速化）
slot_index = {s: i for i, s in enumerate(slots)}

# ------------------
# 3. 固定タスクの設定
# ------------------
blocked_slots = set()
fixed_events = {}

def add_fixed_event(day, start, end, name):
    t = int(start * 2)
    end_t = int(end * 2)
    while t < end_t:
        h = t // 2
        m = "00" if t % 2 == 0 else "30"
        s = f"{day}_{h:02d}:{m}"

        blocked_slots.add(s)   
        fixed_events[s] = name  

        t += 1

# 固定タスクの追加（１日目）
add_fixed_event("Day1", 10.5, 12.5, "授業３")
add_fixed_event("Day1", 15, 17, "授業４")
add_fixed_event("Day1", 18, 19.5, "企業説明会")

add_fixed_event("Day1", 12.5, 13.5, "昼食")
add_fixed_event("Day1", 20, 21, "夕食")
add_fixed_event("Day1", 21.5, 22.5, "風呂")

# 固定タスクの追加（２日目）
add_fixed_event("Day2", 11.5, 12.5, "昼食")
add_fixed_event("Day2", 18, 19, "夕食")
add_fixed_event("Day2", 19.5, 20.5, "風呂")

def block_buffer_around(event_name):
    for s, name in fixed_events.items():
        if name == event_name:
            i = slot_index[s]
            for j in [i - 1, i + 1]:
                if 0 <= j < len(slots):
                    blocked_slots.add(slots[j])

block_buffer_around("企業説明会")

# ------------------
# 4. 通常タスクの定義
# ------------------
tasks = {
    "授業１の予習": {"duration": 4, "priority": 2},
    "授業２の課題": {"duration": 4, "priority": 2},
    "Slackの返信": {"duration": 1, "priority": 5},
    "研究計画書_関連研究_歴史": {"duration": 8, "priority": 1},
    "研究計画書_関連研究_定性・定量研究": {"duration": 6, "priority": 1},
}

# ------------------
# 5. モデルの定義
# ------------------
model = cp_model.CpModel()

# ------------------
# 6. タスク × スロットの組み合わせ作成
# ------------------
x = {}
for t in tasks:
    for s in slots:
        x[(t, s)] = model.NewBoolVar(f"x_{t}_{s}")

# ------------------
# 7. 制約の追加
# ------------------
# 制約１：固定タスクの時間帯には何も入れない
for s in blocked_slots:
    if s in slots:
        for t in tasks:
            model.Add(x[(t, s)] == 0)

# 制約２：タスクの完了には指定された時間がかかる
for t, info in tasks.items():
    model.Add(sum(x[(t, s)] for s in slots) == info["duration"])

# 制約３：１つの時間ブロックにつき１タスクのみ実行
for s in slots:
    model.Add(sum(x[(t, s)] for t in tasks) <= 1)

# 制約４：完了に長い時間を要するタスクについては、最低１時間はまとめて取り組む
for t in tasks:
    if "返信" in t:
        continue

    for i in range(len(slots)):
        s = slots[i]

        neighbors = []
        if i > 0:
            neighbors.append(x[(t, slots[i - 1])])
        if i < len(slots) - 1:
            neighbors.append(x[(t, slots[i + 1])])

        if neighbors:
            model.Add(x[(t, s)] <= sum(neighbors))

# １日の開始・終了時
for t in tasks:
    if "返信" in t:
        continue

    model.Add(x[(t, slots[0])] <= x[(t, slots[1])])
    model.Add(x[(t, slots[-1])] <= x[(t, slots[-2])])

# ------------------
# 8. 目的関数の設定
# ------------------
weights = {s: len(slots) - i for i, s in enumerate(slots)}

model.Maximize(
    sum(weights[s] * tasks[t]["priority"] * x[(t, s)]
        for t in tasks for s in slots)
)

# ------------------
# 9. 解く
# ------------------
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)

# ------------------
# 10. 出力
# ------------------
if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print("=== スケジュール ===")

    current_day = None

    for s in slots:
        day = s.split("_")[0]

        if day != current_day:
            if current_day is not None:
                print("\n" + "-" * 30)
            print(f"\n### {day}")
            current_day = day

        if s in fixed_events:
            print(s[5:], fixed_events[s])
        else:
            assigned = False
            for t in tasks:
                if solver.Value(x[(t, s)]) == 1:
                    print(s[5:], t)
                    assigned = True
            if not assigned:
                print(s[5:], "free")

コードの解説

1. ライブラリのインポート

Google Colaboratoryの場合、最初にOR-Toolsをインストールする必要があります。

pip install ortools

from ortools.sat.python import cp_model

2. 時間ブロックの作成

まず、1日を30分ごとのブロックに分割する関数generate_slots()を作ります。引数は以下の通り。

  • day(string)：1日を識別する名前。日付など
  • start_hour(float)：タスクの取り組み開始時間。0.5（=30分）刻みで入力
  • end_hour(float)：タスクの取り組み終了時間。0.5（=30分）刻みで入力
def generate_slots(day, start_hour, end_hour):
    slots = []
    # 30分間隔にするため２倍
    t = int(start_hour * 2)
    end = int(end_hour * 2)
    # 時間表記を取得（例：10:30）
    while t < end:
        h = t // 2
        m = "00" if t % 2 == 0 else "30"
        slots.append(f"{day}_{h:02d}:{m}")
        t += 1
    return slots

関数を適用し、変数を作ります。
サンプルコードでは2日分のスケジューリングを行うため、変数を２個作成したのち連結しています。

slots_day1 = generate_slots("Day1", 9, 23.5)
slots_day2 = generate_slots("Day2", 9, 23)
slots = slots_day1 + slots_day2

また、ここで「スロット名：位置インデックス」を対応させる辞書を作成しています。
この辞書を使うことで、時間ブロックの前後関係を扱うほか、後述するタスクの連続性の確保も可能になります。

# スロット名と位置インデックスを対応
slot_index = {s: i for i, s in enumerate(slots)}

3. 固定タスクの設定

ここで「固定タスク」とは、授業や会議など時間帯を動かせないタスクを指します。今回のコードでは、まず時間ブロックに固定タスクを組み込んだのち計画を作成します。

サンプルコードでは、まず変数blocked_slotsとfixed_eventsを設定しています。blocked_slotsは固定タスクのため使用不可能な時間ブロックのIDを格納するための集合、fixed_eventsは時間ブロックのIDと固定タスクの名前を対応づけて表示するための辞書です。

blocked_slots = set()
fixed_events = {}

次に、時間ブロックに固定タスクを組み込む関数add_fixed_event()を作成します。引数はgenerate_slots()でも用いたday、開始・終了時間を示すstartとend、固定タスクの名前を表すnameです。

def add_fixed_event(day, start, end, name):
    # 30分間隔にするため２倍
    t = int(start * 2)
    end_t = int(end * 2)
    while t < end_t:
        # 時間帯表示を取得
        h = t // 2
        m = "00" if t % 2 == 0 else "30"
        s = f"{day}_{h:02d}:{m}"

        blocked_slots.add(s)     # 制約用
        fixed_events[s] = name   # 表示用

        t += 1

関数を適用し、固定タスクを追加します。
下記の例では、１日目は授業２コマと企業説明会、２日目は全休です。このブログも全休で書いています。
また、それぞれ昼食・夕食・風呂の予定を入れています。

# 固定タスクの追加（１日目）
add_fixed_event("Day1", 10.5, 12.5, "授業３")
add_fixed_event("Day1", 15, 17, "授業４")
add_fixed_event("Day1", 18, 19.5, "企業説明会")

add_fixed_event("Day1", 12.5, 13.5, "昼食")
add_fixed_event("Day1", 20, 21, "夕食")
add_fixed_event("Day1", 21.5, 22.5, "風呂")

# 固定タスクの追加（２日目）
add_fixed_event("Day2", 11.5, 12.5, "昼食")
add_fixed_event("Day2", 18, 19, "夕食")
add_fixed_event("Day2", 19.5, 20.5, "風呂")

さらに、企業説明会など「周囲の環境を整えてから実行する必要のあるタスク」も存在します。
このようなタスクの前後は時間を空けたいため、関数block_buffer_around()でこの機能を実装します。

def block_buffer_around(event_name):
    for s, name in fixed_events.items(): # 全ての固定タスクをチェック
        if name == event_name:
            i = slot_index[s] # インデックス取得
            
            for j in [i - 1, i + 1]: 
                if 0 <= j < len(slots): # インデックスエラー防止
                    blocked_slots.add(slots[j]) # 時間帯固定

# block_buffer_aroundの実行
block_buffer_around("企業説明会")

4. 通常タスクの定義

時間帯に制約のある固定タスクに対して、いつでも実行できるタスクを「通常タスク」とします。
辞書taskに{タスク名:{タスクに必要な時間: 優先度}}という形式でタスクの詳細を格納しています。

tasks = {
    "授業１の予習": {"duration": 4, "priority": 2},
    "授業２の課題": {"duration": 4, "priority": 2},
    "Slackの返信": {"duration": 1, "priority": 5},
    "研究計画書_関連研究_歴史": {"duration": 8, "priority": 1},
    "研究計画書_関連研究_定性・定量研究": {"duration": 6, "priority": 1},
}

5. モデルの定義

前回と同じく、今回も制約プログラミング（Constraint Programming）を行うCpModelを用います。

model = cp_model.CpModel()

6. タスク × スロットの組み合わせ作成

まずは全タスク × 全スロットの組み合わせ分の変数を作ります。以降のモデリングはこの変数に制約を加える形で行います。

x = {}
for t in tasks:
    for s in slots:
        x[(t, s)] = model.NewBoolVar(f"x_{t}_{s}")

上記のコードを実行すると、xには以下のようなデータが格納されます。

{('授業１の予習', 'Day1_09:00'): x_授業１の予習_Day1_09:00(0..1),
('授業１の予習', 'Day1_09:30'): x_授業１の予習_Day1_09:30(0..1),
('授業１の予習', 'Day1_10:00'): x_授業１の予習_Day1_10:00(0..1),
...}

(0..1)は取りうる値の範囲（0=タスクをしない、1=する）を示しています。

7. 制約の追加

Addメソッドを使って条件を追加していきます。

制約１：固定タスクの時間帯には何も入れない

固定タスクを実行するための時間帯がblocked_slotsに記録されているので、その時間帯は通常タスクを行わないようにします。

for s in blocked_slots:
    if s in slots:
        for t in tasks:
            model.Add(x[(t, s)] == 0)

制約２：タスクの完了には指定された時間がかかる

計画においてタスクに費やす時間は、タスク完了に必要な時間と同量とします。

for t, info in tasks.items():
    model.Add(sum(x[(t, s)] for s in slots) == info["duration"])

制約３：１つの時間ブロックにつき１タスクのみ実行

時間ブロックを１つ固定し、そのブロックに入っている全タスクの合計スコアが１以下になるようにします。
例えば、「Day1_10:00」というブロックがあったとき、

x[(授業１の予習, Day1_10:00)] = 1 
x[(授業２の課題, Day1_10:00)] = 0
x[(Slackの返信, Day1_10:00)] = 0

となるようにします。

for s in slots:
    model.Add(sum(x[(t, s)] for t in tasks) <= 1)

制約４：完了に長い時間を要するタスクについては、最低１時間はまとめて取り組む

タスクを頻繁に切り替えると負荷が発生し（切り替えコスト：switch costと呼ばれる2）、反応の遅れや処理ミスが発生する確率が上がることが示唆されています。

今回のタスク例だと、「10:00〜授業１の予習、10:30〜授業２の課題、11:00〜授業１の予習…」と頻繁に切り替わる状況だと（少なくとも筆者は）疲れてしまいます。もちろん細切れにしか時間が使えない場合など致し方ない場面もあるかと思いますが、長時間かかるタスクはできるだけまとめてやりたい、というのが私の気持ちです。

上記を最終的なスケジュールに反映すべく、モデルに以下のように制約を加えます。リストneighborsに前後の時間ブロックのスコアを格納し、前後いずれか、もしくは両方に同じタスクが入っているようにします。

for t in tasks:
    # 返信は1時間未満で終わるのでスルー
    if "返信" in t:
        continue

    for i in range(len(slots)):
        # ブロックごとのインデックス
        s = slots[i]
        # 前後のブロックを追加
        neighbors = []
        if i > 0:
            neighbors.append(x[(t, slots[i - 1])])
        if i < len(slots) - 1:
            neighbors.append(x[(t, slots[i + 1])])
        # 前後のつながりを保証
        if neighbors:
            model.Add(x[(t, s)] <= sum(neighbors))

1日の最初・最後には前（後）にあたる時間ブロックが存在しないため、別途処理を行います。

for t in tasks:
    if "返信" in t: # スルー
        continue

    model.Add(x[(t, slots[0])] <= x[(t, slots[1])])
    model.Add(x[(t, slots[-1])] <= x[(t, slots[-2])])

8. 目的関数の設定

タスクはなるべく前倒しで処理したいので、weightsを用いて早い時間帯に大きな重みづけをしています。

その上で、weightsが大きく、priorityが高いタスクを優先的に処理するものとします。

weights = {s: len(slots) - i for i, s in enumerate(slots)}

model.Maximize(
    sum(weights[s] * tasks[t]["priority"] * x[(t, s)]
        for t in tasks for s in slots)
)

9. 解く

CP-SATにより全パターンを探索し、制約を満たす最適な計画を作ります。なお、組み合わせ爆発に伴う計算時間の長期化を防ぐため、計算を10秒で打ち切ることにしています。

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)

10. 出力

最適解もしくは何か解が見つかった状態で、結果を出力します。

if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    print("=== スケジュール ===")

    current_day = None

    for s in slots:
    # "Day1"のような名前を取得
        day = s.split("_")[0] 

        # 日付切り替えの際に破線
        if day != current_day:
            if current_day is not None:
                print("\n" + "-" * 30)
            print(f"\n### {day}")
            current_day = day

        if s in fixed_events:
            # 日付は省略
            print(s[5:], fixed_events[s])
        else:
            assigned = False
            for t in tasks:
                if solver.Value(x[(t, s)]) == 1:
                    print(s[5:], t)
                    assigned = True
            if not assigned: # 自由時間
                print(s[5:], "free")

以上のコードを実行すると、以下のような出力が得られます。

=== スケジュール ===

### Day1
09:00 Slackの返信
09:30 授業２の課題
10:00 授業２の課題
10:30 授業３
11:00 授業３
11:30 授業３
12:00 授業３
12:30 昼食
13:00 昼食
13:30 授業２の課題
14:00 授業２の課題
14:30 free
15:00 授業４
15:30 授業４
16:00 授業４
16:30 授業４
17:00 free
17:30 free
18:00 企業説明会
18:30 企業説明会
19:00 企業説明会
19:30 free
20:00 夕食
20:30 夕食
21:00 free
21:30 風呂
22:00 風呂
22:30 授業１の予習
23:00 授業１の予習

------------------------------

### Day2
09:00 授業１の予習
09:30 授業１の予習
10:00 研究計画書_関連研究_歴史
10:30 研究計画書_関連研究_歴史
11:00 研究計画書_関連研究_歴史
11:30 昼食
12:00 昼食
12:30 研究計画書_関連研究_歴史
13:00 研究計画書_関連研究_歴史
13:30 研究計画書_関連研究_定性・定量研究
14:00 研究計画書_関連研究_定性・定量研究
14:30 研究計画書_関連研究_歴史
15:00 研究計画書_関連研究_歴史
15:30 研究計画書_関連研究_歴史
16:00 研究計画書_関連研究_定性・定量研究
16:30 研究計画書_関連研究_定性・定量研究
17:00 研究計画書_関連研究_定性・定量研究
17:30 研究計画書_関連研究_定性・定量研究
18:00 夕食
18:30 夕食
19:00 free
19:30 風呂
20:00 風呂
20:30 free
21:00 free
21:30 free
22:00 free
22:30 free

今後の展望

とりあえず動くものができたので一安心です。修正したい点はいくつかあるので、そこも随時直してみようと思います。

また、せっかく1日の計画を自動で作るプログラムができたので、UIを整えてよりインタラクティブなシステムにしてみたいとも考えています。

参考文献

  1. Martins, J. (2026). 時間区切りのテクニック: 明確な目標を設定した時間管理戦略. Asana. https://asana.com/ja/resources/what-is-timeboxing ↩

  2. Rogers, R. D., & Monsell, S. (1995). Costs of a predictible switch between simple cognitive tasks. Journal of experimental psychology: General, 124(2), 207. https://psycnet.apa.org/doiLanding?doi=10.1037%2F0096-3445.124.2.207 ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?