CHƯƠNG 1: TỔNG QUAN BÀI TOÁN LẬP LỊCH Trang 8 Output: Cho ra bảng kết quả lập lịch. Thông tin cho biết: GVPB, ủy viên được phân công cho hội đồng nào. Thời gian địa điểm mà hội đồng báo cáo. Đề tài tương ứng từng hội đồng.
GV biết được thời gian, địa điểm của các đề tài mà mình được phân công.4 Các bước cơ bản giải quyết bài toán Để thực hiện được mục tiêu của bài toán, hệ thống cần xác định các chức năng chính: Nhập liệu: Nhập danh sách các đề tài, GVHD, GVPB, ủy viên, các phòng, danh sách sinh viên và danh sách bảng đăng kí đề tài. Thực hiện thao tác sắp xếp lập lịch tự động. Sau bước này sẽ có kết quả lập lịch do chương trình tự động tạo ra thỏa mãn các ràng buộc cứng và ràng buộc mềm. Có thể hiệu chỉnh kết quả đạt được để cho ra kết quả tốt nhất như mong muốn.
CHƯƠNG 1: TỔNG QUAN BÀI TOÁN LẬP LỊCH Trang 9 1.5 Phân tích yêu cầu Lược đồ usecase: Hình 1-1: Lược đồ usecase tổng quát Mô tả chức năng: Chức năng đăng nhập: Hệ thống cần quản lý người vào sử dụng hệ thống. Hệ thống chỉ cho phép người quản lý vào tránh trường hợp người lạ đăng nhập làm hư hao dữ liệu. Nhóm chức năng quản lý hệ thống: Đổi mật khẩu: Cho phép người dùng đổi mật khẩu truy cập hệ thống. Đăng xuất: Cho phép người dùng đang xuất ra khỏi chương trình.
Quản lý sinh viên, quản lý giảng viên, quản lý đề tài, quản lý đăng ký đề tài, quản lý phân công phản biện gồm các chức năng chính thêm, sửa, xóa. Đối với chức năng xếp lịch khi tiến hành xếp lịch sẽ thực hiện chạy quá trình xếp lịch. Sau đó ta có thể xuất kết quả ra thành file có định dạng như PDF hay Excel bằng việc sử dụng chức năng in kết quả. Ngoài ra còn có các chức năng như hiệu chỉnh kết quả, in kết quả theo phòng.
Người dùng cũng có thể thêm dữ liệu bằng cách nhập từ file excel. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Trang 10 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT 2.1 Công nghệ sử dụng 2.5 là một thành phần có thể được cài thêm hoặc đã có sẵn trong các hệ điều hành Windows. Nó cung cấp những giải pháp đã được code sẵn cho những yêu cầu thông thường của chương trình, quản lý thực thi các chương trình viết trên framework, người dùng cần phải cài đặt framework để có thể chạy chương trình .5 do Microsoft đưa ra và được sử dụng trong hầu hết các ứng dụng viết trên nền Windows. Những giải pháp được code sẵn hình thành nên một thư viện lớp của framework, được sử dụng trong nhiều lĩnh vực của lập trình như: giao diện người dùng, truy cập dữ liệu, kết nối cơ sở dữ liệu, mã hóa, phát triển những ứng dụng web, các giải thuật số học và giao tiếp trên mạng.
Thư viện lớp của framework được lập trình viên sử dụng, kết hợp với code của chính mình để tạo nên các ứng dụng.2 Công nghệ LINQ Để giảm gánh nặng thao tác trên nhiều ngôn ngữ khác nhau và cải thiện năng suất lập trình, Microsoft đã phát triển giải pháp tích hợp dữ liệu cho .NET Framework có tên gọi là LINQ (Language Integrated Query) tạm dịch là ngôn ngữ tích hợp truy vấn, đây là thư viện mở rộng cho các ngôn ngữ lập trình C# và Visual Basic. [3] Điểm mạnh của LINQ là có thể viết truy vấn cho nhiều đối tượng dữ liệu. Từ cơ sở dữ liệu, XML, Data Object, thậm chí là truy vấn cho một biến mảng đã tạo ra trước đó. Vì thế ta có các khái niệm như LinQ to SQL, LinQ to XML.
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Trang 11 Các thành phần chính của LINQ: [4] Hình 2-1 Lược đồ tổng quan linq [5] LinQ to Object: Sử dụng LinQ đối với các đối tượng Collection mà đã được thực thi giao diện IEnumerable hoặc IEnumerable<T> tức những collection có thể “liệt kê” được. Đây là trường hợp sử dụng đơn giản nhất của LINQ khi làm việc với dữ liệu. LinQ to SQL: Là một phiên bản hiện thực hóa của ORM (object relation mapping) có bên trong .5, nó cho phép bạn mô hình hóa một cơ sở dữ liệu dùng các lớp. Sau đó ta có thể truy vấn cơ sở dữ liệu dùng LinQ, cũng như cập nhật, thêm, sửa, xóa dữ liệu từ đó một cách dễ dàng.
LinQ to SQL hỗ trợ đầy đủ transaction, view và các stored procedure (SP). Nó cũng cung cấp một cách dễ dàng để thêm khả năng kiểm tra tính hợp lệ của dữ liệu và các quy tắc trong mô hình dữ liệu của bạn. LinQ to XML: Sử dụng LinQ với mục đích truy vấn dữ liệu được lưu trữ ở dạng file XML. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Trang 12 LinQ to Datasets: Cho phép người lập trình sử dụng DataSets như một nguồn dữ liệu bình thường bằng các cú pháp truy vấn căn bản của LinQ.
LinQ to Entities: Cho phép chúng ta có thể truy vấn các thực thể bên trong Entitiy Framework. LinQ với ADO.NET: LinQ là tập mở rộng cho phép viết các câu truy vấn ngay trong các ngôn ngữ lập trình. Nó cho phép bạn làm việc với các kiểu tập hợp dữ liệu như XML, array và các cơ sở dữ liệu.NET là công nghệ cho phép các ứng dụng có thể kết nối và làm việc với các loại cơ sở dữ liệu khác nhau (truy vấn, cập nhật, thêm, sửa, xóa, gọi thủ tục). Bản chất LinQ không phải là một công nghệ được tạo ra để thay thế ADO.NET, ta có thể làm việc với LinQ mà không cần kết nối đến cơ sở dữ liệu.
Tuy nhiên, LinQ to SQL là phần mở rộng của LinQ, cho phép ta có thể làm việc được với cơ sở dữ liệu SQL Server, trong trường hợp này ta có thể bỏ qua câu lệnh ADO.NET mà chỉ quan tâm tới cú pháp mà LinQ cung cấp.3 Giới thiệu về DEVExpress DevExpress là một Framework được viết cho nền tảng. Nó cung cấp các control và công nghệ để phục vụ cho việc thiết kế phát triển phần mềm, website. Nó giúp thiết kế form trở nên đẹp hơn và giúp công việc lập trình trở nên đơn giản hơn. Các thành phần của DevExpress gồm: [6] WinForms Controls: Cung cấp các control cho WinForms.NET Controls: Cung cấp các control cho WebForms.
WPT Controls: Cung cấp các control cho WPT. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Trang 13 Silverlight Control: Cung cấp các control cho Silverlight. XtraCharts Control: Cung cấp các loại biểu đồ. XtraReports: Cung cấp các control tạo báo cáo.
XPO: Cung cấp môi trường làm việc với database. XAF: Một công nghệ mới giúp việc phát triển phần mềm một cách nhanh chóng. Trải qua hàng loạt phiên bản, DevExpress đã từng bước nâng cấp, hoàn thiện và thêm mới rất nhiều chức năng. Với các phiên bản hiện nay, DevExpress đã cung cấp những công cụ, môi trường để biến những ý tưởng thành hiện thực một cách nhanh chóng, dễ dàng.
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Trang 14 2.2 Phương pháp sử dụng 2.1 Giới thiệu giải thuật di truyền (GA) Giải thuật di truyền (GAs: Genetic Algorithms) hình thành dựa trên ý tưởng mô phỏng quá trình tiến hóa của sinh vật trong tự nhiên vào các bài toán tối ưu để tìm ra lời giải tương đối tối ưu. Tính tối ưu được thể hiện ở chỗ thế hệ sau bao giờ cũng phát triển hơn, hoàn thiện hơn thế hệ trước. Quá trình tiến hóa trong tự nhiên được duy trì thông qua quá trình sinh sản và chọn lọc tự nhiên, trong quá trình tiến hóa này, các thế hệ mới sinh ra sẽ dần bổ xung thay thế cho thế hệ cũ, các cá thể thích ứng với môi trường tốt hơn sẽ tồn tại và các cá thể kém thích nghi sẽ dần bị đào thải. [7] Xuất phát từ một tập các giải pháp ban đầu, GA sẽ tiến hành xây dựng nên lớp giải pháp mới tốt hơn từ các giải pháp ban đầu thông qua quá trình chọn lọc, lai ghép, đột biến từ tập giải pháp ban đầu.
Quần thể giải pháp sẽ trải qua quá trình tiến hóa và ở mỗi giai đoạn sẽ bổ xung các giải pháp tương đối tốt, đồng thời loại bỏ các giải pháp chưa tốt để dần tiến tới giải pháp tối ưu nhất. Trong giải thuật di truyền ta có thể xem các cá thể trong một quần thể là các chuỗi hay các nhiễm sắc thể. Các nhiễm sắc thể được tạo thành từ các đơn vị là các gen biễu diễn trong một chuỗi tuyến tính. Mỗi cá thể sẽ biểu diễn một lời giải của bài toán đang giải; một tiến trình tiến hóa được thực hiện trên một quần thể nhiễm sắc thể tương ứng với quá trình tìm kiếm lời giải trong không gian lời giải.[8] Trong lĩnh vực lập lịch, giải thuật di truyền đã được sử dụng rất nhiều cho các bài toán lập lịch.
Về cơ bản, bài toán lập lịch được coi là việc gắn các mốc thời gian thực hiện cho các công việc sao cho phù hợp với khả năng về tài nguyên. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Trang 15 2.2 Một số phương pháp khác Phương pháp leo đồi Phương pháp leo đồi sử dụng kỹ thuật lặp và áp dụng cho một điểm duy nhất (điểm tồn tại trong không gian tìm kiếm). Với mỗi bước lặp, một điểm mới được chọn từ các điểm lân cận của điểm hiện tại. Vì thế leo đồi được gọi là phương pháp tìm kiếm lân cận hay tìm kiếm cục bộ.
Nếu điểm mới cho giá trị (của hàm mục tiêu) tốt hơn, điểm mới sẽ trở thành điểm hiện tại. Ngược lại, một điểm lân cận khác sẽ được chọn và thử. Quá trình này sẽ dừng nếu không thêm được lời giải tốt hơn lời giải hiện hành. [8] Từ đó ta thấy rõ phương pháp leo đồi chỉ cung cấp các giá trị tối ưu cục bộ và những giá trị này phụ thuộc vào điểm bắt đầu.
Do vậy, để tăng cơ hội thành công, phương pháp leo đồi thường phải được thực hiện nhiều lần; mỗi lần với một điểm bất đầu khác nhau. [8] Phương pháp mô phỏng luyện thép Kỹ thuật mô phỏng luyện thép là một kỹ thuật khắc phục những nhược điểm của phương pháp leo đồi: Lời giải không phải phụ thuộc nhiều vào điểm bất đầu nữa và thường là gần với điểm tối ưu hơn. Đạt được điều này là nhờ đưa vào xác suất nhận p. Xác suất p là hàm theo giá trị của hàm mục tiêu đối với điểm hiện tại và điểm mới, và một tham số điều khiển bổ sung, tham số “nhiệt độ” T.
Nói chung nhiệt độ T càng thấp thì cơ hội nhận điểm mới càng thấp.