Thuật toán nào để sử dụng để tạo bảng thời gian cho các trường học

Question

Tôi đang làm việc trên một ứng dụng đơn giản sẽ tạo bảng thời gian (kế hoạch hàng ngày) cho các trường học. Tôi đã đọc các khái niệm cơ bản về thuật toán, nhưng bị nhầm lẫn về nơi bắt đầu.

Vấn đề:
Phân bổ giáo viên đến các lớp học có tính đến rất nhiều khó khăn như:
1) Chủ đề
2) Chuyên môn của giáo viên
3) Không quá 2 lớp liên tục .. vv

Không cần phải nói rằng không nên trùng lặp. Về cơ bản, tôi cần phải chỉ định N giáo viên cho các lớp M với số giờ làm việc cố định hàng ngày (8).

Đầu vào:
1) Tổng số lớp
2) Giáo viên cùng với chuyên môn chuyên môn của mình
3) Đối tượng/khóa học cho mỗi lớp
4) Số lượng bài giảng mỗi lớp mỗi ngày
5) Các ràng buộc linh hoạt khác như giờ làm việc tối thiểu/tối đa cho giáo viên mỗi ngày, tổng số giờ làm việc cho mỗi giáo viên mỗi tuần, v.v.

Câu hỏi của tôi:
1) Có đúng không để xem nó như là một bài toán gán với nhiều ràng buộc?
2) Tôi nên sử dụng thuật toán nào? (Thuật toán Hungary?)
3) Tôi có nên bắt đầu bằng cách nhận toàn bộ các ràng buộc tại một lần, sau đó tạo bảng hay nó nên được thực hiện trong các bước trung gian?

Tôi là người mới bắt đầu học/triển khai thuật toán, vì vậy mọi trợ giúp đều chỉ cho tôi đúng hướng được đánh giá cao! Cảm ơn.

Answer 1

Bạn đã chọn một vấn đề khó khăn để bắt đầu. Lập lịch trình tối ưu hóa như thế này là NP hoàn thành. Có rất nhiều giấy tờ về cách đối phó với các vấn đề như thế này, lớp học của vấn đề được gọi là hạn chế sự hài lòng. Bạn có thể thực hiện tìm kiếm toàn diện dễ dàng nhất nhưng cũng rất tốn thời gian, nếu bạn có nhiều hơn một số lớp, nó sẽ không hoạt động. Bạn có thể nhìn vào nền tảng giải quyết là một bộ công cụ cho .net để giải quyết những thứ này. Scott Hanselman đã thực hiện một podcast về nó tại đây http://www.hanselminutes.com/default.aspx?showID=209 và bạn có thể tìm hiểu thêm về nó tại đây http://code.msdn.microsoft.com/solverfoundation. Nếu bạn ưa thích tự mình thử xem GSAT hay nói cách khác, một số thuật toán tiến hóa này trông thú vị http://www.springer.com/engineering/book/978-3-540-48582-7.

Answer 2

Câu hỏi này liên tục xuất hiện ít nhất một lần một tuần tại đây và câu trả lời (bao gồm cả tôi) luôn giống nhau. Tôi nghĩ chúng ta nên tạo một thẻ cụ thể trên các thuật toán lập lịch biểu nếu một thuật toán không tồn tại.

Tôi sẽ nhắc lại rằng kỹ thuật giải pháp phù hợp nhất để lên lịch các vấn đề như thế này nằm trong khu vực lập trình hạn chế. Trong khi các kỹ thuật tối ưu hóa khác là OK cho các vấn đề nhỏ, xây dựng thường là đau khổ đối với một số khó khăn. Hãy xem xét tất cả các biến số nguyên mà bạn phải tạo cho một số ràng buộc đơn giản. Bởi vì vấn đề thường đòi hỏi một loạt các lịch trình khả thi (hoặc để xác định tính khả thi) hơn là một giải pháp tối ưu, CP là phương pháp ưa thích vì đó là những gì nó được thiết kế để làm. Hầu hết các cách tiếp cận khác yêu cầu người dùng "buộc" một điều kiện tối ưu về vấn đề mà một người không thực sự tồn tại.