Tối ưu lập kế hoạch

Học kỳ: 20202
Topics: Semester exam scheduling

Đề bài

Mô tả

• Có N môn 1,2,...,N cần được xếp lịch thi
• Môn i có số lượng sinh viên đăng ký thi là d(i)
• Giữa N môn thi có danh sách các cặp 2 môn (i,j) không thể xếp trùng kíp, ngày
• Có M phòng thi 1,2,...,M, trong đó phòng j có số lượng chỗ ngồi là c(j)
• Mỗi ngày được chia thành 4 kíp
  

=> Hãy lập kế hoạch bố trí lịch và phòng cho các môn thi sao cho tổng số ngày diễn ra N môn thi là nhỏ nhất

Đầu vào

• Dòng 1: N
• Dòng 2: d₁, d₂, ..., d_N
• Dòng 3: M
• Dòng 4: c₁, c₂, ..., c_<
• Dòng 5: K nguyên dương
• Dòng 5+k (k=1,...,K): các cặp i, j

Hướng dẫn cài đặt OR-Tools Java

OS: Ubuntu 20.04 LTS
Chú ý: OR-Tools là thư viện C++, vì vậy, với Windows OS, đảm bảo cài đặt MingW. Đảm bảo thêm các biến mỗi trường và thêm vào Path đầy đủ

Cài đặt môi trường

sudo apt-get install openjdk-11-jdk
sudo apt-get install maven

Cài đặt OR-Tools

Tải xuống và giải nén: OR-Tools for Ubuntu 20.04 LTS

Kiểm tra cài đặt

Đi tới thư mục vừa giải nén

make test_java

Nếu các ví dụ chạy thành công, OR-Tools đã sẵn sàng