fork download
copy 
  1. """
  2. BÀI TOÁN XẾP LỊCH HỌC (Class Scheduling with OR-Tools)
  3. =========================================================
  4.  
  5. PROBLEM STATEMENT:
  6.   Cho n lớp học và m phòng. Mỗi lớp thứ i trong n lớp có:
  7.   - Thời lượng d[i], giáo viên dạy g[i], sĩ số s[i]
  8.   Mỗi phòng j trong m phòng có:
  9.   - Sức chứa c[j]
  10.   Thời lượng của mỗi ngày:
  11.   - 12 tiết
  12.   Mỗi ngày có hai nửa ngày:
  13.   - Mỗi nửa gồm 6 tiết
  14.  
  15.   Yêu cầu: Xếp lịch và gán phòng cho 1 tuần sao cho:
  16.   1. Tổng thời lượng trong một tuần gồm 5 ngày (tổng cộng 5*12 = 60 tiết)
  17.   2. Một lớp không được dài vượt quá nửa hoặc cuối ngày
  18.   3. Một giáo viên không dạy trùng tkb
  19.   4. Phòng đủ sức chứa cho lớp
  20.   5. Tối đa hóa số lớp được xếp
  21.  
  22. APPROACH:
  23.   Two-phase CP-SAT solving:
  24.   - Phase 1 (Time Model): Xếp thời gian hợp lệ, tối đa hóa số lớp
  25.   - Phase 2 (Room Model): Gán phòng cho các lớp đã xếp thời gian
  26.  
  27. INPUT/OUTPUT:
  28.   Input:  input.txt (n, m, d[i], g[i], s[i], c[j])
  29.   Output: output.txt (class_id start_time room_id for each scheduled_class)
  30. """
  31.  
  32. from ortools.sat.python import cp_model
  33. import sys
  34. import os
  35.  
  36.  
  37. # ╔══════════════════════════════════════════════════════════════════════════╗
  38. # ║                     PHẦN 1: DỮ LIỆU INPUT & HẰNG SỐ                      ║
  39. # ╚══════════════════════════════════════════════════════════════════════════╝
  40.  
  41. # -------- Dữ liệu đầu vào từ input.txt --------
  42. n, m = 0, 0         # Số lớp, số phòng
  43. duration = []       # duration[i] = thời lượng lớp i
  44. teacher = []        # teacher[i] = ID giáo viên dạy lớp i
  45. attend = []         # attend[i] = sĩ số lớp i
  46. capacity = []       # capacity[j] = sức chứa phòng j
  47.  
  48. # -------- Hằng số lịch học --------
  49. num_day = 5                         # Số ngày trong tuần
  50. num_half_day = num_day * 2          # Tổng nửa ngày (10 nửa)
  51. day_time = 12                       # Thời gian 1 ngày
  52. half_day_time = int(day_time / 2)   # Thời gian 1 nửa ngày = 6
  53.  
  54. # Khoảng thời gian cho nửa ngày i
  55. # start_half[i] = thời gian bắt đầu nửa thứ i
  56. # end_half[i]   = thời gian kết thúc nửa thứ i
  57. start_half = [i * half_day_time + 1 for i in range(num_day * 2)]
  58. end_half = [start_half[i] + half_day_time - 1 for i in range(len(start_half))]
  59.  
  60.  
  61. # ╔══════════════════════════════════════════════════════════════════════════╗
  62. # ║               PHẦN 2: MODEL 1 - TIME SCHEDULING (Biến Toàn Cục)         ║
  63. # ╚══════════════════════════════════════════════════════════════════════════╝
  64.  
  65. time_model = None  # CP-SAT model cho phase 1
  66.  
  67. # Biến quyết định cho time model:
  68. start = []          # start[i] = thời gian bắt đầu lớp i (nếu được xếp)
  69. is_present = []     # is_present[i] = 1 nếu lớp i được xếp, 0 nếu không
  70. intervals = []      # intervals[i] = khoảng thời gian của lớp i
  71.  
  72.  
  73. # ╔══════════════════════════════════════════════════════════════════════════╗
  74. # ║               PHẦN 3: MODEL 2 - ROOM ASSIGNMENT (Biến Toàn Cục)         ║
  75. # ╚══════════════════════════════════════════════════════════════════════════╝
  76.  
  77. room_model = None        # CP-SAT model cho phase 2
  78. room_var = []            # room_var[i] = phòng được gán cho scheduled_classes[i]
  79. scheduled_classes = []   # Danh sách lớp đã được xếp thời gian (từ phase 1)
  80. Q = 0                    # Số lớp thực sự được xếp (tính sau phase 1)
  81.  
  82.  
  83. # ╔══════════════════════════════════════════════════════════════════════════╗
  84. # ║                    PHẦN 4: FILE OUTPUT (OJ Mode)                         ║
  85. # ╚══════════════════════════════════════════════════════════════════════════╝
  86.  
  87. stat_file = open(os.devnull, 'w')       # Thống kê solver
  88. viz_file = open(os.devnull, 'w')        # Visualization data
  89. time_log_file = open(os.devnull, 'w')   # Log của time solver
  90. room_log_file = open(os.devnull, 'w')   # Log của room solver
  91.  
  92.  
  93. # ╔══════════════════════════════════════════════════════════════════════════╗
  94. # ║                   PHẦN 5: HÀM I/O (Input/Output)                         ║
  95. # ╚══════════════════════════════════════════════════════════════════════════╝
  96.  
  97. def setup_files():
  98.     """
  99.     Định tuyến các luồng input/output nếu file tồn tại (OJ mode).
  100.  
  101.     Nếu tồn tại input.txt:
  102.     - stdin  ← input.txt
  103.     - stdout ← output.txt
  104.     - Mở các file log (stat.txt, viz.txt, time_log.txt, room_log.txt)
  105.     """
  106.     global stat_file, viz_file, time_log_file, room_log_file
  107.  
  108.     if os.path.exists('input.txt'):
  109.         sys.stdin = open('input.txt', 'r', encoding='utf-8')
  110.         sys.stdout = open('output.txt', 'w', encoding='utf-8')
  111.  
  112.         stat_file = open('stat.txt', 'w', encoding="utf-8")
  113.         viz_file = open('viz.txt', 'w', encoding="utf-8")
  114.         time_log_file = open("time_log.txt", "w", encoding="utf-8")
  115.         room_log_file = open("room_log.txt", "w", encoding="utf-8")
  116.  
  117.  
  118. def input_data():
  119.     """
  120.     Đọc dữ liệu từ stdin (hoặc input.txt nếu ở OJ mode).
  121.  
  122.     Format:
  123.       Line 1: n m (số lớp, số phòng)
  124.       Line 2..n+1: duration[i] teacher[i] attend[i]
  125.       Line n+2: capacity[0] capacity[1] ... capacity[m-1]
  126.     """
  127.     global n, m, duration, teacher, attend, capacity
  128.  
  129.     n, m = map(int, input().split())
  130.  
  131.     for _ in range(n):
  132.         i, j, k = map(int, input().split())
  133.         duration.append(i)
  134.         teacher.append(j)
  135.         attend.append(k)
  136.  
  137.     capacity = list(map(int, input().split()))
  138.  
  139.  
  140. def write_output(final_assignments):
  141.     """
  142.     Ghi kết quả cuối cùng ra stdout (nếu ở OJ MODE) hoặc ra output.txt ở LOCAL
  143.  
  144.     Format:
  145.       Line 1: Q (số lớp được xếp)
  146.       Line 2..Q+1: class_id+1 start_time room_id+1
  147.     """
  148.     print(Q)
  149.     for cls_id, start_time, room_id, dur, tch, att, cap in final_assignments:
  150.         print(f"{cls_id+1} {start_time} {room_id+1}")
  151.  
  152.  
  153. def write_viz_output(time_solver, status, final_assignments):
  154.     """
  155.     Ghi thông tin visualization ra viz.txt (cho debug/analysis).
  156.  
  157.     Format:
  158.       Line 1: time_solver status name
  159.       Line 2..Q+1: class_id+1 start_time room_id+1 duration teacher attend room_capacity
  160.       Line Q+2: sức chứa các phòng học
  161.     """
  162.     print("time_solver status:", time_solver.status_name(status), file=viz_file)
  163.     if status in [cp_model.OPTIMAL, cp_model.FEASIBLE]:
  164.         for cls_id, start_time, room_id, dur, tch, att, cap in final_assignments:
  165.             print(f"{cls_id+1} {start_time} {room_id+1} {dur} {tch} {att} {cap}", 
  166.                   file=viz_file)
  167.     print(" ".join(map(str, capacity)), file=viz_file)
  168.  
  169.  
  170. def time_log_to_file(msg):
  171.     """Ghi log từ time solver vào file."""
  172.     time_log_file.write(msg + "\n")
  173.     time_log_file.flush()
  174.  
  175.  
  176. def room_log_to_file(msg):
  177.     """Ghi log từ room solver vào file."""
  178.     room_log_file.write(msg + "\n")
  179.     room_log_file.flush()
  180.  
  181.  
  182. # ╔══════════════════════════════════════════════════════════════════════════╗
  183. # ║            PHẦN 6: PHASE 1 - TIME SCHEDULING MODEL                       ║
  184. # ╚══════════════════════════════════════════════════════════════════════════╝
  185.  
  186. def define_time_model():
  187.     """Khởi tạo CP-SAT model cho phase 1 (xếp thời gian)."""
  188.     global time_model
  189.     time_model = cp_model.CpModel()
  190.  
  191.  
  192. def make_non_overlapping_half_day_and_end_day():
  193.     """
  194.     Ràng buộc 1: Lớp không được dài đè lên nửa ngày hoặc cuối ngày.
  195.  
  196.     Logic:
  197.       - Mỗi lớp chỉ được bắt đầu tại các vị trí trong nửa ngày
  198.       - Nếu duration[i] <= half_day_time, có thể fit vào 1 nửa ngày
  199.       - Tạo domain chứa các khoảng thời gian hợp lệ
  200.       - Thêm biến is_present[i] (optional): lớp i có được xếp?
  201.     """
  202.     global start, is_present, intervals
  203.  
  204.     for cur_class in range(n):
  205.         valid_intervals = []
  206.  
  207.         # Lớp chỉ hợp lệ nếu duration không quá nửa ngày
  208.         if duration[cur_class] <= half_day_time:
  209.             for s in range(len(start_half)):
  210.                 valid_intervals.append([
  211.                     start_half[s], end_half[s] - duration[cur_class] + 1
  212.                 ])
  213.  
  214.         # Tạo biến start[cur_class] với domain là các khoảng hợp lệ
  215.         domain = cp_model.Domain.from_intervals(valid_intervals)
  216.         start.append(time_model.new_int_var_from_domain(domain, f"start_{cur_class+1}"))
  217.  
  218.         # Biến is_present: 1 nếu lớp được xếp, 0 nếu không
  219.         is_present.append(time_model.new_bool_var(f"is_present_{cur_class+1}"))
  220.  
  221.         # Optional interval: chỉ tồn tại nếu is_present[i] = 1
  222.         intervals.append(time_model.new_optional_fixed_size_interval_var(
  223.             start[-1], duration[cur_class], is_present[-1], f"interval_{cur_class+1}"
  224.         ))
  225.  
  226.  
  227. def make_non_overlapping_classes_by_teacher():
  228.     """
  229.     Ràng buộc 2: Một giáo viên không dạy trùng giờ.
  230.  
  231.     Logic:
  232.       - Nhóm các lớp theo giáo viên
  233.       - Thêm no_overlap constraint cho từng giáo viên
  234.         (các lớp của cùng 1 giáo viên không được giao nhau về thời gian)
  235.     """
  236.     teachers_set = set(teacher)
  237.     class_intervals_by_teacher = {key: [] for key in teachers_set}
  238.  
  239.     for i in range(n):
  240.         class_intervals_by_teacher[teacher[i]].append(intervals[i])
  241.  
  242.     for t_intervals in class_intervals_by_teacher.values():
  243.         if len(t_intervals) > 1:
  244.             time_model.add_no_overlap(t_intervals)
  245.  
  246.  
  247. def make_limited_overlapping_classes():
  248.     """
  249.     Ràng buộc 3: Sức chứa phòng (Cumulative Constraint).
  250.  
  251.     Logic:
  252.       - Các lớp có cùng "sĩ số threshold" cần phòng có sức chứa >= threshold
  253.       - Đếm số phòng hợp lệ cho mỗi threshold
  254.       - Đảm bảo "độ đè lịch" (overlapping degree) không vượt số phòng
  255.  
  256.     Ví dụ:
  257.       - Lớp A: 40 sinh viên → có 25 phòng capacity >= 40
  258.       - Lớp B: 40 sinh viên → có 25 phòng capacity >= 40
  259.       - Lớp C:...
  260.       - Giới hạn: tối đa 25 lớp như lớp A,B,C (với sĩ số >= 40) có thể xếp trùng giờ
  261.  
  262.     Mục đích:
  263.       - Tách biệt phase thời gian với phase gán phòng
  264.     """
  265.     unique_attend_thresholds = sorted(list(set(attend)))
  266.  
  267.     for attend_threshold in unique_attend_thresholds:
  268.         # Đếm số phòng đủ sức chứa cho threshold này
  269.         num_rooms_available = sum(1 for c in capacity if c >= attend_threshold)
  270.  
  271.         # Danh sách lớp có sĩ số >= threshold
  272.         classes_demanding_this_tier = [
  273.             intervals[i] for i in range(n) if attend[i] >= attend_threshold
  274.         ]
  275.  
  276.         # Cumulative constraint: 
  277.         # độ đè lịch của các lớp có cùng threshold <= số phòng hợp lệ
  278.         if classes_demanding_this_tier:
  279.             time_model.add_cumulative(
  280.                 classes_demanding_this_tier,
  281.                 [1] * len(classes_demanding_this_tier),
  282.                 num_rooms_available
  283.             )
  284.  
  285.  
  286. def define_objective():
  287.     """
  288.     Hàm mục tiêu cho phase 1: Tối đa hóa số lớp được xếp.
  289.     """
  290.     time_model.maximize(cp_model.LinearExpr.sum(is_present))
  291.  
  292.  
  293. def solve_time_model():
  294.     """
  295.     Giải phase 1 (time model) và ghi thống kê.
  296.  
  297.     Return:
  298.       (time_solver, status)
  299.     """
  300.     time_solver = cp_model.CpSolver()
  301.  
  302.     # Thời gian tối đa cho solver
  303.     time_solver.parameters.max_time_in_seconds = 60
  304.  
  305.     # Setup log
  306.     time_solver.parameters.log_search_progress = True
  307.     time_solver.parameters.log_to_stdout = False
  308.     time_solver.log_callback = time_log_to_file
  309.  
  310.     # Giải
  311.     status = time_solver.solve(time_model)
  312.  
  313.     # Ghi thống kê
  314.     print("\n=== Statistics Time Solver ===", file=stat_file)
  315.     print(f"  Status       : {time_solver.status_name(status)}", file=stat_file)
  316.     print(f"  Conflicts    : {time_solver.num_conflicts}", file=stat_file)
  317.     print(f"  Branches     : {time_solver.num_branches}", file=stat_file)
  318.     print(f"  Wall time    : {time_solver.wall_time}s", file=stat_file)
  319.  
  320.     return time_solver, status
  321.  
  322.  
  323. # ╔══════════════════════════════════════════════════════════════════════════╗
  324. # ║            PHẦN 7: PHASE 2 - ROOM ASSIGNMENT MODEL                       ║
  325. # ╚══════════════════════════════════════════════════════════════════════════╝
  326.  
  327. def define_room_model(time_solver):
  328.     """
  329.     Khởi tạo phase 2 (room model) dựa trên kết quả phase 1.
  330.  
  331.     Logic:
  332.       1. Lọc ra danh sách lớp đã được xếp thời gian (is_present[i] = 1)
  333.       2. Tạo room_var[j] cho mỗi lớp (chỉ số phòng được gán)
  334.       3. Cập nhật global Q (số lớp thực sự được xếp)
  335.     """
  336.     global room_model, room_var, scheduled_classes, Q
  337.  
  338.     room_model = cp_model.CpModel()
  339.  
  340.     # Q = số lớp được xếp từ phase 1
  341.     Q = int(time_solver.value(cp_model.LinearExpr.sum(is_present)))
  342.  
  343.     # Xây dựng danh sách lớp đã xếp
  344.     scheduled_classes = []
  345.     for i in range(n):
  346.         if time_solver.value(is_present[i]):  # Lớp i được xếp
  347.             s = time_solver.value(start[i])
  348.             scheduled_classes.append({
  349.                 'id': i,
  350.                 'start': s,
  351.                 'end': s + duration[i],
  352.                 'attend': attend[i]
  353.             })
  354.  
  355.     # room_var[j] = ID phòng được gán cho scheduled_classes[j]
  356.     room_var = [
  357.         room_model.new_int_var(0, m - 1, f"room_var_{j}") 
  358.         for j in range(Q)
  359.     ]
  360.  
  361.  
  362. def make_non_overloaded_room():
  363.     """
  364.     Ràng buộc 1 (Room Model): Sức chứa phòng >= sĩ số lớp.
  365.  
  366.     Logic:
  367.       - Cho mỗi lớp đã xếp
  368.       - Tìm danh sách phòng có sức chứa >= attend[class]
  369.       - Sử dụng add_allowed_assignments để giới hạn room_var
  370.     """
  371.     for i, cls in enumerate(scheduled_classes):
  372.         # Tìm phòng hợp lệ
  373.         valid_rooms = [r for r in range(m) if capacity[r] >= cls['attend']]
  374.  
  375.         if valid_rooms:
  376.             room_model.add_allowed_assignments(
  377.                 [room_var[i]],
  378.                 [[r] for r in valid_rooms]
  379.             )
  380.         else:
  381.             # Nếu không tìm thấy phòng hợp lệ thì skip 
  382.             # (trường hợp này không nên xảy ra)
  383.             continue
  384.  
  385.  
  386. def make_non_overlapping_classes_in_same_room():
  387.     """
  388.     Ràng buộc 2 (Room Model): Hai lớp trùng giờ phải ở phòng khác.
  389.  
  390.     Logic:
  391.       - Kiểm tra xem hai lớp có giao nhau về thời gian?
  392.       - Nếu có giao nhau: room_var[i] != room_var[j]
  393.  
  394.     Overlap condition:
  395.       Hai lớp giao nhau nếu: start_i < end_j AND start_j < end_i
  396.     """
  397.     for i in range(Q):
  398.         for j in range(i + 1, Q):
  399.             ci, cj = scheduled_classes[i], scheduled_classes[j]
  400.  
  401.             # Kiểm tra xem ci và cj có giao nhau?
  402.             # --> Giả sử có 2 lớp học ci và cj. 
  403.             # Hai lớp này KHÔNG TRÙNG GIỜ (không giao nhau) 
  404.             # khi xảy ra 1 trong 2 trường hợp sau:
  405.             # HOẶC: ci['end'] <= cj['start']
  406.             # HOẶC: cj['end'] <= ci['start']
  407.             # Theo định lý De Morgan, phủ định của (A <= B hoặc C <= D) 
  408.             # chính là (A > B VÀ C > D).
  409.             if ci['start'] < cj['end'] and cj['start'] < ci['end']:
  410.                 # Nếu giao nhau: phải gán vào 2 phòng khác nhau
  411.                 room_model.add(room_var[i] != room_var[j])
  412.  
  413.  
  414. def solve_room_model():
  415.     """
  416.     Giải phase 2 (room model) và ghi thống kê.
  417.  
  418.     Return:
  419.       (room_solver, status)
  420.     """
  421.     room_solver = cp_model.CpSolver()
  422.  
  423.     # Thời gian tối đa cho solver
  424.     room_solver.parameters.max_time_in_seconds = 10
  425.  
  426.     # Setup log
  427.     room_solver.parameters.log_search_progress = True
  428.     room_solver.parameters.log_to_stdout = False
  429.     room_solver.log_callback = room_log_to_file
  430.  
  431.     # Giải
  432.     room_status = room_solver.solve(room_model)
  433.  
  434.     # Ghi thống kê
  435.     print("\n=== Statistics Room Solver ===", file=stat_file)
  436.     print(f"  Status       : {room_solver.status_name(room_status)}", file=stat_file)
  437.     print(f"  Conflicts    : {room_solver.num_conflicts}", file=stat_file)
  438.     print(f"  Branches     : {room_solver.num_branches}", file=stat_file)
  439.     print(f"  Wall time    : {room_solver.wall_time}s", file=stat_file)
  440.  
  441.     return room_solver, room_status
  442.  
  443.  
  444. # ╔══════════════════════════════════════════════════════════════════════════╗
  445. # ║                   PHẦN 8: ENTRY POINT - MAIN FUNCTION                    ║
  446. # ╚══════════════════════════════════════════════════════════════════════════╝
  447.  
  448. def main():
  449.     """
  450.     Luồng chính của chương trình.
  451.  
  452.     Bước 1: Setup I/O (dùng input.txt nếu ở OJ mode)
  453.     Bước 2: Đọc dữ liệu đầu vào
  454.     Bước 3: Phase 1 - Time Scheduling
  455.             - Định nghĩa model + constraints + objective
  456.             - Giải → nhận danh sách thời gian hợp lệ
  457.     Bước 4: Phase 2 - Room Assignment
  458.             - Từ danh sách thời gian, gán phòng
  459.             - Giải → nhận gán phòng cuối cùng
  460.     Bước 5: Ghi nhận final assignment
  461.     Bước 6: Output kết quả
  462.     """
  463.  
  464.     # --- Bước 1: Setup ---
  465.     setup_files()
  466.  
  467.  
  468.     # --- Bước 2: Input ---
  469.     input_data()
  470.  
  471.     # --- Bước 3: Phase 1 - TIME SCHEDULING ---
  472.     define_time_model()
  473.     make_non_overlapping_half_day_and_end_day()
  474.     make_non_overlapping_classes_by_teacher()
  475.     make_limited_overlapping_classes()
  476.     define_objective()
  477.     time_solver, time_status = solve_time_model()
  478.     if time_status not in [cp_model.OPTIMAL, cp_model.FEASIBLE]: return
  479.  
  480.  
  481.     # --- Bước 4: Phase 2 - ROOM ASSIGNMENT ---  
  482.     define_room_model(time_solver)
  483.     make_non_overloaded_room()
  484.     make_non_overlapping_classes_in_same_room()
  485.     room_solver, room_status = solve_room_model()
  486.     if room_status not in [cp_model.OPTIMAL, cp_model.FEASIBLE]: return
  487.  
  488.  
  489.     # --- Bước 5: Build final assignments ---
  490.     final_assignments = []
  491.     for i, cls in enumerate(scheduled_classes):
  492.         r = room_solver.value(room_var[i])
  493.         final_assignments.append((
  494.             cls['id'], cls['start'], r,
  495.             duration[cls['id']], teacher[cls['id']], attend[cls['id']], capacity[r]
  496.         ))
  497.  
  498.  
  499.     # --- Bước 6: Output ---
  500.     write_output(final_assignments)
  501.     write_viz_output(time_solver, time_status, final_assignments)
  502.  
  503.  
  504. if __name__ == "__main__":
  505.     main()
Runtime error #stdin #stdout #stderr 0.79s 36940KB
comments (?)
stdin
copy 
10 2
4 1 15
4 1 18
4 1 15
2 2 18
4 2 11
3 1 15
2 2 27
3 2 18
4 1 13
3 1 10
20 20
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 32, in <module>
ModuleNotFoundError: No module named 'ortools'
https://ideone.com/QKX9D1
Bài toán lập lịch thời khóa biểu với input(n, m, d[i], g[i], s[i], c[j])
language:
Python 3 (python  3.12)
created:
5 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!