Cải tiến xếp lịch tại trường cao đẳng nghề nhằm đáp ứng yêu cầu thời vụ luận văn thạc sĩ công nghệ thông tin

GIỚI THIỆU

Lý do chọn đề tài

Trong cuộc sống, chúng ta thường phải giải quyết các bài toán xếp lịch, chẳng hạn như xếp lịch chuyến bay, thi đấu thể thao, công việc hay thực hiện dự án Để giải quyết những bài toán này, cần tìm ra phương án xếp lịch tối ưu, đáp ứng tất cả các ràng buộc và khai thác hiệu quả nguồn tài nguyên sẵn có, nhằm giảm thiểu thời gian và chi phí thực hiện.

Bài toán xếp thời khóa biểu trong trường học, đặc biệt là ở các trường cao đẳng nghề, gặp nhiều ràng buộc phức tạp Những ràng buộc này liên quan đến các đối tượng tham gia như giảng viên, lớp học và sinh viên, cũng như tài nguyên phục vụ giảng dạy.

Bài toán xếp thời khóa biểu là một bài toán NP - đầy đủ, do đó việc tìm ra lời giải tối ưu có thể gặp khó khăn Mặc dù đã có nhiều giải thuật như giải thuật nhánh cận, giải thuật leo đồi, giải thuật luyện thép, giải thuật tô màu đồ thị và giải thuật xấp xỉ được đề xuất, nhưng những giải thuật này thường không mang tính tổng quát và chỉ hiệu quả với các trường học có quy mô nhỏ và ít ràng buộc về dữ liệu.

Tại các trường Cao đẳng nghề, việc chuyển sang cơ chế tự chủ đã khiến sinh viên thường xuyên tham gia thực tập tại doanh nghiệp, tạo ra thách thức trong việc xếp thời khóa biểu Đặc biệt, các trường có quy mô đào tạo lớn gặp khó khăn hơn do lịch học cần thay đổi theo thời vụ Hiện tại, trên thị trường vẫn chưa có phần mềm nào đáp ứng hiệu quả nhu cầu này.

Nghiên cứu các giải pháp xếp lịch là rất cần thiết để đáp ứng nhu cầu thời vụ tại các trường đào tạo nghề.

Mục tiêu, nội dung và phạm vi nghiên cứu

- Tìm hiểu quy trình xếp lịch trong trường Cao đẳng dạy nghề

- Tìm hiểu các giải thuật xếp lịch liên quan

- Đề xuất giải pháp xếp lịch đáp ứng nhu cầu thực tiễn

- Đánh giá giải pháp đề xuất

- Tìm hiểu quy trình xếp lịch trong trường Cao đẳng công nghệ Quốc tế LILAMA 2

- Thu thập thông tin để xây dựng cơ sở dữ liệu cho việc xếp lịch

- Tìm hiểu và đề xuất giải thuật cho bài toán xếp lịch tại trường Cao đẳng công nghệ Quốc tế LILAMA 2.

- Xây dựng ứng dụng để cải tiến việc xếp lịch theo yêu cầu.

- Tiến hành thử nghiệm và đánh giá kết quả.

Hỗ trợ quy trình xếp lịch trong trường Cao đẳng công nghệ Quốc tế

Trong các phần sau, để dễ dàng theo dõi, học viên sắp xếp báo cáo theo thứ tự trình bày lần lƣợt nhƣ sau

- Cơ sở lý thuyết (chương 2) gồm khái niệm về bài toán xếp lịch các phương pháp tiếp cận, và các nghiên cứu liên quan đến xếp thời khóa biểu,

Bài toán nghiên cứu trong chương 3 được mô tả chi tiết với các nội dung chính như hiện trạng xếp thời khóa biểu hiện tại của trường, quy trình thực hiện, và bài toán cần giải quyết Đồng thời, bài viết cũng nêu rõ hàm mục tiêu cần tối ưu trong bài toán này và đề xuất một mô hình hóa toán học phù hợp để đạt được hiệu quả tối ưu trong việc xếp lịch học.

Phương pháp đề xuất trong chương 4 bao gồm việc mô tả các đầu vào của bài toán, phân tích tính khả thi của nó, đưa ra giải pháp đề xuất, thu thập số liệu thực nghiệm và đánh giá kết quả đạt được.

CƠ SỞ LÝ THUYẾT

Bài toán xếp lịch

Bài toán lập lịch nhằm tìm ra một lịch trình đáp ứng các ràng buộc và mục tiêu nhất định Ràng buộc có thể liên quan đến thuộc tính của công việc, môi trường làm việc, hoặc khả năng của máy móc Các mục tiêu cần đạt được có thể bao gồm việc tối thiểu hóa thời gian hoàn thành công việc, đảm bảo công việc không hoàn thành quá sớm hoặc quá muộn, cũng như giảm thiểu thời gian trễ so với thời gian dự kiến Hơn nữa, có thể kết hợp nhiều mục tiêu khác nhau trong quá trình lập lịch.

Một số khái niệm liên quan về lập lịch

- Một lập lịch khả dĩ là một lập lịch sao cho

✔ Không có 2 khoảng thời gian nào trùng lặp nhau trên cùng một máy.

Không có 2 khoảng thời gian nào trùng lắp đƣợc cấp phát cho cùng

1 công việc Thỏa mãn một số đặc điểm của vấn đề đặc trƣng.

- Một lập lịch tối ƣu là một lập lịch cực tiểu một mục tiêu tối ƣu mong muốn.

Trong bối cảnh lập lịch tại trường học, bài toán xếp thời khóa biểu thu hút sự chú ý lớn từ các nhà nghiên cứu toàn cầu Đây là một dạng bài toán lập lịch với những hạn chế về nguồn lực, nhằm phân bổ một nhóm khóa học vào các khung thời gian, tối ưu hóa các mục tiêu mong muốn Hai bài toán kinh điển nổi bật trong lĩnh vực này là bài toán giáo viên đứng lớp và bài toán xếp thời gian khóa học đại học (UCTP).

Mô hình lớp học - giáo viên, được giới thiệu bởi Gotlieb (1963), yêu cầu một tập hợp giảng viên được chỉ định cho một nhóm lớp học trong một khoảng thời gian nhất định Mỗi lớp học bao gồm một nhóm học sinh theo cùng một chương trình, với giả định rằng tất cả các bài giảng có thời lượng giống nhau Asratian và de Werra (2002) đã nghiên cứu bài toán xếp thời biểu cho các tình huống thường gặp trong chương trình đào tạo của các trường đại học và phổ thông Thời gian biểu của trường đại học bao gồm cả lịch thi và lịch khóa học Xếp lịch kiểm tra, lần đầu tiên được công bố bởi Carter, Laporte và Lee (1996), được định nghĩa là việc phân bổ các kỳ kiểm tra vào các khoảng thời gian có sẵn mà không xảy ra xung đột Nói tóm lại, bài toán này liên quan đến việc phân bổ một tập hợp các bài kiểm tra vào một khung thời gian nhất định để đảm bảo không có học sinh nào phải tham gia hai kỳ thi cùng một lúc.

Các phương pháp tiếp cận

Sự tiến bộ trong công nghệ máy tính đã làm cho các bài toán và thuật toán lập lịch trở nên đa dạng và thực tiễn hơn, thu hút sự quan tâm của các nhà nghiên cứu trong việc giải quyết những thách thức phức tạp.

- Dựa theo các thuật toán và các phương pháp tiếp cận, chúng có thể được phân nhỏ thành một số loại nhƣ sau

Brucker [21, 22] đã xây dựng một bảng tổng kết độ khó của các bài toán lập lịch đã được nghiên cứu, cung cấp cái nhìn tổng quan về mức độ phức tạp của chúng Ngoài ra, các công trình nổi bật khác như nghiên cứu của Timkovsky về sự so sánh độ khó giữa các nhóm bài toán lập lịch cũng đáng được tham khảo Đặc biệt, bài toán lập lịch đầu tiên được chứng minh bởi Johnson [52] cùng với một số kết quả khác [39] cũng góp phần làm phong phú thêm hiểu biết về lĩnh vực này.

✔ Xác định cận biên P≠NP (maximal polynomial solvable) một số nghiên cứu quan tâm đến cận giới hạn trong các bài toán lập lịch [14, 15, 16, 24]

✔ Phương pháp tính chính xác quy hoạch nguyên [17], quy hoạch động, phương pháp tính cận và nhánh [19, 25],

Các giải thuật gần đúng cho quy hoạch phi tuyến tính được phát triển dựa trên phương pháp tính chính xác, nhằm cung cấp những giải pháp chất lượng cao Việc xây dựng chuỗi giải thuật gần đúng đảm bảo tính chắc chắn trong chất lượng của các giải pháp tìm thấy, góp phần nâng cao hiệu quả trong quá trình tối ưu hóa.

An approximation scheme is utilized in decision tree algorithms, including techniques such as branch and cut, branch and price, and search tree-based approaches These methods often incorporate recovering beam search and relaxation strategies to enhance solver configurations, effectively addressing linear programming problems.

✔ Các thuật toán tiến hóa [32, 36] thuật giải di truyền, tìm kiếm lân cận, meta-heuristic, thuật giải lai (hybrid),

Các nghiên cứu liên quan đến xếp thời biểu

UCTP, theo Carter và Laporte (1997), là một bài toán phân công đa chiều, trong đó sinh viên và giáo viên được chỉ định cho các khóa học, phần khóa học hoặc lớp học Các sự kiện, như các cuộc họp giữa học sinh và giáo viên, cũng được gán vào các lớp học và khung thời gian Bài toán này được coi là NP-hard và bao gồm cả các ràng buộc mềm và cứng Một số ràng buộc cứng được áp dụng trong tài liệu cũng đã được liệt kê.

− Đối với mỗi khung thời gian trong mỗi phòng, chỉ một nhóm sinh viên và một giáo sƣ có thể tham dự.

− Không cho phép nhiều hơn một khóa học cho mỗi khung thời gian trong mỗi phòng.

− Số lƣợng học viên tham gia khóa học phải nhỏ hơn hoặc bằng sức chứa của phòng.

− Căn phòng học phải đáp ứng các chức năng theo yêu cầu của khóa học (tham khảo Cacchiani, Caprara, Roberti, Toth, 2013 [23]; Lewis, Paechter, & McCollum, 2007 [37]).

− Khi đƣợc chỉ định, một khóa học phải đƣợc lên lịch trong khung thời gian được xác định trước (tham khảo Goh, Kendall, & Sabar, 2017 [33]; Lewis & Thompson, 2015 [38]).

− Để đáp ứng các yêu cầu về ƣu tiên, các khóa học phải đƣợc lên lịch diễn ra theo đúng thứ tự (tham khảo Babaei, Karimpour, & Hadidi,

Ngoài ra, có rất nhiều ràng buộc mềm đƣợc sử dụng trong các bài toán khác nhau, trong đó một số ràng buộc đƣợc đƣa ra nhƣ sau.

Các khóa học cần được tổ chức nhằm giảm thiểu thời gian trống cho cả giáo sư và sinh viên, điều này giúp tối ưu hóa quá trình học tập và giảng dạy (tham khảo Lewis & Thompson [38]; Van den Broek & Hurkens, 2012 [39]).

− Sinh viên không nên chỉ tham gia một khóa học trong một ngày (tham khảo Goh và cộng sự, 2017; Lewis & Thompson, 2015 [38]).

Một khóa học hiệu quả hơn khi được giảng dạy trong một phòng học cụ thể theo yêu cầu của giáo sư, như đã được nêu trong nghiên cứu của Lewis và các cộng sự năm 2007.

− Vào mỗi ngày, một khoảng thời gian nên đƣợc bỏ trống để học sinh nghỉ trƣa (tham khảo Lewis và cộng sự [37]).

Cacchiani và cộng sự (2013) đã nghiên cứu các vấn đề Xếp thời gian biểu khóa học (UCTP) thông qua hai phương pháp chính: Xếp thời gian biểu dựa trên Chương trình giảng dạy (Curriculum-based UTCP) và Xếp thời gian biểu dựa trên sự đăng ký của từng sinh viên (Post Enrollment-based UTCP).

Trong cách tiếp cận đầu tiên, sinh viên được phân loại thành các “nhóm” dựa trên chương trình học và khóa học cần thiết cho học kỳ tiếp theo Mỗi nhóm sẽ được thiết lập theo chương trình giảng dạy và các khóa học bắt buộc Vấn đề chính là tạo ra lịch bài giảng mà không xảy ra xung đột giữa các khóa học trong chương trình giảng dạy đã chỉ định (tham khảo Cacchiani và cộng sự, 2013).

Trong cách tiếp cận thứ hai, bảng thời gian khóa học được thiết lập dựa trên sự đăng ký của từng học sinh, nhằm đảm bảo tất cả học sinh có thể tham gia các khóa học mà họ đã đăng ký Nghiên cứu gần đây của Abdullah và Turabieh (2012) đã chỉ ra tầm quan trọng của việc lên lịch học dựa trên dữ liệu ghi danh cá nhân.

Cambazard, Hebrard, O'Sullivan, and Papadopoulos (2012), along with Ceschia, Di Gaspero, and Schaerf (2012), as well as Lewis et al (2007), have provided a comprehensive description of this type of problem utilized in Track Two of the Second International.

Tổng quan các phương pháp/giải pháp tiếp cận, các kỹ thuật áp dụng để giải quyết UCTP đƣợc trình bày bởi Babaei et al (2015) [10] nhƣ sau

Vận trù học (OR) là một lĩnh vực nghiên cứu quan trọng, áp dụng các phương pháp siêu mô phỏng để tối ưu hóa quy trình ra quyết định Các kỹ thuật đa tiêu chí và đa mục tiêu giúp phân tích và so sánh nhiều lựa chọn khác nhau một cách hiệu quả Đặc biệt, những phương pháp tiếp cận mới liên quan đến trí tuệ nhân tạo đang mở ra những cơ hội mới trong việc cải thiện hiệu suất và tính chính xác trong vận trù học.

Và cách tiếp cận hệ thống đa đại lý phân tán.

Phương pháp tô màu đồ thị, một kỹ thuật quan trọng trong vận trù học (OR), lần đầu tiên được giới thiệu bởi Welsh và Powell Kỹ thuật này giúp giải quyết các bài toán tối ưu hóa phức tạp bằng cách áp dụng các quy tắc tô màu để phân loại và tổ chức thông tin một cách hiệu quả.

Phương pháp tô màu cạnh trong đa đồ thị lưỡng phân đã được De Werra (1985) cải tiến, với các nút đại diện cho lớp học và giáo viên, trong khi các ràng buộc được xác định qua các cạnh Tuy nhiên, phương pháp này vẫn chưa giải quyết được các khóa học được chỉ định trước Để nâng cao hiệu quả về thời gian chạy và hiệu suất, Asham, Soliman và Ramadan (2011) đã áp dụng màu biểu đồ cùng với thuật toán di truyền (GA) như một giải pháp kết hợp.

Quy hoạch tuyến tính, một nhánh của vận trù học, được ứng dụng phổ biến trong các bài toán xếp lịch Mô hình do Bakir và Aksop (2008) phát triển sử dụng phương pháp này để tối ưu hóa thời gian biểu sắp xếp khóa học Mô hình 0-1 giúp giảm thiểu sự không hài lòng của cả sinh viên và giảng viên, đồng thời thực hiện các ràng buộc cần thiết nhằm tuân thủ các quy tắc đã đề ra.

Khi cần phân tích sâu về các tài liệu liên quan, Lewis (2008) là một nghiên cứu quan trọng, đã phân loại các thuật toán siêu mô phỏng cho việc xếp lịch thời biểu thành ba nhóm: (i) Thuật toán tối ưu hóa một giai đoạn, (ii) Thuật toán tối ưu hóa hai giai đoạn, và (iii) Các thuật toán cho phép thư giãn.

Alvarez-Valdes, Crespo, và Tamarit (2002) đã áp dụng phương pháp tìm kiếm tabu (TS - Tabu Search) để giải quyết bài toán UTCP qua ba giai đoạn, nhằm xây dựng thời khóa biểu phù hợp với hệ thống đại học Tây Ban Nha Phương pháp này cũng được Goh et al (2017) kết hợp với ủ mô phỏng (SA – Simulated Annealing) để nâng cao chất lượng của các giải pháp khả thi.

Việc tối ƣu hóa tổ hợp cũng đƣợc giải quyết bởi Tuga, Berretta và Mendes

Năm 2007, các tác giả đã giới thiệu một phương pháp kết hợp chuỗi lân cận Kempe trong thuật toán Simulated Annealing (SA) Phương pháp này tạo ra một giải pháp khả thi dựa trên đồ thị thông qua các kỹ thuật heuristic, với mục tiêu giảm thiểu vi phạm các ràng buộc mềm.

Khonggamnerd và Innet (2009) đã nghiên cứu một phương pháp tổng hợp mới nhằm giải quyết vấn đề sắp xếp thời khóa biểu cho các trường đại học Trong nghiên cứu này, họ áp dụng mô hình thuật toán di truyền để nâng cao hiệu quả của việc sắp xếp tự động thời khóa biểu, giúp tối ưu hóa quy trình này.

NGỮ CẢNH, ĐỘNG CƠ VÀ MÔ TẢ CỦABÀI TOÁN NGHIÊN CỨU

Hiện trạng

3.1.1 Giới thiệu về Trường Cao đẳng nghề LILAMA 2 a Lịch sử hình thành

− Tên nhà Trường Trường Cao Công nghệ Quốc tế LILAMA 2

− Thành lập năm 1986, trực thuộc Bộ Xây dựng

− Tên giao dịch nước ngoài LILAMA 2 International Technology College

− Trụ sở hoạt động Km32, Quốc lộ 51, Long Thành, Đồng Nai

− Email headoffice.lilama2.edu.vn – Website www.lilama2.edu.com b Chức năng

Trường Cao Công nghệ Quốc tế LILAMA 2 là một đơn vị sự nghiệp đào tạo có tư cách pháp nhân và con dấu riêng, được phép mở tài khoản tại kho bạc Trường hoạt động theo cơ chế tự chủ một phần, với kinh phí bao gồm ngân sách nhà nước cấp, thu học phí, thu từ hoạt động dịch vụ và các nguồn thu khác.

− Lập kế hoạch 5 năm, hàng năm và tổ chức thực hiện kế hoạch nhiệm vụ công tác của Trường.

Tổ chức nghiên cứu và xây dựng các chương trình, giáo trình cùng học liệu dạy nghề cho những ngành nghề được cấp phép đào tạo, đồng thời thực hiện các quy trình ban hành theo thẩm quyền của cơ quan chức năng.

− Xây dựng kế hoạch tuyển sinh hàng năm, tổ chức tuyển sinh học nghề theo kế hoạch.

Trường tổ chức các hoạt động dạy và học, thi, kiểm tra, và công nhận tốt nghiệp theo quy định của Bộ Lao động – Thương binh và Xã hội Đồng thời, trường cấp bằng tốt nghiệp và chứng chỉ kỹ năng nghề, bao gồm cả các chứng chỉ quốc tế thông qua các tổ chức giáo dục và đào tạo mà trường có liên kết và hợp tác.

Trường cần tuyển dụng, sử dụng, quản lý và đào tạo đội ngũ giáo viên, cán bộ, viên chức đảm bảo đủ số lượng và phù hợp với ngành nghề, quy mô cũng như trình độ đào tạo theo quy định pháp luật.

Tổ chức nghiên cứu khoa học và ứng dụng tiến bộ kỹ thuật, chuyển giao công nghệ, đồng thời thực hiện sản xuất, kinh doanh và cung cấp dịch vụ khoa học kỹ thuật theo quy định của pháp luật.

Hợp tác và liên doanh với các cơ sở giáo dục, tổ chức nghiên cứu khoa học, doanh nghiệp, và cá nhân trong và ngoài nước là cần thiết để nâng cao hiệu quả hoạt động dạy nghề, khoa học công nghệ, sản xuất, kinh doanh và dịch vụ.

Chúng tôi cung cấp dịch vụ tư vấn học nghề và việc làm miễn phí cho người học nghề, đồng thời phối hợp chặt chẽ với các cơ quan nhà nước, doanh nghiệp, tổ chức và gia đình để tổ chức các hoạt động dạy nghề hiệu quả.

Tổ chức cho người học nghề tham quan và thực tập tại doanh nghiệp là một hoạt động quan trọng, giúp họ có thêm kinh nghiệm thực tế Đồng thời, nhà trường cũng tạo điều kiện cho giáo viên, cán bộ, viên chức và người học nghề tham gia các hoạt động xã hội, nhằm nâng cao kỹ năng và tạo sự gắn kết với cộng đồng.

Thực hiện dân chủ và công khai trong các hoạt động dạy nghề, nghiên cứu khoa học, ứng dụng tiến bộ kỹ thuật, chuyển giao công nghệ, cùng với các hoạt động tài chính và khác tại nhà trường là rất quan trọng.

Quản lý tổ chức bộ máy và biên chế, thực hiện chế độ tiền lương, đãi ngộ, khen thưởng, kỷ luật cùng các chính sách khác đối với giáo viên, cán bộ và viên chức theo phân cấp hoặc thẩm quyền quản lý của Trường.

− Quản lý tài chính, tài sản đƣợc giao, quản lý các hoạt động có thu của nhà Trường theo quy định của pháp luật và Bộ Xây dựng.

Nhà trường cần thực hiện chế độ báo cáo định kỳ và báo cáo đột xuất theo quy định hoặc theo yêu cầu của Bộ Xây dựng và Bộ Lao động – Thương binh và Xã hội, nhằm cung cấp thông tin về tình hình tổ chức, hoạt động và các lĩnh vực công tác của nhà trường.

Trường Cao đẳng nghề công lập thực hiện các nhiệm vụ theo quy định của pháp luật và các nhiệm vụ khác được Bộ trưởng Bộ Xây dựng giao phó.

Trường Cao Đẳng Công Nghệ Quốc Tế Lilama 2 cung cấp hai hệ đào tạo chính, bao gồm chương trình trung cấp và chương trình đào tạo bậc cao đẳng.

Chương trình trung cấp có chỉ tiêu tuyển sinh hàng năm khoảng 500 và có hai dạng đào tạo

Học viên có bằng tốt nghiệp phổ thông trung học sẽ hoàn thành chương trình đào tạo trong thời gian hai năm, tức là cần hoàn tất các môn học trong 4 học kỳ.

Học viên tốt nghiệp trung học cơ sở với định hướng nghề nghiệp rõ ràng sẽ tham gia chương trình học kéo dài 3 năm, đồng thời thu thập kiến thức văn hóa ở cấp trung học phổ thông Mỗi ngày, học viên sẽ có một buổi học văn hóa và một buổi học theo chương trình hướng nghiệp Sau ba năm, học viên sẽ thi tốt nghiệp phổ thông quốc gia và thi tốt nghiệp trung cấp nghề, mang lại cho họ hai bằng cấp sau khi hoàn thành chương trình học.

Chương trình Cao đẳng có chỉ tiêu tuyển sinh hàng năm khoảng 600 và có hai dạng đào tạo

Quy trình xếp thời khóa biểu hiện tại của trường

Qua nghiên cứu và tìm hiểm quy trình xếp lịch tại trường LILAMA2 học viên đã tổng hợp ra các bước thực hiện như sau

Bước 1 Lập tiến độ đào tạo

Vào đầu năm học, phòng Đào tạo sẽ xây dựng kế hoạch đào tạo tổng thể cho toàn trường Thời gian học được chia thành hai kỳ, mỗi kỳ kéo dài 5 tháng Học kỳ 1 bắt đầu từ tháng 8 và kết thúc vào tháng 1 năm sau, trong khi học kỳ 2 diễn ra từ tháng 2 đến tháng 6.

Thời gian nghỉ Tết âm lịch và nghỉ hè tại trường cao đẳng nghề thường kéo dài 1 tháng mỗi kỳ Bảng tiến độ cho khóa học Cao đẳng K12, với 22 lớp, được trình bày từ tháng 8 đến tháng 1 năm sau Số tuần được đánh số từ T1 đến T24, trong đó có các thông tin về ngày đầu và ngày cuối tuần Mỗi lớp có trạng thái riêng được thể hiện bằng màu sắc: màu xanh dương (HKI) cho học kỳ 1, màu vàng (K) cho thi kết thúc môn, và màu nâu (HKII) cho học kỳ 2 Khung màu sắc ở cuối bảng giúp giải thích các trạng thái của tiến độ đào tạo.

Bảng tiến độ sau khi hoàn tất sẽ đƣợc ký duyệt và chuyển về các đơn vị trong trường để thực hiện.

- Mỗi kỳ học không được vượt quá 30 tuần lễ tương đương 6 tháng

- Mỗi lớp học chỉ được lên tiến độ tối đa 7 học kỳ (tương đương 3,5 năm)

- Mỗi lớp học phải thêm tối thiểu 3 học kỳ (tương đương 1,5 năm)

Hình 3.1 Kế hoạch tổng thể cho 1 năm học

Bước 2 Lên danh sách môn học (môn học lớp)

Các khoa sẽ lên danh sách môn học trong từng học kỳ cho từng lớp học.

Người phụ trách kế hoạch giảng dạy của khoa sẽ lựa chọn học kỳ và lớp học cần sắp lịch, sau đó chọn môn học từ dữ liệu của trường Trong quá trình này, các khoa chuyên môn sẽ xem xét các môn tiên quyết và điều kiện của từng khoa để lập danh sách môn học phù hợp cho từng lớp Yếu tố đầu tiên được xem xét là tình trạng giáo viên, tiếp theo là tình trạng phòng học và xưởng thực hành Tại các trường đào tạo nghề, mỗi giáo viên thường được giao một xưởng để giảng dạy và chịu trách nhiệm bảo trì, bảo dưỡng thiết bị trong xưởng đó.

Trong bảng danh sách môn học sẽ có các trường Mã môn học, tên môn học

"Số cột HS1" đại diện cho số cột điểm hệ số 1, trong khi "số cột HS2" là số cột điểm hệ số 2 Thuật ngữ "HS điểm TP" chỉ hệ số điểm thành phần, và "kiểm tra" thể hiện số lượng bài kiểm tra cho từng môn học cụ thể Chi tiết được trình bày trong Hình 3.2.

− Mỗi môn học chỉ được đưa vào danh sách môn học lớp (chương trình khung đào tạo) một lần duy nhất

− Số môn học/mô đun trong một học kỳ không được vượt quá 15 môn học/mô đun

Chỉ những môn học thuộc đúng chuyên ngành đào tạo mới được chấp nhận, trong khi các môn học không liên quan đến chuyên ngành hoặc từ các khoa chuyên môn khác sẽ không được công nhận, trừ những môn học chung hoặc môn học cơ sở.

B ƣớc 3 Lên kế hoạch chi tiết theo tuần.

Lên kế hoạch chi tiết theo tuần cho từng lớp trong bước này sẽ thực hiện nhƣ sau

Chọn học kỳ cần lên kế hoạch, sau đó chọn lớp cần lên kế hoạch.

Trong bảng kế hoạch tuần, các trường sẽ bao gồm mã môn, tên môn học, và giáo viên phụ trách Cán bộ xếp lịch sẽ lựa chọn giảng viên cho từng môn học Số tiết học trong tuần được xác định, với đặc trưng của các trường dạy nghề là mỗi buổi học kéo dài 4 tiết và chỉ tập trung vào một môn duy nhất.

Môn học “kỹ thuật điều khiển tự động hóa” do thầy Trương Thanh Inh giảng dạy, với tổng thời lượng 120 tiết, trong đó đã được lên kế hoạch 60 tiết Môn học này sẽ được giảng dạy từ tuần 1 đến tuần 8, với lịch học mỗi tuần một buổi.

Kế hoạch chi tiết hàng tuần sẽ được in từ phần mềm và gửi đến phòng Đào tạo để xem xét Nếu việc phân bổ giảng viên và thời gian đào tạo chưa hợp lý, phòng Đào tạo sẽ yêu cầu điều chỉnh kế hoạch.

- Số tiết được lên kế hoạch không được vượt số tiết của môn học.

- Mỗi môn học không được học quá 5 buổi 1 tuần

Hình 3.3 Kế hoạch đào tạo chi tiết theo tuần

Bước 4 Thực hiện chạy sắp lịch

Chạy sắp lịch sẽ đƣợc thực hiện nhƣ sau

Chọn học kỳ cần sắp lịch, sau đó chọn lớp cần sắp lịch.

Từ kết quả của các bước thực hiện trên sẽ cho ra một form mẫu xếp lịch gồm có

Mã môn học cần sắp lịch, tên môn học cần sắp lịch, số tiết, năm học, học kỳ.

Trong bước này người thực hiện chọn thứ, chọn phòng cho môn học cần sắp.sau đó chọn buổi học “buổi 1” là buổi sáng, “buổi 2” là buổi chiều.

Tiếp theo chọn “Tạo lịch” để thực hiện việc xếp lịch.

Trong quá trình xếp lịch, nếu có sự trùng giờ của giáo viên, phần mềm sẽ thông báo không thể xếp lịch do trùng giáo viên, yêu cầu người dùng chọn buổi khác Tương tự, nếu có trùng phòng xưởng, phần mềm cũng sẽ thông báo và yêu cầu chọn xưởng hoặc buổi khác để đảm bảo lịch trình không bị trùng lặp.

Sau khi hoàn thành bước này, sinh viên có thể dễ dàng tra cứu lịch học theo lớp, trong khi giáo viên có thể kiểm tra lịch dạy dựa trên tên của mình Để thực hiện việc tra cứu, người dùng có thể truy cập vào đường link: http://congthongtin.lilama2.edu.vn/.

- Mỗi phòng/xưởng chỉ được mố trí một môn học tại một thời điểm

- Số sinh viên không quá 35/phòng

- Mỗi giáo viên chỉ được giảng dạy 1 lớp tại một thời điểm

Hình 3.5 Thời khóa biểu của 1 lớp tra cứu ở cổng thông tin

Quá trình xếp thời khóa biểu toàn trường đã hoàn thiện kế hoạch giảng dạy cho cả năm, nhưng với đặc thù của các trường Cao đẳng nghề, việc chú trọng thực hành và tiếp cận thực tế là rất quan trọng Nhà trường ưu tiên phối hợp với ngành công nghiệp để tạo cơ hội thực tế cho sinh viên Điều này cũng cho phép điều chỉnh thời khóa biểu để đáp ứng nhu cầu thực tập từ doanh nghiệp Trong khi đó, các trường Đại học thường sắp xếp thời gian thực tập cho sinh viên vào những kỳ nghỉ, dẫn đến việc sinh viên chủ yếu tham gia vào các dự án mô phỏng thay vì trải nghiệm thực tế.

Với định hướng đối lập, sinh viên sẽ được trải nghiệm thực tế qua các dự án phù hợp với nhu cầu thời vụ của doanh nghiệp Điều này giúp sinh viên tự tin hơn khi ra trường, đồng thời tích lũy kinh nghiệm quý báu để tham gia ngay vào các hoạt động của doanh nghiệp mà không cần thời gian đào tạo lại.

Trên cơ sở đó, quá trình đi thực tập sản xuất đƣợc triển khai nhƣ sau

Bắt đầu từ năm học thứ 2, sinh viên sẽ học các môn chuyên ngành và thực tập tại các công ty hợp tác với nhà trường Lịch trình thực tập thường không được lên kế hoạch trước, mà sẽ được thông báo khi doanh nghiệp sẵn sàng tiếp nhận sinh viên.

- Nhà trường sẽ giao khoa làm quyết định đi thực tập, quyết định được chuyển về phòng Đào tạo để theo dõi tiến độ.

Sau khi sinh viên hoàn thành lịch thực tập tại doanh nghiệp, các khoa sẽ tổ chức các buổi học bù để bổ sung cho lịch học đã được lên kế hoạch từ đầu năm.

Lưu ý rằng lịch học sẽ ưu tiên sử dụng lịch của đầu kỳ, ngoài ra còn tăng thêm buổi học để cho kịp tiến độ trong học kỳ

Mô tả bài toán

Vấn đề chính không phải là tìm ra giải pháp để các lớp hoàn thành đúng tiến độ, mà là sắp xếp lịch học cho một số lớp vào thời khóa biểu đã được lên kế hoạch trước Điều này là cần thiết vì các lớp này đã tạm ngừng học để tham gia thực tập tại các doanh nghiệp.

Mục tiêu chính của bài toán là xác định một giải pháp mới cho phép chèn thêm các mô đun mà không làm ảnh hưởng đến lịch trình đã được sắp xếp, đồng thời đảm bảo chương trình học hoàn thành đúng tiến độ cho càng nhiều lớp càng tốt.

Để tối ưu hóa lịch học cho toàn trường, cần xây dựng một thời khóa biểu chi tiết dựa trên lịch học hiện có, bao gồm thông tin về môn học, giảng viên, số buổi học và độ ưu tiên Mục tiêu là tìm kiếm và bổ sung thêm nhiều môn học vào lịch trình, từ danh sách đã được xác định, nhằm nâng cao hiệu quả học tập cho sinh viên.

3.4 Hàm mục tiêu cần tối ƣu của bài toán

− Cần xử lý giải quyết tốt các sự kiện, có nghĩa là phải bổ sung vào lịch đã có sẵn

− Xác định lịch để có thể thêm tối đa số buổi bù trong khung thời gian cho trước

3.5 Mô hình hóa toán học

=1 khi lớp i học môn j với i ∈ {1, , I}, j ∈ {1, , J}, k ∈ {1, , K}, t ∈ {1, , T}, trong đó

∈ N số buổi cần sắp xếp học bù môn j của lớp I, với

∈ {0,1}, và =1 nếu thầy k bận tại thời điểm t hoặc thầy k không dạy môn j của lớp i, với i ∈ {1, , I}, j ∈ {1, , J}, k ∈ {1, , K}, t ∈ {1, , T}.

Một lớp chỉ học 1 môn học lớp tại 1 thời điểm

Tổng số buổi học bù không đƣợc vƣợt quá số buổi nghỉ.

Thầy k bận vào thời điểm thoặc thầy k không dạy môn j của lớp i.

Một môn học lớp không thể học 2 buổi 1 ngày.

Xác định lịch để có thể thêm tối đa số buổi bù trong khung thời gian cho trước

∑ ∑ ∑ ∑ Ý nghĩa của mô hình toán học đề xuất

Mô hình toán học được đề xuất cung cấp một cách mô tả rõ ràng và chính xác cho bài toán nghiên cứu, thay thế cho các mô tả bằng lời Điều này giúp hiện thực hóa và kiểm nghiệm tính khả thi của thời khóa biểu bù một cách hiệu quả hơn.

Có nhiều phương pháp để mô hình hóa bài toán, và mô hình được đề xuất tập trung vào mô hình hóa tuyến tính Điều này giúp kế thừa hiệu quả các kết quả toán học cơ bản và tận dụng các solver cùng thư viện đã được phát triển trên thế giới trong hơn hai mươi năm qua, bắt đầu từ đầu thế kỷ 21.

- Ngoài ra, việc khéo léo giảm thiểu các thông số giúp mô hình rõ ràng hơn.

Mô hình đề xuất đã giảm thiểu đáng kể số lượng ràng buộc cứng trong việc xếp lịch bằng cách gom nhóm các ràng buộc, như ràng buộc số 3 "giáo viên không bận vào thời điểm hoặc không dạy môn nào của lớp I" Điều này giúp cải thiện tính phù hợp trong việc sắp xếp lịch giảng dạy, đặc biệt liên quan đến các yếu tố thời gian và chuyên môn của từng giảng viên.

Trong chương này, chúng tôi đã trình bày ngữ cảnh và động cơ của bài toán nghiên cứu, cùng với mô tả chi tiết về bài toán Ngữ cảnh thí điểm tại trường Cao đẳng nghề được mô tả thông qua quy trình hiện có Chúng tôi đề xuất một mô hình toán học nhằm mô tả rõ ràng và logic bài toán nghiên cứu, đồng thời tạo nền tảng để tích hợp với các solver ngoài công nghiệp, giúp xác định lời giải chính xác.

Mô hình hóa toán học

=1 khi lớp i học môn j với i ∈ {1, , I}, j ∈ {1, , J}, k ∈ {1, , K}, t ∈ {1, , T}, trong đó

∈ N số buổi cần sắp xếp học bù môn j của lớp I, với

∈ {0,1}, và =1 nếu thầy k bận tại thời điểm t hoặc thầy k không dạy môn j của lớp i, với i ∈ {1, , I}, j ∈ {1, , J}, k ∈ {1, , K}, t ∈ {1, , T}.

Một lớp chỉ học 1 môn học lớp tại 1 thời điểm

Tổng số buổi học bù không đƣợc vƣợt quá số buổi nghỉ.

Thầy k bận vào thời điểm thoặc thầy k không dạy môn j của lớp i.

Một môn học lớp không thể học 2 buổi 1 ngày.

Xác định lịch để có thể thêm tối đa số buổi bù trong khung thời gian cho trước

∑ ∑ ∑ ∑ Ý nghĩa của mô hình toán học đề xuất

Mô hình toán học được đề xuất cung cấp một cách mô tả rõ ràng và chính xác cho bài toán nghiên cứu Sự mô tả này thay thế cho các hình thức mô tả bằng lời, giúp cải thiện hiệu quả trong việc hiện thực hóa và kiểm nghiệm tính khả thi của thời khóa biểu bù được đề xuất.

Có nhiều phương pháp để mô hình hóa bài toán, và mô hình đề xuất tập trung vào mô hình hóa tuyến tính Điều này cho phép kế thừa hiệu quả các kết quả toán học cơ bản và tận dụng các solver, thư viện đã được phát triển trên toàn cầu trong hơn hai mươi năm qua, kể từ đầu thế kỷ 21.

- Ngoài ra, việc khéo léo giảm thiểu các thông số giúp mô hình rõ ràng hơn.

Mô hình đề xuất đã tối ưu hóa quá trình xếp lịch bằng cách gom nhóm các ràng buộc, chẳng hạn như nhóm ràng buộc số 3 "giáo viên không bận vào thời điểm này hoặc không dạy môn nào của lớp I" Nhờ đó, số lượng ràng buộc cứng cần xem xét đã giảm đáng kể, giúp cải thiện sự phù hợp trong việc xếp lịch theo các yếu tố thời gian và chuyên môn giảng dạy của từng giảng viên.

Chương này trình bày ngữ cảnh và động cơ của bài toán nghiên cứu, đồng thời mô tả quy trình hiện có tại trường Cao đẳng nghề Một mô hình toán học được đề xuất nhằm mô tả rõ ràng và logic bài toán nghiên cứu, đồng thời tạo nền tảng cho việc tích hợp với các solver ngoài công nghiệp để tìm ra lời giải chính xác.

PHƯƠNG PHÁP ĐỀ XUẤT

Mô tả đầu vào của bài toán

- Số lớp sẽ đƣợc xếp lịch trong 1 học kỳ 179 lớp

- Kế hoạch học tập các môn học trong kỳ của lớp.

Mỗi kỳ học, các khoa lập kế hoạch học tập cho lớp dựa trên tiến độ đào tạo từ đầu khóa Danh sách các môn học sẽ được xác định từ đầu kỳ để đảm bảo sự phù hợp với chương trình giảng dạy.

- Kế hoạch bố trí giáo viên của khoa.

Ví dụ kế hoạch bố trí giáo viên của khoa cơ khí cho lớp Cắt gọt kim loại

Bảng 4.1 Bảng mẫu kế hoạch giáo viên

STT Tên môn học Số tiết Giảng viên giảng dạy Ghi chú

1 Toán kỹ thuật 2 80 Đoàn Nam Giang

2 Gia công trên các máy công cụ vạn năng 240 Nguyễn Xuân Huy

3 LĐ, kiểm tra các mạch điện ứng dụng và biện pháp bảo vệ

4 Toán kỹ thuật 2 80 Đoàn Nam Giang

- Kế hoạch bố trí phòng học của lớp.

Ví dụ kế hoạch bố trí phòng học của khoa cơ khí cho lớp Cắt gọt kim loại

Bảng 4.2 Bảng mẫu kế hoạch phòng học cho 1 lớp.

Từ kế hoạch bố trí giáo viên và kế hoạch bố trí phòng học của của khoa cho lớp

Cắt gọt kim loại K10 ta có lịch học nhƣ sau

Bảng 4.3 Bảng mẫu thời khóa biểu của 1 lớp học

Lớp Sĩ số Môn học/mô đun Số tiết

Ngày kết thúc Thứ Buổi Số tiết

STT Tên môn học Số tiết Phòng học/xưởng Ghi chú

2 Gia công trên các máy công cụ vạn năng 240 WORKSHOP

3 LĐ, kiểm tra các mạch điện ứng dụng và biện pháp bảo vệ 120 CNC 3.3

5 Tiếng Anh kỹ thuật 80 CNC5.3

7 Tiếng Anh kỹ thuật 80 CNC5.3

STT Tên môn học Số tiết Giảng viên giảng dạy Ghi chú

5 Tiếng Anh kỹ thuật 80 Nguyễn Hoàng Vân

7 Tiếng Anh kỹ thuật 80 Nguyễn Hoàng Vân

Vấn đề sinh viên quay lại học tập sau khi đi thực tập về.

Trước khi bắt đầu thực tập, sinh viên cần ưu tiên sắp xếp lịch học Nếu không gặp trở ngại từ giáo viên, bạn học hay phòng học, nên xem xét các giải pháp để tăng thời gian học cho các môn học, nhằm đảm bảo tiến độ đào tạo.

- Giải pháp tăng thời lƣợng đào tạo.

Ưu tiên những môn học có thể hoàn thành trong thời gian còn lại Có thể tăng số buổi học hoặc chuyển những môn có thời lượng lớn sang kỳ học tiếp theo để đảm bảo tiến độ học tập.

Lớp Sĩ số Môn học/mô đun Số tiết

Ngày kết thúc Thứ Buổi Số tiết

Chủ nhiệm Lê Tuyên Giáo

Toán kỹ thuật 2 80 7.8.2017 9.10.2017 Thứ 2 7h30-10h45 4 Đoàn Nam Giang

Gia công trên các máy công cụ vạn năng

LĐ, kiểm tra các mạch điện ứng dụng và biện pháp bảo vệ

Hình 4.1 Thời khóa biểu của 1 lớp xem trên cổng thông tin

Nếu lịch học bị xung đột với lịch của giảng viên, hãy ưu tiên những môn học không bị ảnh hưởng và đánh dấu các môn học có vấn đề để dễ dàng giải quyết Cần tìm ra giải pháp hợp lý về việc sắp xếp giảng viên theo lịch học cũ.

+ Giải pháp tăng thời lƣợng đào tạo.

Nếu lịch học bị ảnh hưởng do phòng học đang sửa chữa hoặc bảo trì, cần tiến hành đổi phòng và tiếp tục theo lịch học cũ Đồng thời, nghiên cứu các giải pháp để tăng thời gian giảng dạy cho các môn học nhằm đảm bảo tiến độ đào tạo.

Phân tích tính khả thi của bài toán nghiên cứu

Phần này không xem xét độ khó của bài toán mà chỉ tập trung vào việc xác định sự tồn tại của lời giải, đặc biệt qua việc sử dụng máy tính để tính toán Chúng tôi sẽ thống kê các số liệu hiện có và nếu không còn khung giờ trống, việc chèn thêm buổi nghỉ sẽ không khả thi Do đó, giải pháp đề xuất là thử nghiệm chèn tối đa số buổi bù vào trong một số tuần mô phỏng.

Đề xuất này luôn mang lại kết quả khả thi và khi sử dụng Solver, mô hình sẽ tối ưu hóa kết quả một cách tốt nhất Tuy nhiên, câu hỏi quan trọng là liệu tài nguyên, đặc biệt là thời gian tính toán, có đủ để thực hiện trong thực tế hay không Việc tính toán và đo đạc này chủ yếu phục vụ cho nghiên cứu và mô tả chất lượng của giải pháp, sẽ được thảo luận chi tiết trong các phần sau Tóm lại, với hướng thực hiện này, giải pháp đề xuất cam kết mang lại kết quả tối ưu nhất có thể.

Giải pháp đề xuất

Trong luận văn này, học viên trình bày mô hình của bài toán và thực hiện khảo sát nhằm đánh giá chất lượng nghiệm thu cũng như thời gian tính toán của giải pháp được đề xuất.

Học viên đã áp dụng ngôn ngữ lập trình Java để truy xuất dữ liệu từ mô phỏng thực tế và xuất kết quả cho đơn vị sử dụng thí điểm.

Học viên khuyến nghị sử dụng công cụ solver Gurobi để hỗ trợ trong việc mô phỏng tính toán và xác định nghiệm từ không gian nghiệm được mô tả trong mô hình toán học đã nêu.

Mỗi trường hợp dưới đây sẽ tạo ra 5 mẫu ngẫu nhiên

- Số lớp cần xếp lịch bù {1,2,3,5}

- Thời lƣợng thực tập theo tuần ~[1,4] Từ đó xác định đƣợc số buổi của một lớp môn học cần xếp lịch bù.

- Thời gian cần sắp lịch bù.

Kết quả kiểm thử thu đƣợc

Sau khi hiện thực mô hình bằng ngôn ngữ Java và có tích hợp Solver Gurobi.Kết quả thực nghiệm đƣợc tổng hợp nhƣ trong Bảng sau

Bảng 4.4 Bảng kết quả thực nghiệm

Dựa trên các mẫu mô phỏng trên với số lớp cần xếp lịch bù trong tập {5, 10, 20,

Hệ thống mô phỏng số buổi cần bù được xác định dựa trên số buổi học thực tế của lớp trong khoảng thời gian từ 1, 2 đến 4 tuần Kết quả cho thấy sự tương quan giữa số buổi cần bù và thời khóa biểu của lớp học.

- Luôn đề xuất được lịch cải tiến trong tất cả các trường hợp mô phỏng

- Thời gian tính toán là phù hợp (tối đa không vƣợt quá nửa phút)

Số tuần bù/ lập lịch Kết quả Thời gian tính toán (ms)

- Số lƣợng buổi đề xuất bù chiếm hơn 50% số lƣợng buổi mong muốn học bù.

Kết quả sẽ được đánh giá dựa trên hai tiêu chí: số lượng tuần bù và số lượng lớp cần xếp lịch bù đồng thời.

4.4.1 Đánh giá kết quả theo tuần

Từ kết quả ở Bảng 4.4 trên, nếu xét từng phương diện lịch bù theo số lượng tuần, chúng ta sẽ thu đƣợc các biểu đồ minh họa nhƣ sau.

Biểu Đồ 4.1 Xếp lịch bù 1 tuần

Trong biểu đồ 4.1 trên, các thông tin mà chúng ta có thể quan sát nhƣ sau

- Mẫu dữ liệu đều thí điểm mô phỏng với số tuần bù và số tuần nghỉ là nhƣ nhau và xét với trường hợp đơn giản nhất là 1 tuần.

- Các giá trị từ 1,2, 3, 4, 5,6 trong trục hoàn lần lƣợt mô tả mẫu dữ liệu xét tương ứng với số lượng lớp là 5, 10, 20, 30, 50, và 100.

Mặc dù các đường trên biểu đồ không cùng đơn vị để so sánh trực tiếp, nhưng khi xem xét từ góc độ tăng trưởng theo thời gian, ta nhận thấy rằng sự gia tăng này diễn ra theo cấp số mũ, và kết quả thu thập cũng cho thấy một dạng tương tự.

Biểu đồ 4.2 dưới đây xem xét các thông tin thu được từ việc xếp lịch bù trong hai tuần.

Biểu Đồ 4.2 Xếp lịch bù 2 tuần Với biểu đồ 4.2 trên, các thông tin mà chúng ta có thể quan sát nhƣ sau

Mẫu dữ liệu trong thí điểm mô phỏng cho thấy số tuần bù và số tuần nghỉ là tương đương, được so sánh với trường hợp là 2 tuần dựa trên biểu đồ trước đó.

- Các giá trị từ 1, 2, 3, 4, 5, 6 trong trục hoàn lần lƣợt mô tả mẫu dữ liệu xét tương ứng với số lượng lớp là 5, 10, 20, 30, 50, và 100.

Mặc dù các đường trên biểu đồ không cùng đơn vị để so sánh trực tiếp, nhưng khi xem xét từ góc độ tăng trưởng theo thời gian, ta thấy rằng mức độ tăng trưởng của thời gian tính toán theo cấp số mũ diễn ra nhanh hơn so với Biểu đồ 4.1, mặc dù kết quả thu thập có hình dạng tương tự.

Biểu đồ 4.3 dưới đây xem xét các thông tin thu được từ việc xếp lịch bù trong bốn tuần.

Biểu Đồ 4.3 Xếp lịch bù 4 tuần Trong biểu đồ 4.3 trên, các thông tin mà chúng ta có thể quan sát nhƣ sau

- M u d li u đ u thí đi m mô ph ng v i s tu n bù và s tu n ngh làẫ ữ ệ ề ể ỏ ớ ố ầ ố ầ ỉ nh nhau và xét v i trư ớ ường s tu n bù và s tu n ngh l n nh ttrongố ầ ố ầ ỉ ớ ấ m u th là 4 tu n.ẫ ử ầ

- Các giá tr t 1,2, 3, 4, 5,6 trong tr c hoàn l n lị ừ ụ ầ ượt mô t m u d li uả ẫ ữ ệ xét tương ng v i s lứ ớ ố ượng l p là 5, 10, 20, 30, 50, và 100.ớ

- Các đường trên bi u đ cũng có hình dáng tăng trể ồ ưởng tương t nhauự trong đó th i gian tính toán có đ tăng nhanh h n so v i các thông sờ ộ ơ ớ ố khác.

4.4.2 Đánh giá kết quả theo số lƣợng lớp

- 5 lớp, số tuần nghỉ là 1,2,4 và số tuần bù là 1,2,4,8,10, dữ liệu thực nghiệm thu đƣợc là (bảng kết quả, và biểu đồ minh họa và giải thích)

Bảng 4.5 Bảng kết quả thực nghiệm cho 5 lớp học

Dựa trên bảng số liệu tổng hợp, chúng ta có thể phân tích hai khía cạnh: số buổi bù cho 5 lớp và thời gian tính toán để xác định số buổi bù nhiều nhất.

Số buổi cần bù Số buổi bù Thời gian (ms)

4 12 98 96 866 nhất trong điều kiện giới hạn cho phép (số tuần đƣợc bù) Các Bảng và Biểu đồ sau đây sẽ mình họa kết quả thu đƣợc.

Bảng 4.6 Bảng mô tả số buổi bù đƣợc cho 5 lớp

Ngh 1 tu n ỉ ầ Ngh 2 tu n ỉ ầ Ngh 4 tu n ỉ ầ

Biểu Đồ 4.4 Biểu đồ mô tả số buổi bù đƣợc cho 5 lớp

Bảng 4.7 Bảng mô tả thời gian tính toán khi tìm buổi bù cho 5 lớp

Biểu Đồ 4.5 Biểu đồ mô tả thời gian tính toán khi tìm buổi bù cho 5 lớp

Trong các Bảng 4.6, 4.7 và các Biểu đồ 4.4, 4.5 trên, các thông tin mà chúng ta có thể quan sát nhƣ sau

- Mẫu dữ liệu đều thí điểm mô phỏng với số tuần tuần nghỉ là 1, 2, 4 và số tuần bù cho kiểm thử là 1, 2, 4, 8, 10, 12.

- Trục hoành có các mốc từ 1 đến 6 mô tả các mẫu kiểm thử có số tuần bù lần lƣợt là 1, 2, 4, 8, 10, 12

- Trục tung mô tả số buổi bù có thể đƣợc thêm vào thời khóa biểu của 5 lớp học đang quan sát

Biểu đồ cho thấy rằng khi số tuần bù đƣợc tăng lên 1, 2, 4, 8, 10, 12, thời gian tính toán sẽ thay đổi tương ứng trong các kịch bản nghỉ với số tuần khác nhau.

Nếu số tuần nghỉ là 1, cần bù 4 tuần để đủ số buổi Tương tự, nếu nghỉ 2 tuần, cần 8 tuần bù để hoàn thành số buổi cần thiết.

- Trong trường hợp có số tuần nghỉ là 4 thì học viên dự đoán cần có số tuần cần bù là phải 16 mới tìm đủ số buổi cần bù.

- 10 lớp, số tuần nghỉ là 1,2,4 và số tuần bù là 1,2,4,8,10, dữ liệu thực nghiệm thu đƣợc là (bảng kết quả, và biểu đồ minh họa và giải thích)

Từ bảng số liệu tổng hợp trên, chúng ta có thể bóc tách ra nhìn dưới hai góc nhìn

- Số buổi bù đƣợc cho 5 lớp

- Thời Gian tính toán để tìm số buổi bù nhiều nhất trong điều kiện giới hạn cho phép (số tuần đƣợc bù).

Các Bảng và Biểu đồ sau đây sẽ mình họa kết quả thu đƣợc.

- Nếu số tuần nghỉ là 1 thì số tuần bù cần thiết là 4 thì đã đủ số buổi cần bù.

- Nếu số tuần nghỉ là 2 thì số tuần cần bù là 8 thì đã đủ số buổi cần bù.

- Nếu số tuần nghỉ là 4 thì học viên dự đoán cần có số tuần cần bù là phải

16 mới tìm đủ số buổi cần bù.

- Thời gian tính toán gần như tương đương trong các trường hợp nghỉ 1 tuần, nghỉ 2 tuần và nghỉ 4 tuần.

20 lớp, số tuần nghỉ là 1,2,4 và số tuần bù là 1,2,4,8,10, dữ liệu thực nghiệm thu đƣợc là (bảng kết quả, và biểu đồ minh họa và giải thích)

Từ bảng số liệu tổng hợp trên, chúng ta có thể bóc tách ra nhìn dưới hai góc nhìn

- Số buổi bù đƣợc cho 20 lớp

- Thời gian tính toán để tìm số buổi bù nhiều nhất trong điều kiện giới hạn cho phép (số tuần đƣợc bù).

Các Bảng và Biểu đồ sau đây sẽ mình họa kết quả thu đƣợc.

Biểu Đồ 4.8 Biểu đồ mô tả số buổi bù đƣợc cho 20 lớp Bảng 4.13 Bảng mô tả thời gian tính toán khi tìm buổi bù cho 20 lớp

- Thời gian đề tìm ra lịch mà có số buổi bù nhiều nhất gần tương đương nhau cho các kịch bản kiểm thử nghỉ 1 tuần/ nghỉ 2 tuần/ nghỉ 4 tuần.

Dựa trên bảng số liệu về số buổi bù, nếu số tuần nghỉ là 1, cần 4 tuần bù để đủ số buổi; nếu nghỉ 2 tuần, cần 8 tuần bù Dự đoán rằng nếu nghỉ 4 tuần, sẽ cần 16 tuần bù để đạt đủ số buổi cần thiết, và kết quả ở tuần 12 cũng gần đạt như mong đợi.

- 50 lớp, số tuần nghỉ là 1,2,4 và số tuần bù là 1,2,4,8,10, dữ liệu thực nghiệm thu đƣợc là (bảng kết quả, biểu đồ minh họa và giải thích)

Dựa trên bảng số liệu tổng hợp, chúng ta có thể phân tích từ hai khía cạnh: số buổi bù được cho 50 lớp và thời gian tính toán để xác định số buổi bù tối đa trong giới hạn cho phép (số tuần được bù) Các bảng và biểu đồ dưới đây sẽ minh họa kết quả đạt được.

Biểu Đồ 4.10 Biểu đồ mô tả số buổi bù đƣợc cho 50 lớp Bảng 4.16 Bảng mô tả thời gian tính toán khi tìm buổi bù cho 50 lớp

- Nếu số tuần nghỉ là 1 thì số tuần bù cần thiết là 4 thì đã đủ số buổi cần bù.

Và nếu số tuần nghỉ là 2 và với số tuần cần bù là 8 thì đã đủ số buổi cần bù.

Nếu có 4 tuần nghỉ, chúng ta có thể dự đoán rằng cần bù 16 tuần để đủ số buổi cần thiết.

- 100 lớp, số tuần nghỉ là 1,2,4 và số tuần bù là 1,2,4,8,10, dữ liệu thực nghiệm thu đƣợc là (bảng kết quả, biểu đồ minh họa và giải thích)

Dựa trên bảng số liệu tổng hợp, chúng ta có thể phân tích từ hai khía cạnh: số buổi bù cho 100 lớp và thời gian tính toán để xác định số buổi bù tối đa trong giới hạn cho phép (số tuần được bù) Các bảng và biểu đồ dưới đây sẽ minh họa kết quả đạt được.

Số tuần bù Nghỉ 1 tuần Nghỉ 2 tuần Nghỉ 4 tuần

- Thời gian tính toán ra nghiệm tốt nhất là tương đương cho các kịch bản.

Khi số tuần nghỉ là 1, trường cần bù 4 tuần để đảm bảo đủ số buổi học Nếu số tuần nghỉ tăng lên 2, trường sẽ cần bù 8 tuần, điều này cũng đáp ứng đủ số buổi cần thiết.

4 thì học viên dự đoán cần có số tuần cần bù là phải 16 mới tìm đủ số buổi cần bù.

Khi số tuần để sắp lịch bù gấp 4 lần số tuần nghỉ do thực tập, khả năng tìm ra lịch bù đầy đủ cho tất cả các lớp là rất cao.

Tổng hợp các thảo luận khi áp dụng thí điểm

Trong quá trình thí điểm dữ liệu thực tế tại trường Cao đẳng nghề Quốc, nhiều câu hỏi thảo luận quan trọng đã được nêu ra nhằm đảm bảo tính hiệu quả và khả thi của dự án.

Tế Lilama2 Trong mục này, các câu hỏi và trả lời thường gặp liên quan đến đề xuất trong đề tài luận văn đƣợc tổng hợp lại nhƣ sau

1 Giải thuật có đảm bảo các môn học kết thúc trong kỳ không?

Tiêu đề	Cải Tiến Xếp Lịch Tại Trường Cao Đẳng Nghề Nhằm Đáp Ứng Yêu Cầu Thời Vụ
Người hướng dẫn	PGS.TS. Huỳnh Tường Nguyên
Trường học	Trường Đại Học Lạc Hồng
Chuyên ngành	Công Nghệ Thông Tin
Thể loại	Luận Văn Thạc Sĩ
Năm xuất bản	2020
Thành phố	Đồng Nai

Định dạng
Số trang	77
Dung lượng	2,76 MB