Chương I: GIỚI THIEU DE TÀI 1. ĐẶT VAN DE Ngành giáo dục đóng vai trò rât quan trọng trong việc tạo ra nguôn nhân lực chât lượng cao phục vụ cho nên kinh tê cũng như chính trị xã hội của đât nước. Hiện nay, ngành giáo Việt Nam cân có nhiêu thay đôi đê đào tạo ra nguôn nhân lực đôi dao, chất lượng cao góp phân xây dựng đất nước hùng mạnh. Ngay từ năm 1999, nhận thấy nhu cau nguồn nhân lực chất lượng cao là yếu tố sông còn của việc phát triển Tập đoàn và ngành công nghiệp CNTT, FPT đã phối hợp với tập đoàn đào tạo CNTT hàng dau thế giới Aptech An độ triển khai hệ thông các trung tâm đào tạo Lập trình viên Quốc tế Aptech và Mỹ thuật đa phương tiện Arena tại Việt nam.
Ngày 08/09/2006, Chính phủ đã có Quyết định số 208/2006/QD-TTg cho phép chính thức thành lập Trường Dai hoc Tư thục FPT. Trường Đại học FPT xây dựng mô hình của một trường Đại học thế hệ mới, có triết lý giáo dục hiện đại, gan liền đào tạo với thực tiễn cuộc sống và nhu cầu nhân lực của đất nước, gop phan đưa ngành CNTT Việt nam lên ngang tầm các nước tiên tiễn trên thé giới. Sự khác biệt của Trường Đại học FPT so với các trường đại học khác là đào tạo kỹ sư công nghiệp, nghĩa là đào tạo theo hình thức liên kết chặt chẽ với các doanh nghiệp CNTT, gan đào tạo với thực tiễn, với nghiên cứu - triển khai và các công nghệ hiện đại nhất. Triết lý và phương pháp giáo dục hiện đại; Đào tạo con người toàn diện, hài hòa; Chương trình luôn được cập nhật và tuân thủ các chuẩn công nghệ quốc tế; Đặc biệt chú trọng kỹ năng ngoại ngữ; Tăng cường đào tạo quy trình t6 chức sản xuất, kỹ năng làm việc theo nhóm và các kỹ năng cá nhân khác là những điểm sẽ đảm bảo cho sinh viên tốt nghiệp có những cơ hội việc làm tốt nhất tại tập đoàn FPT va các doanh nghiệp hang đầu khác.
Ngày 13/07/2010, trường cao đăng thực hành FPT (FPT Polytechnic), trực thuộc đại học FPT, được thành lập với sứ mệnh cung cấp dịch vụ đảo tạo tốt trên các tiêu chí: phù hợp với năng lực học tập của sinh viên; đáp ứng nhu câu lớn của doanh nghiệp; và cung cấp dịch vụ đào tạo chuẩn mực dựa trên các chuẩn đã được công nhận. Với nhận định Việt Nam có hàng trăm nghìn doanh nghiệp, các chuyên ngành đào tạo của FPT Polytechnic đều nhắm tới nhu cầu xã hội lớn như: mỗi doanh nghiệp đều cần có nhân viên kế toán, nhân viên tiếp thị và bán hàng: các doanh nghiệp đều cần có website quảng bá sản phẩm và giao dịch do đó đều cần một nhân viên thiết kế, quản trị website; các doanh nghiệp có hệ thống máy tính đều cần nhân viên lập trình để xây dựng các ứng dụng hữu ích và đảm bảo hệ thống được vận hành hiệu quả. Chương trình đào tạo của FPT Polytechnic tuân theo chuẩn khung chương trình cua BTEC, Vuong quéc Anh. Sach giáo trình, tài liệu hoc tập được chuyển ngữ sang Tiếng Việt từ các bộ sách uy tín của các NXB lớn trên thế giới như Pearson, Cengage, Mc-Graw Hills,.
Học liệu được các cán bộ có uy tín cua Trường Đại học FPT thiết kế, biên tập và chuyển tải trên việc áp dụng hệ thống công nghệ thông tin hiện đại. Hiện nay, hệ thống FPT Polytechnic đã được thành lập tại 06 thành phố lớn trên cả nước như: e FPT Polytechnic Hà Nội e FPT Polytechnic Da Nang e FPT Polytechnic TP. Hồ Chí Minh e FPT Polytechnic Quảng Ninh e FPT Polytechnic Thanh Hóa e FPT Polytechnic Dak Lak Với sự thành công của hệ thống FPT Polytechnic cùng với đội ngũ giảng viên giàu kinh nghiệm và nhiệt tình, số lượng sinh viên ngày càng tăng mạnh, trong tương lai FPT Polytechnic sẽ mở thêm nhiều cơ sở khác tại các tỉnh thành, đó là chiến lược phát triển của hệ thống FPT Polytechnic. Là thành viên trong hệ thống FPT Polytechnic, FPT Polytechnic TP.
Hồ Chí Minh cũng đã phát triển rất nhanh, chiếm tỷ trọng tăng trưởng cao nhất hệ thông năm 2012. Với số lượng sinh viên (trên 4000SV), lớp học, giảng viên ngày cảng tăng mạnh, Phòng Dao Tạo gặp khó khăn trong vấn dé sắp xếp lịch biểu học va giảng dạy cho sinh viên cũng như giảng viên. Hiện tại có 2 nhân viên làm lịch biểu cho mỗi học kỳ và trung bình khoảng mất từ 15 đến 20 ngày. Nguyên nhân chính là hiện tại Phòng Đào Tạo dùng cách sắp xếp lịch đơn giản bằng phương pháp thủ công, sử dụng kinh nghiệm va dùng phần mém Excel dé nhập lịch biểu.
van dé này dang được Trường FPT Polytechnic TP. Hồ Chí Minh quan tâm. Từ đó việc xây dựng một phần mém sắp xếp lịch biéu cho Trường FPT Polytechnic TP. Hỗ Chí Minh là việc cần thiết cho trường hiện nay.
Với kinh nghiệm về lập trình và các kỹ thuật điều độ được học trong lớp cao học ISE — 2012, tôi chọn dé tai: “UNG DỤNG CÁC GIẢI THUẬT TRONG DIEU ĐỘ TIME TABLING DE XÂY DUNG LICH BIEU GIANG DẠY, ÁP DUNG CHO TRƯỜNG FPT POLYTECHNIC TP.HCM” làm luận văn thạc sĩ. NỘI DUNG e Tìm hiểu kỹ thuật điều độ trong sản xuất và dịch vụ, kỹ thuật điều độ lịch biểu, từ đó chọn thuật toán sắp xếp lịch biểu đa mục tiêu hợp lý cho mục tiêu của đề tài. e Tim hiểu quy trình sắp xếp lịch biểu tại Phòng Đào Tạo - Trường FPT Polytechnic TP. Hỗ Chí Minh.
e Thu thập thông tin về lớp học, môn học, giảng viên cơ hữu, giảng viên thỉnh giảng, các ràng buộc cứng và mêm. -3- e Tổng hop, phân tích và thiết kế hệ thống thông tin (Thiết kế giao diện, cơ sở dữ liệu, xây dựng phân mêm, tài liệu hướng dân.) e Đánh giá kết quả phần mém va đưa kiến nghị phát triển phần mềm. MỤC TIỂU Xây dựng phan mềm sắp xếp lịch biểu giảng dạy tại Trường FPT Polytechnic TP. Hỗ Chí Minh với 03 chỉ số đánh giá: e Giảm thời gian lên lịch.
e Tối ưu việc sử dụng phòng học. e Tối ưu việc sắp xếp giảng viên. GIỚI HAN VA PHAM VI DE TÀI Phần mềm sắp xếp lịch biểu giảng dạy tự động cho Trường FPT Polytechnic với 2 chức năng chính: e Sắp xếp phòng học cho các lớp. e Sắp xếp giảng viên theo môn hoc cho các lớp Do hạn chế về thời gian và nhằm đảm bao tính hiệu quả của dé tai nên nội dung đề tài chỉ tập trung vào nghiên cứu và xây dựng phần mềm sắp xếp lịch biểu với hai chức năng chính trên, trong tương lai sẽ phát triển thêm nhiều tính năng nữa.
Dữ liệu mẫu sử dụng của học kỳ Spring 2014 và Summer 2014 (Phụ lục đính kèm) Chương II: CƠ SỞ LÝ THUYET VÀ CÁC NGHIÊN CỨU LIÊN QUAN 2. DIEU DO TIME TABLING 2. Giới thiệu kỹ thuật diéu độ Điều độ là một quá trình ra quyết định đóng vai trò rất quan trọng trong hầu hết các hoạt động, các ngành công nghiệp sản xuất và dịch vụ. Chức năng điều độ trong một công ty là sử dụng các kỹ thuật toán học hay một SỐ phương pháp định lượng khác để phân phối hop lý nguồn tài nguyên có hạn phục vụ công việc.
Sự phân phối nguồn tài nguyên thích hợp sẽ cho phép công ty dat được mục tiêu tối ưu mong muốn như: cực tiểu thời gian hoàn thành, cực tiểu các công việc trễ hạn. Ví dụ: dự án lắp đặt hệ thống máy tính, chế tạo động cơ, dây chuyển lắp ráp ôtô, hệ thong đặt chỗ thuê xe trước, điều độ y tá trong bệnh viện. đều cần đến kỹ thuật điêu độ nhâm đạt được mục tiêu tôi ưu mong muôn. Chức năng điều độ trong một hệ thống sản xuất hay một tô chức dịch vụ phải tương tác với nhiều chức năng khác.
Các sư tương tác này thường thông qua mạng máy tính, nhưng trong nhiều tình huống, sự tương tác giữa điều độ và các chức năng ra quyết định khác xảy ra trong các budi họp hay thư báo. Mô hình tong quát của bài toán Time Tabling Bài toán Time tabling có hai giai đoạn để giải quyết là giai đoạn thỏa mãn ràng buộc cứng (CSP) và tối ưu ràng buộc mềm (COP). e Thỏa mãn ràng buộc cứng e Tối ưu hóa ràng buộc mềm e Bài toán thóa man ràng buộc (Contraint Satisfaction Prolem - CSP) Bài toán CSP được định nghĩa bao gồm: Biến V: là tập hữu hạn các biến Rang buộc: giới hạn hành động gan tri cho biến.,wk) là một bộ các biến từ tập V Qj là các ràng buộc Miễn trị D Lời giải của bài toán là một hàm f (hàm gan tri) quy định cách gan tri cho toàn bộ các biên sao cho: - - Với mỗi biến v e V,f(v) e Dy - - Với mỗi ràng buộc ((W1,., Í(wk)) € Q Để giải bài toán thỏa mãn ràng buộc ta có rất nhiều thật toán tìm kiếm, ở đây ta dùng các giải thuật Local Search. e Bài toán tối ưu tổ hợp (Combinatorial Optimization Problem - COP) Bài toán COP được định nghĩa bao gồm bộ 03 tập (S, F, f), trong đó: - §: tập hữu hạn các lời giải.
- F: tập lời giải khả thi. - f: hàm mục tiêu đánh giá chất lượng lời giải. Giải quyêt bài toán tôi ưu tô hợp là tìm một lời giải tôi ưu toàn cục x* eFE sao cho f(x*) <= f(x) Vx eE. Thuật giải sử dụng trong bước này thường dùng Tabu Search hoặc di truyền (Genetic Algorithm).
Mô hình tong quát để giải bài toán Time tabling với hai giai đoạn thỏa man ràng buộc cứng (CSP) và tối ưu ràng buộc mềm (COP) có thé được giải quyết tối ưu bằng các thuật toán tìm kiếm trình bày bên dưới. Các giải thuật lập lịch biểu (Time tabling) Có rất nhiều giải thuật chuyên về lập lịch biểu giảng day đã được nghiên cứu và phát triển trong nhiều thập ký qua, điển hình là các giải thuật: Tìm kiếm cục bộ (Local Search) dựa vào một ý tưởng tổng quát và đơn giản. Gọi P là một bài toán tối ưu tô hợp cần giải, và s là lời giải hiện hành giả sử là một lời giải kha thi của P, và có ham chi phi f(s). Miền lân cận N(s) được định nghĩa cho s, là tập những lời giải láng giéng khả thi s’ của s sao cho từ s ta có thể đạt tới s’ nhờ vào một bước chuyển m.
Bước chuyền có tác dụng biến đổi s thành ra một lời giải láng giéng. Thao tác biến đổi này được lặp cho đến khi hội tụ về một lời giải tốt. Lời giải này là lời giải cận tối ưu, mà trong một số bài toán thực tế, không Lá “9° CÁ sai biệt øì nhiêu với lời giải tôi ưu.