Chương 1: Tổng quan về bài toán lập lịch Giới thiệu về bài toán lập lịch, những đặc trƣng cơ bản và hƣớng tiếp cận nghiên cứu, bài toán xếp thời khóa biểu ở trƣờng phổ thông. Giới thiệu nghiên cứu một dạng cụ thể của bài toán lập lịch là bài toán xếp thời khóa biểu. Chương 2: Một số hướng tiếp cận và thuật toán giải bài toán xếp thời khoá biểu Tìm hiểu về một số giải thuật giải bài toán, đánh giá các giải thuật và đề xuất giải thuật giải bài toán. Chương 3: Thiết kế chương trình xếp thời khóa biểu chính khóa trường Phổ Thông Vùng Việt Bắc Phân tích thiết kế hệ thống, áp dụng giải thuật tối ƣu hóa đàn kiến, đánh giá khả năng ứng dụng để giải quyết bài toán thời khóa biểu.
Các bƣớc thực hiện: thiết kế dữ liệu, ý tƣởng thuật toán, xây dựng chƣơng trình, nhận xét. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 CHƢƠNG 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH 1. Giới thiệu chung về bài toán lập lịch Bài toán cần xác định trình tự thời gian thực hiện các công việc trong điều kiện ràng buộc về tài nguyên cần thiết sử dụng để thực hiện các công việc bài toán đó đƣợc phân loại là Bài toán lập lịch. - Lập lịch có thể đƣợc định nghĩa là một bài toán tìm kiếm chuỗi tối ƣu để thực hiện một tập các hoạt động chịu tác động của một tập các ràng buộc cần phải đƣợc thỏa mãn.
Ngƣời lập lịch thƣờng cố gắng thử đến mức tối đa sự sử dụng các cá thể, máy móc và tối thiểu thời gian đòi hỏi để hoàn thành toàn bộ quá trình nhằm sắp xếp lịch. Vì thế bài toán lập lịch là một vấn đề rất khó để giải quyết. Hiện nay có nhiều khả năng để phát triển các kỹ thuật hiện tại để giải quyết bài toán này. Những kỹ thuật đó bao gồm: Các tiếp cận Trí tuệ nhân tạo nhƣ hệ thống tri thức cơ sở (knowledge-based systems), bài toán thoả mãn ràng buộc, hệ chuyên gia, mạng Nơron và các tiếp cận của các nghiên cứu hoạt động: lập trình tính toán, lập trình động, tìm kiếm nhánh và đƣờng biên, kỹ thuật mô phỏng, tìm kiếm Tabu và phƣơng pháp nút cổ chai 1.
Các đặc trƣng của bài toán lập lịch Khi nghiên cứu về bài toán lập lịch cần làm rõ các đặc trƣng cơ bản của bài toán. Các đặc trƣng cơ bản đó bao gồm: Tập công việc, tài nguyên, tác vụ, ràng buộc và mục tiêu. - Tập công việc: Mô tả tính chất công việc (lập danh sách môn học, lập danh sách giáo viên, lập danh sách phòng học, lập bảng thông tin môn học.) - Tài nguyên: Là các dữ liệu đầu vào để giải quyết bài. Các tài nguyên này có thể phục hồi hoặc không.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 - Thời gian giới hạn: Mô tả các dạng thời gian (trình tự, thời điểm, khoảng thời gian – ca học – tiết học,.) - Ràng buộc: Đây là những điều kiện cần thỏa mãn để bài toán có thể đƣa đƣợc lời giải tốt nhất. - Mục tiêu: Đánh giá độ tối ƣu của lịch trình lời giải của bài toán. Khi các mục tiêu đƣợc thỏa mãn thì các ràng buộc cũng đƣợc thỏa mãn. Đánh giá độ phức tạp của bài toán lập lịch: vấn đề ràng buộc tài nguyên trong bài toán lập lịch rất đa dạng và phức tạp.
Thông thƣờng các vấn đề liên quan đến ràng buộc về tài nguyên trong bài toán lập lịch thƣờng xảy ra trong tình huống lƣợng tài nguyên là khan hiếm, hạn chế. Nhƣ vậy đặc trƣng công việc đối với vấn đề tài nguyên đó là lƣợng thời gian hoàn thành công việc, yêu cầu phân bổ tài nguyên cho công việc. Các công việc có thể đƣợc thực hiện theo một số phƣơng pháp khác nhau nhƣng có điểm chung đó là đƣợc xác định bởi một quy tắc ràng buộc, các công việc đƣợc thực hiện theo dây chuyền, một số công việc chỉ đƣợc thực hiện sau khi đã thực hiện xong một số công việc khác. Một số ví dụ về bài toán lập lịch: a.
Bài toán lập lịch cho 2 máy: Xét mỗi một chi tiết phải đƣợc lần lƣợt gia công trên 2 máy A, B. Thời gian gia công chi tiết trên máy A là trên máy B là (i=1,2,. Hãy tìm lịch trình tự gia công) các chi tiết trên hai máy sao cho việc hoàn thành gia công tất cả các chi tiết là sớm nhất. Thuật toán Johnson: Chia các chi tiết thành 2 nhóm: nhóm gồm các chi tiết thoả mãn < , tức là và nhóm gồm các chi tiết thoả mãn tức là.
Các chi tiết thoả mãn xếp vào nhóm nào cũng đƣợc. Sắp xếp các chi tiết trong theo chiều tăng của các LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 và sắp xếp các chi tiết trong theo chiều giảm của các nối vào đuôi , dãy thu đƣợc đọc từ trái sang phải) sẽ là lịch gia công. Bài toán lập lịch cho 3 máy: Xét bài toán gia công N chi tiết trên 3 máy theo thứ tự A,B,C với bảng thời gian (i=1,2,.N) thoả mãn: hoặc Thuật toán: Lịch gia công tối ƣu trên 3 máy sẽ trùng với lịch gia công tối ƣu trên 2 máy: máy thứ nhất với thời gian và máy thứ hai với thời gian. Thuật toán More Có n ôtô đƣa vào xƣởng sửa chữa đƣợc đánh số thứ tự 1,2.
Ôtô phải sửa chữa trong thời gian và thời điểm phải bàn giao là. Mỗi thời điểm xƣởng chỉ sửa chữa một cái, xƣởng sửa chữa không ngừng và thời điểm bắt đầu sửa chữa là 0. Hãy đƣa ra một thứ tự sửa chữa sao cho số lƣợng ôtô đúng hạn là lớn nhất. Sắp xếp theo thứ tự tăng dần của thời điểm bàn giao.
Duyệt từ đầu cho đến khi gặp ôtô quá hạn đầu tiên (Giả sử là ôtô thứ k). Tìm từ đầu cho đến ôtô thứ k, ôtô nào có lớn nhất (Giả sử đó là ôtô thứ m). Nếu ôtô này đã đƣợc chuyển một lần rồi thì dừng chƣơng trình, còn nếu không thì ta chuyển ôtô này xuống cuối. Rồi trở lại bƣớc 2.
Bài toán lập lịch là dạng bài toán quan trọng đƣợc nghiên cứu trong các môi trƣờng tính toán. Quá trình lập lịch là quá trình quyết định sẽ thực thi công việc tại một nguồn tài nguyên cụ thể nào và vào thời điểm nào là thích hợp nhất bởi công việc đó sẽ ảnh hƣởng rất lớn đến hiệu năng hoạt động của hệ thống. Nhu cầu cần sử dụng bài toán lập lịch là rất lớn trên thực tế. Hầu nhƣ mọi lĩnh vực liên quan đến quản lý, điều hành đều phải sử dụng đến bài toán lập lịch.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 Hiện nay có nhiều phƣơng pháp nghiên cứu, phát triển để giải quyết bài toán này. Những kỹ thuật đó bao gồm: - Các tiếp cận trí tuệ nhân tạo nhƣ: Hệ thống cơ sở tri thức (knowledgebased systems), bài toán thoả mãn ràng buộc, hệ chuyên gia, mạng Neural, tìm kiếm, tìm kiếm chọn lọc, thuật toán Heuristic, thuật toán tô màu đồ thị, thuật toán luồng… - Các tiếp cận dựa trên những nghiên cứu hoạt động: Lập trình tính toán, lập trình động, tìm kiếm nhánh và đƣờng biên, kỹ thuật mô phỏng, tìm kiếm Tabu search, phƣơng pháp nút cổ chai. Bài toán lập lịch có rất nhiều ứng dụng trong thực tế nhƣ: Bài toán lập lịch xếp thời khóa biểu cho các trƣờng đại học, cao đẳng, các trƣờng phổ thông…, lập lịch phân công công tác cho một công ty, doanh nghiệp, lập lịch cho hệ thống tính toán lƣới trắc địa, lập lịch cho bộ xử lý CPU… 1. Bài toán xếp thời khóa biểu ở trƣờng phổ thông 1.
Giới thiệu bài toán xếp thời khóa biểu Trong một cơ quan, một tổ chức, một trƣờng học công việc quản lý và sắp xếp công việc cho các cá nhân, các nhóm trong từng giai đoạn và thời điểm cũng nhƣ địa điểm một cách hợp lý và khoa học là hết sức cần thiết và cấp bách. Công việc đó dựa trên các bài toán lập lịch và việc tìm lời giải tối ƣu cho các bài toán này vẫn là hƣớng nghiên cứu mà rất nhiều cá nhân, tổ chức hƣớng tới và cũng có nhiều công trình nghiên cứu về vấn đề này. Trong phạm vi một trƣờng học cũng có nhiều bài toán lập lịch, trong đó tiêu biểu là bài toán xếp thời khóa biểu. Bài toán này nhằm sắp xếp lịch hoạt động giảng dạy và học tập của giáo viên và học sinh.
Sau đây chúng ta đi tìm hiểu bài toán lập thời khóa biểu chính khóa, theo tuần, theo học kỳ, theo năm học của trƣờng Phổ thông trung học: - Bƣớc 1: Lập kế hoạch đào tạo (dựa vào khung chƣơng trình đào tạo của Nhà trƣờng theo các qui định của Ngành giáo dục). LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 - Bƣớc 2: Lập kế hoạch đào tạo theo tuần, theo học kỳ. - Bƣớc 3: Xây dựng bảng phân công giáo viên. - Bƣớc 4: Xây dựng bảng phân công từng lớp, từng khối.
- Bƣớc 5: Xây dựng thời khóa biểu. - Bƣớc 6: Hoàn chỉnh thời khóa biểu tổng thể cho giáo viên, lớp học. Bài toán xếp thời khóa biểu trong các nhà trƣờng là bài toán cần phải thỏa mãn những ràng buộc hết sức phức tạp và nhiều khi là mâu thuẫn của các đối tƣợng. Việc đƣa ra một bảng thời khóa biểu hợp lý không những làm mất nhiều thời gian và công sức của ngƣời lập lịch mà đôi khi còn gây ra mâu thuẫn nhƣ thỏa mãn nhu cầu của ngƣời hay nhóm ngƣời này lại phạm vào nhu cầu của ngƣời hay nhóm ngƣời khác.
Vấn đề xây dựng thời khóa biểu tự động hoặc bán tự động cho các loại công việc khác nhau bao gồm cả các hoạt động dạy và học trong một trƣờng học là một vấn đề cấp thiết đã thu hút nhiều sự chú ý trong cả hai lĩnh vực nghiên cứu và ứng dụng. Tuy nhiên kết quả nghiên cứu đạt đƣợc trong lĩnh vực này vẫn chƣa đƣợc ứng dụng rộng rãi bởi các nguyên nhân sau: - Về mặt học thuật, bài toán xếp thời khóa biểu tự động là một bài toán có độ phức tạp giải thuật rất cao. Chƣa có giải thuật xếp thời khóa biểu một cách tổng quát. - Khi áp dụng vào các trƣờng học, mỗi trƣờng có mô hình đào tạo, đặc thù khác nhau dẫn đến các mối quan hệ ràng buộc khác nhau.
Việc đƣa ra một mô hình biểu diễn đặc trƣng tổng quát cho tất cả các mối quan hệ ràng buộc này là rất khó.