PuLP Coding Challenges | #070325 | Hard

Phân bổ các nhiệm vụ (tasks) cho các tài nguyên (resources) trong một khoảng thời gian nhất định, sao cho:

Giảm thiểu số lượng tài nguyên được sử dụng.
Đảm bảo không có chồng chéo thời gian giữa các nhiệm vụ được gán cho cùng một tài nguyên.
Mỗi nhiệm vụ được phân bổ đúng một tài nguyên và một ngày bắt đầu phù hợp trong khoảng thời gian cho phép.
Dữ liệu đầu vào gồm:
- Mã nhiệm vụ (ID): Ví dụ, 1, 2, 3…
- Số giờ cần phân bổ: Chuyển đổi thành số ngày (8 giờ = 1 ngày).
- Khoảng thời gian khả dụng: Ngày bắt đầu và ngày kết thúc (định dạng như “22W211” – tuần 21 năm 2022, ngày thứ Hai).
- Danh sách tài nguyên: Các tài nguyên có thể gán cho từng nhiệm vụ (ví dụ: RES1, RES2, RES3).

GIẢI THÍCH KẾT QUẢ:

Nhiệm vụ 4 (Res4: 6/16/2021 – 6/16/2021)
- Thời gian: Kéo dài 1 ngày (6/16/2021). Tài nguyên: Res4.
- Đây là nhiệm vụ đầu tiên trong bảng sử dụng Res4, chỉ chiếm 1 ngày, không có nhiệm vụ nào khác trong khoảng thời gian này, nên không xảy ra chồng chéo.
Nhiệm vụ 5 (Res4: 6/21/2021 – 6/23/2021)
- Thời gian: 3 ngày (6/21/2021 – 6/23/2021). Tài nguyên: Res4.
- Bắt đầu sau khi nhiệm vụ 4 kết thúc (6/16/2021). Khoảng cách từ 6/16/2021 đến 6/21/2021, không có chồng chéo với nhiệm vụ trước.
Nhiệm vụ 6 (Res4: 6/24/2021 – 6/25/2021)
- Thời gian: 2 ngày (6/24/2021 – 6/25/2021). Tài nguyên: Res4.
- Bắt đầu ngay sau khi nhiệm vụ 5 kết thúc (6/23/2021), không chồng chéo vì thời gian được sắp xếp liên tục.
Nhiệm vụ 2 (Res4: 5/23/2022 – 5/27/2022)
- Thời gian: 5 ngày (5/23/2022 – 5/27/2022). Tài nguyên: Res4.
- Nhảy từ năm 2021 sang 2022, sau nhiệm vụ 6 (kết thúc 6/25/2021) có một khoảng thời gian dài không sử dụng Res4. Nhiệm vụ 2 bắt đầu vào 5/23/2022, không có chồng chéo với các nhiệm vụ trước trên Res4.
Nhiệm vụ 10 (Res2: 5/23/2022 – 6/6/2022)
- Thời gian: 15 ngày (5/23/2022 – 6/6/2022). Tài nguyên: Res2.
- Bắt đầu cùng ngày với nhiệm vụ 2 (5/23/2022), nhưng được gán cho Res2 thay vì Res4. Điều này hợp lý vì Res4 đang được sử dụng cho nhiệm vụ 2 (5/23/2022 – 5/27/2022), và việc dùng Res2 giúp tránh chồng chéo.
Nhiệm vụ 9 (Res4: 5/30/2022 – 6/3/2022)
- Thời gian: 5 ngày (5/30/2022 – 6/3/2022). Tài nguyên: Res4.
  Bắt đầu sau khi nhiệm vụ 2 kết thúc (5/27/2022), không chồng chéo với nhiệm vụ trước trên Res4.
Nhiệm vụ 8 (Res2: 6/7/2022 – 7/6/2022)
- Thời gian: 30 ngày (6/7/2022 – 7/6/2022). Tài nguyên: Res2.
- Bắt đầu ngay sau khi nhiệm vụ 10 kết thúc (6/6/2022) trên Res2. Trong khoảng thời gian này, Res4 được sử dụng cho các nhiệm vụ khác (như nhiệm vụ 9 và sau đó là nhiệm vụ 7), nên Res2 là lựa chọn phù hợp để tránh chồng chéo.
Nhiệm vụ 7 (Res4: 6/20/2022 – 7/4/2022)
- Thời gian: 15 ngày (6/20/2022 – 7/4/2022). Tài nguyên: Res4.
- Bắt đầu sau khi nhiệm vụ 9 kết thúc (6/3/2022), không chồng chéo với nhiệm vụ trước trên Res4.
Nhiệm vụ 3 (Res4: 7/5/2022 – 7/14/2022)
- Thời gian: 10 ngày (7/5/2022 – 7/14/2022). Tài nguyên: Res4.
- Bắt đầu ngay sau khi nhiệm vụ 7 kết thúc (7/4/2022), liên tục và không chồng chéo trên Res4.
Nhiệm vụ 1 (Res4: 7/15/2022 – 7/29/2022)
- Thời gian: 15 ngày (7/15/2022 – 7/29/2022). Tài nguyên: Res4.
- Bắt đầu ngay sau khi nhiệm vụ 3 kết thúc (7/14/2022), đảm bảo tính liên tục và không có chồng chéo trên Res4.
Res4: Được sử dụng cho các nhiệm vụ 4, 5, 6, 2, 9, 7, 3, 1. Các nhiệm vụ này được sắp xếp liên tiếp theo thời gian mà không chồng chéo.
Res2: Được sử dụng cho các nhiệm vụ 10 và 8, chủ yếu cho các nhiệm vụ dài hơn và diễn ra song song với các nhiệm vụ trên Res4.
Chỉ có 2 tài nguyên (Res4 và Res2) được sử dụng trong toàn bộ bảng phân bổ