ĐẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA

PHẠM THỊ BÍCH TRÂM

ĐỀ XUẤT GIẢI PHÁP NÂNG CAO HIỆU QUẢ
CƠNG TÁC XẾP THỜI KHOÁ BIỂU - ỨNG DỤNG
TẠI MỘT TRƯỜNG ĐẠI HỌC TẠI CẦN THƠ

Chuyên ngành: Kỹ thuật công nghiệp
Mã số: 8520117

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 07 năm 2023


Cơng trình được hồn thành tại: Trường Đại học Bách Khoa – ĐHQG – HCM
Cán bộ hướng dẫn khoa học: TS. LÊ ĐỨC ĐẠO
Cán bộ chấm nhận xét 1: TS. Nguyễn Đức Duy
Cán bộ chấm nhận xét 2: TS. Trần Quỳnh Lê
Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM ngày
08 tháng 07 năm 2023
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. Chủ tịch: PGS.TS Đỗ Ngọc Hiền
2. Thư ký: TS. Lê Thị Diễm Châu
3. Phản biện 1: TS. Nguyễn Đức Duy
4. Phản biện 2: TS. Trần Quỳnh Lê
5. Uỷ viên: TS. Đỗ Thành Lưu
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành
sau khi luận văn đã được sữa chữa (nếu có).

CHỦ TỊCH HỘI ĐỒNG

TRƯỞNG KHOA CƠ KHÍ


i

ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƯỜNG ĐẠI HỌC BÁCH KHOA

Độc lập – Tự do – Hạnh phúc

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên: PHẠM THỊ BÍCH TRÂM

MSHV: 2170122

Ngày, tháng, năm sinh: 07/10/1996

Nơi sinh: Cần Thơ

Chuyên ngành: Kỹ thuật công nghiệp

Mã số: 8520117

I.

TÊN ĐỀ TÀI

Tiếng Việt: Đề xuất giải pháp nâng cao hiệu quả cơng tác xếp thời khóa biểu –

Ứng dụng tại một trường Đại học tại Cần Thơ.
Tiếng Anh: Proposing solutions to improve the efficiency of timetabling
problem - Application at a university in Can Tho.
NHIỆM VỤ VÀ NỘI DUNG:
Nhiệm vụ: Đề xuất giải pháp nâng cao hiệu quả hoạt động tại Trường Đại học
Kỹ thuật - Công nghệ Cần Thơ.
Nội dung:
- Nghiên cứu và tổng hợp lý thuyết về điều độ, các giải thuật được ứng dụng để
giải quyết bài toán lập lịch, giải thuật di truyền và ứng dụng của giải thuật để giải
quyết trường hợp thực tế.
- Phân tích, khảo sát và đánh giá thực trạng cơng tác xếp thời khóa biểu tại
Trường Đại học Kỹ thuật - Công nghệ Cần Thơ.
- Đề xuất giải pháp nâng cao hiệu quả cơng tác xếp thời khóa biểu.
II. NGÀY GIAO NHIỆM VỤ: 06/02/2023
III. NGÀY HOÀN THÀNH NHIỆM VỤ: 11/06/2023
IV. CÁN BỘ HƯỚNG DẪN: TS. LÊ ĐỨC ĐẠO
Tp. Hồ Chí Minh, ngày ….. tháng …. năm 2023
CÁN BỘ HƯỚNG DẪN

CHỦ NHIỆM BỘ MÔN ĐÀO TẠO

(Họ tên và chữ ký)

(Họ tên và chữ ký)

TS. LÊ ĐỨC ĐẠO

PGS.TS. ĐỖ NGỌC HIỀN

TRƯỞNG KHOA CƠ KHÍ



ii

LỜI CẢM ƠN
Luận văn tốt nghiệp thạc sĩ là công trình tổng kết quá trình học tập, nghiên cứu
trình độ sau đại học của cá nhân tôi tại Đại học Quốc gia TP. Hồ Chí Minh - Trường
Đại học Bách Khoa. Để hồn thành luận văn, tơi may mắn nhận được rất nhiều sự
giúp đỡ và hỗ trợ trực tiếp cũng như gián tiếp từ Nhà trường, Thầy cô, gia đình, đồng
nghiệp, bạn bè. Tại đây, tơi xin gửi lời cảm ơn chân thành nhất đến:
-

Thầy Cô thuộc Bộ môn Kỹ thuật hệ thống cơng nghiệp, Khoa Cơ khí, phịng
Đào tạo Sau Đại học, Trường Đại học Bách Khoa Thành phố Hồ Chí Minh đã
giúp đỡ tơi trong suốt q trình học tập tại Trường và thực hiện luận văn.

-

Lãnh đạo, Thầy Cô và đồng nghiệp của tôi tại Trường Đại học Kỹ thuật - Công
nghệ Cần Thơ đã luôn hỗ trợ, động viên và tạo mọi điều kiện tốt nhất để tơi
tập trung học tập nâng cao trình độ và hồn thành luận văn.

-

Cảm ơn gia đình, bạn bè đã luôn ở bên động viên, tạo động lực để tơi nỗ lực
cố gắng hồn thành luận văn.

-

Đặc biệt, tơi xin gửi lời cảm ơn sâu sắc và chân thành nhất đến TS. Lê Đức

Đạo đã hướng dẫn, giúp đỡ và góp ý để tơi hồn thiện luận văn.
Mặc dù đã có nhiều cố gắng để nghiên cứu và thực hiện, nhưng do hạn chế về

kiến thức và kinh nghiệm, luận văn chắc chắn khơng tránh khỏi những thiếu sót và
hạn chế. Tơi rất hy vọng nhận được những góp ý quý giá của mọi người để luận văn
có thể hồn chỉnh hơn.
Xin chân thành cảm ơn!
Tp. Hồ Chí Minh, ngày ….. tháng …. năm 2023
Học viên

Phạm Thị Bích Trâm


iii

TÓM TẮT LUẬN VĂN
“Đề xuất giải pháp nâng cao hiệu quả cơng tác xếp thời khóa biểu – Ứng dụng
tại một trường Đại học tại Cần Thơ”

Hiệu quả của công việc là một trong những thước đo đánh giá hiệu quả của một
tổ chức. Cơng tác xếp thời khóa biểu không chỉ ảnh hưởng đến công tác vận hành mà
ảnh hưởng trực tiếp đến hiệu quả tổ chức giảng dạy của giảng viên và hiệu quả học
tập của sinh viên. Đề xuất giải pháp nâng cao hiệu quả công tác xếp thời khóa biểu là
việc làm cần thiết và cấp bách của Trường Đại học Kỹ thuật - Công nghệ Cần Thơ.
Phương pháp tiếp cận của nghiên cứu là nghiên cứu lý thuyết - thực trạng - giải
pháp. Nghiên cứu sử dụng 2 nguồn dữ liệu: sơ cấp và thứ cấp với mục tiêu đánh giá
hiện trạng công tác xếp thời khóa biểu của Trường, khảo sát đội ngũ giảng viên để
đánh giá sự hài lòng và ghi nhận kiến nghị được đề xuất. Giải pháp được xây dựng
để giải quyết vấn đề tồn tại dựa trên thực trạng nghiên cứu.
Giải pháp đề xuất theo q trình của cơng tác xếp thời khóa biểu. Bắt đầu từ

bước thu thập dữ liệu đầu vào của cơng tác, q trình thực hiện và kết quả đầu ra.
Giải pháp có thể được thử nghiệm trên bộ dữ diệu lớn hơn và triển khai thực tế.


iv

ABSTRACT
“Proposing solutions to improve the efficiency of timetabling problem Application at a university in Can Tho”
Work efficiency is one of the measures to evaluate the effectiveness of an
organization. The scheduling work not only affects the operation, but also directly
affects the effectiveness of the teaching organization of the lecturers and the learning
efficiency of the students. Proposing solutions to improve the efficiency of
timetabling problem is a necessary and urgent job of Can Tho University of
Technology.
The research approach is to study theory - reality - solution. The study uses two
data sources: primary and secondary with the goal of assessing the current status of
the University's scheduling problem, surveying the teaching staff to assess
satisfaction and recording proposed recommendations. The solution is built to solve
the existing problem based on the research situation.
Proposed solutions according to the process of timetabling problem. Starting
from the step of collecting the input data of the work, the implementation process and
the outputs. The solution can be tested on a larger magic data set and implemented in
real life.


v

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn “ Đề xuất giải pháp nâng cao hiệu quả công tác xếp

thời khóa biểu – Ứng dụng tại một trường đại học tại Cần Thơ ” là cơng trình nghiên
cứu của cá nhân tôi, không sao chép bất kỳ tài liệu nghiên cứu nào của người khác.
Các dữ liệu, số liệu và tài liệu tham khảo sử dụng trong luận văn được khảo sát, trích
dẫn, phân tích từ số liệu sơ cấp và thứ cấp có nguồn gốc và chú thích rõ ràng, trung
thực. Tơi xin hồn tồn chịu trách nhiệm về tính xác thực, minh bạch của luận văn.
Học viên

Phạm Thị Bích Trâm


vi

MỤC LỤC
Trang
NHIỆM VỤ LUẬN VĂN THẠC SĨ ........................................................................... i
LỜI CẢM ƠN ............................................................................................................ ii
TÓM TẮT LUẬN VĂN............................................................................................ iii
ABSTRACT .............................................................................................................. iv
LỜI CAM ĐOAN .......................................................................................................v
MỤC LỤC ................................................................................................................. vi
DANH MỤC BẢNG ............................................................................................... viii
DANH MỤC HÌNH .................................................................................................. ix
DANH MỤC VIẾT TẮT ............................................................................................x
Chương 1. GIỚI THIỆU .............................................................................................1
1.1

Tổng quan ......................................................................................................1

1.2


Mục tiêu của đề tài.........................................................................................2

1.3

Đối tượng và phạm vi nghiên cứu .................................................................2

1.4

Phương pháp nghiên cứu ...............................................................................3

1.5

Cấu trúc của đề tài .........................................................................................3

1.6

Kế hoạch thực hiện ........................................................................................4

1.7

Phương pháp luận ..........................................................................................4

Chương 2. CƠ SỞ LÝ THUYẾT VÀ LƯỢT KHẢO TÀI LIỆU ...............................6
2.1

Cơ sở lý thuyêt ...............................................................................................6

2.1.1 Giới thiệu về điều độ ..................................................................................6
2.1.2 Các phương pháp giải bài tốn lập thời khóa biểu .....................................7
2.1.3 Lý thuyết về giải thuật di truyền ................................................................9

2.1.3 Ứng dụng của giải thuật ...........................................................................16
2.2

Lược khảo tài liệu ........................................................................................18

Chương 3. PHÂN TÍCH THỰC TRẠNG CƠNG TÁC XẾP THỜI KHỐ BIỂU
CỦA TRƯỜNG ĐẠI HỌC .......................................................................................22
3.1

Giới thiệu chung ..........................................................................................22

3.2 Phân tích thực trạng cơng tác xếp thời khóa biểu tại Trường Đại học Kỹ
thuật - Công nghệ Cần Thơ ...................................................................................25
3.2.1 Thực trạng cơng tác lập thời khóa biểu tại Trường Đại học Kỹ thuật Công nghệ Cần Thơ ..........................................................................................25


vii

3.2.2 Đánh giá cơng tác xếp thời khóa biểu tại Trường Đại học Kỹ thuật - Công
nghệ Cần Thơ ....................................................................................................35
Chương 4. ĐỀ XUẤT GIẢI PHÁP NÂNG CAO HIỆU QUẢ CÔNG TÁC LẬP
THỜI KHỐ BIỂU CHO TRƯỜNG ĐẠI HỌC .....................................................42
4.1

Chuẩn hóa quy trình lập thời khóa biểu cho trường đại học .......................42

4.2 Ứng dụng giải thuật di truyền để điều độ việc xếp thời khoá biểu cho
Trường Đại học .....................................................................................................48
4.2.1


Thiết lập mơ hình bài tốn điều độ thời khố biểu ...............................48

4.2.2

Áp dụng giải thuật di truyền vào bài toán lập thời khố biểu...............50

4.3

Phân tích kết quả điều độ.............................................................................59

4.3.1

Kết quả ..................................................................................................59

4.3.2 Phân tích ...................................................................................................64
Chương 5. KẾT LUẬN VÀ KIẾN NGHỊ .................................................................73
TÀI LIỆU THAM KHẢO .........................................................................................75
PHỤ LỤC ..................................................................................................................78


viii

DANH MỤC BẢNG
Trang
Bảng 1.1 Kế hoạch thực hiện đề tài ............................................................................4
Bảng 3.1 Quá trình tuyển sinh các ngành thuộc Khoa qua các năm .........................24
Bảng 3.2 Thời khóa biểu Khoa Kinh tế - Quản lý công nghiệp học kỳ 1 (2022-2023)
...................................................................................................................................26
Bảng 3.3 Thống kê thực tế số ngày lên lớp của giảng viên ......................................28
Bảng 4.1 Kế hoạch phân công giảng dạy học kỳ 1 năm học 2022-2023 ..................51

Bảng 4.2 Danh sách phịng học phục vụ cho cơng tác tổ chức lớp học ....................55
Bảng 4.3 Thời khóa biểu Khoa Kinh tế - Quản lý công nghiệp................................61
Bảng 4.4 Thống kê số ngày lên lớp của giảng viên Khoa Kinh tế - Quản lý công
nghiệp ........................................................................................................................64
Bảng 4.5 Thống kê số ngày lên lớp mỗi tuần của giảng viên trước và sau khi áp dụng
giải thuật di truyền ....................................................................................................70


ix

DANH MỤC HÌNH
Trang
Hình 1.1 Sơ đồ phương pháp luận ..............................................................................5
Hình 2.1 Mô tả các bước tiến hành của giải thuật di truyền ..................................... 11
Hình 2.2 Sự lựa chọn cá thể tốt nhất của quá trình đột biến .....................................12
Hình 2.1 Sơ đồ thực hiện giải thuật di truyền đơn giản ............................................14
Hình 3.1 Logo của Trường ĐHKTCNCT ................................................................23
Hình 3.2 Quá trình mở ngành đào tạo chính quy của Trường ĐHKTCNCT............23
Hình 3.3 Phân bổ thời gian dạy học của Trường Đại học Kỹ thuật - Cơng nghệ Cần
Thơ ............................................................................................................................26
Hình 3.4 Biểu đồ thể hiện số học phần và số ngày lên lớp của giảng viên Khoa Kinh
tế - Quản lý cơng nghiệp ...........................................................................................34
Hình 3.5 Biểu đồ thể hiện mức độ hài lòng của cán bộ, giảng viên trong cơng tác xếp
thời khóa biểu ............................................................................................................35
Hình 3.6 Biểu đồ thể hiện các vấn đề khơng hài lịng nhất của cán bộ, giảng viên trong
cơng tác xếp thời khóa biểu.......................................................................................36
Hình 3.7 Biểu đồ thể hiện các vấn đề quan tâm nhất cán bộ, giảng viên trong thời
khóa biểu giảng dạy ..................................................................................................36
Hình 3.8 Sơ đồ xương cá phân tích ngun nhân dẫn đến sự khơng hiệu quả của
cơng tác xếp lịch ........................................................................................................39

Hình 4.1 Sơ đồ quy trình xếp thời khóa biểu được đề xuất ......................................43
Hình 4.2 Sơ đồ tiến độ thực hiện cơng tác xếp thời khóa biểu .................................44
Hình 4.3 Sơ đồ áp dụng giải thuật di truyền vào mơ hình bài tốn ..........................57
Hình 4.4 Giải pháp tối ưu được đề xuất khi kết quả thỏa mãn điều kiện dừng ........60
Hình 4.5 Biểu đồ chênh lệch số ngày lên lớp mỗi tuần của giảng viên trước và sau
khi áp dụng giải thuật. ...............................................................................................71


x

DANH MỤC VIẾT TẮT
BOM: Bill of Materials
GA: Genetic Algorithm
NST: nhiễm sắc thể
GA: Genetic Algorithm
ACO: Ant Colony Optimization


1

Chương 1. GIỚI THIỆU
1.1

Tổng quan
Cơ sở giáo dục đại học là nơi có đội ngũ giảng viên từ nhiều lĩnh vực khác nhau

nhưng cùng nhau làm việc nhằm đáp ứng được mục tiêu giáo dục đã đề ra. Việc thiết
lập thời khố biểu một cách hợp lý, khơng có sự xung đột và giảng viên đều có thể
sử dụng là một trong những thách thức mà hầu hết các trường đại học phải đối mặt.
Thời gian biểu là một bảng các sự kiện khác nhau và lịch trình của chúng [1]. Trong

thời khoá biểu của trường đại học, tổ chức chỉ định các khoá học cho sinh viên do
giảng viên giảng dạy là một tập hợp tài nguyên hữu hạn xác định, bao gồm các khoảng
thời gian và lớp học. Q trình đặt ra nhiều thách thức, có thể thấy trong trường hợp
điển hình: một số nhóm sinh viên có thể hoặc khơng thể học cùng một khóa học tại
cùng một thời điểm [2]. Như vậy, khi xếp lịch dạy phải đảm bảo không xung đột giữa
người học, giảng viên và phòng học. Nhu cầu này làm cho việc lập thời gian biểu cho
các lớp học trở thành một công việc phức tạp và tốn nhiều thời gian để hoàn thành.
Bộ phận lập thời khoá biểu của trường đại học không thể thực hiện phân bổ một
cách ngẫu nhiên mà cần phải xem xét một số yếu tố quyết định. Các ràng buộc hướng
dẫn quá trình lập thời gian biểu hiệu quả. Ràng buộc bao gồm các quy định, chính
sách của các trường đại học, giảng viên và sinh viên có thể được phân loại thành ràng
buộc cứng, mềm hoặc trung bình. Ràng buộc cứng là những quy định hồn tồn khơng
được vi phạm hoặc chồng chéo; ràng buộc mềm là mong muốn của các bên liên quan
trong việc xếp lịch mà khơng có bất kỳ hậu quả nghiêm trọng nào; ràng buộc trung
bình là ưu tiên mà họ khơng muốn bị vi phạm [3]. Bộ phận lập thời khoá biểu cần
xem xét tất cả các ràng buộc này để tạo ra một kết quả tối ưu. Do sự phức tạp này,
những người điều phối thời khoá biểu danh một lượng thời gian đáng kể để tìm ra
giải pháp tốt nhất. Tuy nhiên, ngay cả khi họ có nhiều kinh nghiệm, kết quả xếp lịch
có thể khơng tối ưu do số lượng lớn các kết hợp có thể xảy ra.
Như vậy, sự phân bổ tiết giảng giữa các giảng viên khác nhau trong một tổ chức
tạo thành một vấn đề có tính chất tổ hợp. Việc giải quyết thách thức như vậy và thu
được các giải pháp tối ưu là khó tính tốn. Do đó, bài tốn lập thời khố biểu của


2

trường đại học là trường hợp về bài toán NP - hard [4]. Đây là những vấn đề khơng
có giải pháp hiệu quả cụ thể nào. Trong trường hợp lập thời khố biểu khi khơng có
thuật tốn cụ thể nào có thể được sử dụng để lập thời khố biểu cho các lớp vì mỗi tổ
chức có những ràng buộc đặc biệt của nó [5, 6]. Đồng thời, khi được thực hiện thủ

công, kết quả thu được phụ thuộc vào cách tiếp cận ban đầu và kinh nghiệm của bộ
phận lập thời khố biểu.
Trường Đại học Kỹ thuật - Cơng nghệ Cần Thơ là trường đại học thuộc vùng
Đồng bằng Sông Cửu Long, đào tạo các ngành thuộc lĩnh vực kỹ thuật, công nghệ,
kinh doanh quản lý. Trường đào tạo 22 chuyên ngành với 73 lớp học. Việc giới hạn
về cơ sở vật chất đặc biệt là số lượng phòng học chỉ hơn 30 phòng lý thuyết và 12
phòng thực hành khiến cho việc lập thời khoá biểu của trường trở nên vơ cùng khó
khăn. Bên cạnh đó, việc xếp thời khố biểu cịn mang tính chất thủ cơng mất rất nhiều
thời gian và không tận dụng tối đa được hiệu quả sử dụng phòng. Nghiên cứu “Đề
xuất giải pháp nâng cao hiệu quả cơng tác xếp thời khóa biểu - Ứng dụng tại một
Trường Đại học tại Cần Thơ” được thực hiện với mục tiêu đề xuất giải pháp xếp thời
khóa biểu thỏa mãn tất cả các ràng buộc đồng thời tiết kiệm thời gian, tối ưu hoạt
động giảng dạy, tăng sự hài lòng của giảng viên và khai thác hiệu quả các nguồn lực
đào tạo của nhà trường.
Mục tiêu của đề tài

1.2

Đề tài được thực hiện với mục tiêu:

1.3

-

Tối ưu hoạt động giảng dạy

-

Tăng sự hài lòng của giảng viên
Đối tượng và phạm vi nghiên cứu


Trong đề tài này, tác giả thực hiện phân tích thực trạng, tìm hiểu vấn đề khó khăn
trong cơng tác lập thời khóa biểu. Từ đó đề xuất các giải pháp để nâng cao hiệu quả
của công tác này.
Đề tài tập trung nghiên cứu các đặc điểm của giải thuật di truyền để ứng dụng
vào cơng tác lập thời khóa biểu tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ


3

1.4

Phương pháp nghiên cứu
 Phương pháp nghiên cứu lý thuyết: Nghiên cứu các tài liệu liên quan về giải

thuật di truyền, lược khảo tài liệu về ứng dụng giải thuật trong giải quyết các bài toán
tối ưu và biểu diễn bài tốn lập thời khóa biểu ứng dựng giải thuật di truyền.
 Phương pháp thu thập dữ liệu: Đề tài sử dụng dữ liệu thứ cấp và sơ cấp; dữ
liệu thứ cấp được thu thập tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ và Khoa
Kinh tế - Quản lý công nghiệp về quy mô, cơ cấu đào tạo, kế hoạch phân công giảng
dạy,…; dữ liệu sơ cấp được thu thập qua một cuộc khảo sát được thực hiện tại không
gian nghiên cứu. Cả hai dữ liệu được sử dụng để thống kê, mơ tả và phân tích thực
trạng của cơng tác lập thời khóa biểu.
 Phương pháp nghiên cứu thực nghiệm: Phân tích thực trạng, xây dựng giải
pháp lập thời khố biểu dựa trên quy trình ứng dụng phần mềm và giải thuật di truyền;
thử nghiệm và đánh giá kết quả dựa trên dữ liệu thực tế.
1.5

Cấu trúc của đề tài
Cấu trúc của đề tài bao gồm 5 chương: Chương 1 - Tổng quan: Nội dung chương


1 trình bày lý do chọn đề tài, mục tiêu nghiên cứu, đối tượng và phạm vi nghiên cứu,
phương pháp luận và cấu trúc đề tài; Chương 2 - Cơ sở lý thuyết: Nội dung chương
2 trình bày cơ sở lý thuyết và lượt khảo các tài liệu liên quan đến đề tài; Chương 3 Phân tích thực trạng cơng tác xếp thời khoá biểu tại trường Đại học: Nội dung
Chương 3 giới thiệu về đối tượng được nghiên cứu, phân tích thực trạng quy trình lập
thời khố biểu tại trường Đại học ABC; Chương 4 - Đề xuất giải pháp nâng cao
cơng tác lập thời khố biểu tại trường Đại học: Nội dung Chương 4 trình bày đề
xuất giải pháp nâng cao cơng tác lập thời khố biểu, phân tích kết quả của việc ứng
dụng; Chương 5 - Kết luận và kiến nghị: Nội dung Chương 5 trình bày phần kết
luận đề tài, kết quả đạt được, hạn chế của đề tài và kiến nghị cho việc ứng dụng đề
tài trong trường hợp thực tế.


4

Kế hoạch thực hiện

1.6

Kế hoạch thực hiện đề tài được trình bày ở bảng sau:
Bảng 1.1 Kế hoạch thực hiện đề tài
STT

Nội dung

Thời gian

Kết quả dự kiến
Hiểu rõ công tác xếp TKB tại


1

Nghiên cứu lý
thuyết

09/2022

trường đại học, đặc điểm về giải
thuật ứng dụng vào cơng tác xếp
TKB

2

Tìm hiểu quy trình
xếp TKB

10-11/2022

Tổng hợp được số liệu để đánh
giá hiệu suất
- Đánh giá hiệu quả sử dụng

3

Phân tích thực trạng
xếp thời khố biểu

12/2022 –

nguồn lực từ kết quả xếp TKB


01/2023

- Phân tích ưu điểm và hạn chế
của quy trình hiện tại.

Đề xuất giải pháp
4

trong cơng tác xếp
thời khố biểu

5

Kết luận

02/202303/2023

04/2023

Đề xuất được giải pháp ứng
dụng vào cơng tác lập lịch thời
khố biểu
Đề tài đạt được các mục tiêu ban
đầu đặt ra
(Tác giả, 2023)

1.7

Phương pháp luận

Phương pháp luận của đề tài được thể hiện ở Hình 1.1


5

Nghiên cứu
lý thuyết

Thu thập dữ liệu

Phân tích thực trạng cơng
tác xếp TKB

Không đạt

Đề xuất giải pháp nâng
cao hiệu quả công tác
xếp thời khóa biểu

Đạt
Ứng dụng vào đơn vị
trường đại học

Phân tích và đánh giá

Kết luận

Hình 1.1 Sơ đồ phương pháp luận
(Tác giả tổng hợp, 2023)
Tóm tắt nội dung Chương 1

Nội dung Chương 1 trình bày lý do chọn đề tài, mục tiêu nghiên cứu, xác định đối
tượng và phạm vi nghiên cứu, phương pháp và kế hoạch thực hiện đề tài, sơ đồ
phương pháp luận và cấu trúc của đề tài.


6

Chương 2. CƠ SỞ LÝ THUYẾT VÀ LƯỢT KHẢO TÀI LIỆU
Cơ sở lý thuyết là hệ thống hóa các lý thuyết và quan điểm lý luận để làm luận
điểm khoa học xuyên suốt cho đề tài nghiên cứu. Các lý thuyết về điều độ, các phương
pháp giải bài toán lập thời khóa biểu, lý thuyết về giải thuật di truyền và phương pháp
áp dụng giải thuật được trình bày tại Chương này để làm cơ sở cho việc vận dụng.
Các tài liệu liên quan được lượt khảo để tổng quan về hướng nghiên cứu liên quan
đến đề tài, điểm mới trong hướng nghiên cứu của đề tài.
2.1

Cơ sở lý thuyêt

2.1.1 Giới thiệu về điề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ụ. Kỹ thuật điêu độ được sử
dụng trong mua bán và sản xuất, trong vận chuyển và phân bố, trong xử lý thông tin
và truyền thông [7].
Chức năng của điều độ trong một tổ chức 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 hợp lý các nguồn tài ngun có
hạn phục vụ cơng việc. Sự phân phối tài nguyên thích hợp sẽ cho phép tổ chức đạt
được mục tiêu tối ưu mong muốn. Nguồn tài nguyên (resources) có thể là các máy
móc trong phân xưởng, các đường băng trong sân bay, các công nhân ở các công
trường xây dựng hay các đơn vị xử lý trong môi trường tính tốn,… Các cơng việc
(task) có thể là các sự vận hành trong các công xưởng, các lần cất cánh hay đáp xuống

tại sân bay, các giai đoạn trong một dự án xây dựng hay các chương trình máy tính
được thi hành tương ứng với các nguồn tài nguyên. Mỗi cơng việc có thể có một mức
độ ưu tiên, một thời gian có thể bắt đầu sớm nhất và một ngày tới hạn riêng biệt. Các
mục tiêu trong điều độ sản xuất, có thể có nhiều dạng khác nhau, ví dụ như cực tiểu
thời gian hồn thành các cơng việc hay cực tiểu các công việc trễ hạn [7]
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 nhau. Các sự tương tác này thường thông qua


7

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 tròn các buổi họp hay qua thư báo.
2.1.2 Các phương pháp giải bài tốn lập thời khóa biểu
 Đối với phương pháp tiếp cận truyền thống, một số phương pháp để giải bài
tốn lập thời khóa biểu như sau:
-

Giải thuật vét cạn (tìm kiếm theo chiều rộng hoặc chiều sâu) về mặt ngun
tắc ln tìm được nghiệm nếu bài tốn có nghiệm. Nhưng trên thực tế, các bài
tốn thời khóa biểu khơng nên áp dụng phương pháp này, vì ta phải phát triển
một khơng gian trạng thái cực lớn trước khi đi đến trạng thái đích. Do các hạn
chế về thời gian tính tốn và dung lượng bộ nhớ, không cho phép ta thực hiện
được.
Chẳng hạn, với bài tốn thời khóa biểu cho 50 lớp học, mỗi lớp có 15 mơn
học, mỗi lớp có 30 tiết mỗi tuần thi khơng gian tìm kiếm rất lớn là 50*15*30
trường hợp. Dễ nhận thấy rằng, nếu dùng phương pháp vét cạn thì thời gian
chạy để tìm lời giải tối ưu rất lớn, khó chấp nhận được.

-


Giải thuật leo đồi (Hill Climbing) sử dụng kỹ thuật nâng cấp lặp, áp dụng cho
một số điểm đơn (điểm hiện hành) trong không gian tìm kiếm. Mỗi lần nâng
cấp, một điểm trong lân cận của điểm hiện hành được chọn làm điểm kế tiếp,
nếu nó cho kết quả tốt hơn của hàm mục tiêu. Việc tìm kiếm kết thúc khi khơng
thể nâng cấp được nữa. Rõ ràng, giải thuật leo đồi chỉ cho kết quả tối ưu cục
bộ, kết quả này phụ thuộc vào sự chọn lựa điểm xuất phát, mặt khác ta khơng
có được thông tin về sai số giữa tối ưu cục bộ tìm được và tối ưu tồn cục.
Mặc dù đã cải tiến bằng cách tăng số lượng điểm xuất phát (chọn ngẫu nhiên
hoặc chọn theo kết quả của lần chạy trước), nhưng khi có nhiều giá trị lân cận
thì khả năng tìm được kết quả tối ưu tồn cục của giải thuật leo đồi còn rất
thấp.
 Các phương pháp tiếp cận hiện nay để giải bài tốn xếp thời khóa biểu
Đã có nhiều giải thuật được đề xuất đề giải các bài tốn thời khóa biểu. Các

giải thuật này tìm được lời giải gần tối ưu và là một trong các xu thế phát triển hiện


8

nay đối với các bài tốn chưa thể tìm được lời giải tối ưu thực sự. Các giải thuật này
đều mô phỏng theo tự nhiên như giải thuật luyện kim, giải thuật di truyền, giải thuật
Tabu-search, giải thuật luyện kim... trong đó giải thuật di truyền và tối ưu hóa đàn
kiến được xem là những phương pháp hiệu quả cao nhất.
-

Giải thuật Tabu-search là một trong những metaheuristic được áp dụng nhiều
nhất cho các bài toán tối ưu tổ hợp khó. Bắt nguồn từ một lời giải ban đầu,
thuật giải Tabu Search sẽ lập đi lặp lại việc tìm kiếm trong miền khơng gian
tìm kiếm của bài tồn nhằm mục đích tìm ra lời giải tối ưu. Tại mỗi bước lặp

của mình, thuật giải Tabu Search sẽ tìm kiếm và chỉ ra một lời giải duy nhất
để làm cơ sở cho bước lập tiếp theo. Để tránh việc duyệt trở lại những lời giải
đã được duyệt, thuật giải Tabu Search sử dụng Tabu-list. Danh sách này chứa
những lời giải đã được thực hiện trong các bước lặp trước, chúng sẽ khơng
được sử dụng lại chừng nào nó cịn nằm trong Tabu-list [8].

-

Giải thuật luyện kim (Annealing Algorithm), người ta dùng kỹ thuật thay đổi
entropy của hệ và điều khiển tốc độ hội tụ của quần thể bằng cách biến đổi
nhiệt động học với một tham số nhiệt độ T toàn cục [9]. Để hạn chế sự tối ưu
cục bộ và tăng khả năng khám phá khơng gian tìm kiếm, người ta dùng thủ
thuật giam từng bước nhiệt độ T (đến một mức nào đó). Tuy nhiên, do T chỉ
giảm đến một mức nhất định, nên kỹ thuật luyện kim không tránh khỏi hạn
chế trong việc khám phá khơng gian tìm kiếm và sự hội tụ lân cận.

-

Giải thuật di truyền là sự kết hợp ý tưởng của giải thuật leo đồi và luyện kim.
Đặc trưng của giải thuật này là duy trì một tập hợp các lời giải tiềm năng (gọi
là tập các cá thể hay quần thể), khuyến khích việc hình thành và trao đổi thơng
tin giữa các cá thể trong quần thể thông qua phép lai và phép biến dị. Một q
trình tiến hóa được thực hiện trên một quần thể thực chất là sự tìm kiếm trong
một khơng gian các lời giải tiềm năng. Sự tìm kiếm này địi hỏi sự cân bằng
giữa hai mục tiêu tìm lời giải tốt nhất và khám phá khơng gian tìm kiếm mới.

-

Giải thuật tối vụ đàn kiến (ACO – Ant Colony Optimization) do Dongo đề
xuất là phương pháp tiếp cận hiện đại nhất. Một lần thần ngẫu nhiên trong

ACO cho phép các con kiến xây dựng được một lượng lớn các lời giải khác


9

nhau hơn các phương pháp khác. Tại cùng một thời gian việc sử dụng các
thông tin kinh nghiệm sẽ hướng dẫn các con kiến tìm kiếm được các lời giải
tối ưu. Quan trọng hơn, kinh nghiệm tìm kiếm của con kiến sẽ được sử dụng
để tăng cường trong quá trình lặp xây dựng giải thuật. Thêm vào đó, việc tham
gia của đàn kiến kiến làm cho giải thuật ACO có được một tập hợp các tác
nhân lặp hiệu quả để giải quyết bài toán. Tuy nhiên, giải thuật tối ưu đàn kiến
phức tạp hơn phương pháp tính tốn tiến hóa nhiều.
Hiện nay giải thuật di truyền, giải thuật luyện kim và giải thuật tối ưu đàn kiến
là các phương pháp được sử dụng nhiều nhất để giải quyết bài toán lập thời khóa biểu
[10, 11]. Giải thuật luyện kim sẽ hội tụ biến, cho kết quả với tốc độ nhanh hơn, code
dễ nhưng gặp vấn đề tối ưu cục bộ [12]. Giải thuật tối ưu đàn kiến và giải thuật di
truyền là hai giải thuật tối ưu toàn cục [12, 13]. Tuy nhiên, giải thuật tối ưu đàn kiến
thích hợp cho bài tốn tìm đường đi ngắn nhất hơn là trong các vấn đề khác [13]. Trên
thực tế việc lập thời khóa biểu chỉ diễn ra khoảng hai đến ba lần trong một năm tương
ứng với từng học kỳ. Vì vậy để phù hợp trong luận văn này, tác giả sử dụng giải thuật
di truyền để tiếp cận bài toán lập thời khóa biểu cho trường học do thời gian và chi
phí cho việc lập thời khóa biểu nằm trong khoảng chấp nhận được.
2.1.3 Lý thuyết về giải thuật di truyền
2.1.2.1 Giải thuật di truyền (GAs)
Thuật toán di truyền (Genetic Algorithm - GA) phỏng theo các q trình tiến hố
tự thích nghi của các quần thể sinh học để tối ưu hoá các hàm mục tiêu. Thuật toán
này lần đầu tiên được phát triển bởi John Holland [14] và đã được áp dụng rất thành
công trong nhiều lĩnh vực khác nhau của khoa học máy tính bao gồm: Học máy, lí
thuyết điều khiển và tối ưu tổ hợp,... Trong thuật toán di truyền, người ta sử dụng các
thuật ngữ vay mượn từ di truyền học như: cá thể, nhiễm sắc thể (NST), gen, quẩn thể,

thể trạng, chọn lọc, lai, đột biến, v.v… Trong số đó, một cá thể (cá thể, kiểu gen, cẩu
trúc) đại diện cho một giải pháp để giải quyết vấn đề. Không giống như trong tự
nhiên, một cá thể có thể có nhiều NST, thì ở đây mỗi cá thể chỉ có một NST. NST có
thể là một chuỗi tuyến tính và có thể có các đơn vị gen nhỏ hơn trong NST. Mỗi gen


10

đại diện cho một thuộc tính, một tính trạng và có một vị trí nhất định trong NST. Một
quần thể là một nhóm giới hạn của các cá thể.
Cụ thể, một tập hợp các biến cho một vấn đề nhất định được mã hóa thành chuỗi
(hoặc cấu trúc mã hóa khác) tương tự như NST trong tự nhiên. Mỗi trình tự chứa một
giải pháp khả thi cho vấn đề. Thuật toán di truyền sử dụng các toán tử được tạo ra bởi
sự chọn lọc tự nhiên của một tập hợp các chuỗi nhị phân (hoặc cấu trúc khác) để mã
hóa khoảng tham số của mỗi thế hệ, kiểm tra các phạm vi khác nhau của không gian
tham số và hướng tìm kiếm đến khoảng có xác suất cao để tìm hiệu suất tốt hơn.
Thuật tốn di truyền gồm có bốn quy luật cơ bản là lai ghép, đột biến, sinh sản và
chọn lọc tự nhiên cụ thể như sau:
Quá trình lai ghép (phép lai) là quá trình diễn ra bằng cách ghép một hay nhiều
đoạn gen từ hai NST cha mẹ để hình thành NST mới mang đặc tính cả cha lẫn mẹ.
Phép lai này được mô tả: Chọn ngẫu nhiên hai hay nhiều cá thể trong quần thể. Giả
sử chuỗi NST của cha và mẹ đều có chiều dài là m. Tìm điểm lai bằng cách tạo ngẫu
nhiên một con số từ 1 đến m-1. Như vậy, điểm lai này sẽ chia hai chuỗi NST cha mẹ
thành hai nhóm NST con là m1 và m2. Hai chuỗi NST con lúc này sẽ là m11+m22
và m21+m12. Đưa hai chuỗi NST con vào quần thể để tiếp tục tham gia quá trình tiến
hóa.


11


Hình 2.1 Mơ tả các bước tiến hành của giải thuật di truyền
Quá trình đột biến (phép đột biến) là q trình tiến hóa xảy ra trường hợp một
hoặc một số tính trạng của con khơng được thừa hưởng từ hai chuỗi NST cha mẹ.
Phép đột biến xảy ra với xác suất thấp hơn rất nhiều so với xác suất xảy ra phép lai.
Phép đột biến được mô tả:
-

Chọn ngẫu nhiên một số k từ khoảng 1 ≥ k ≥ m

-

Thay đổi giá trị của gen thứ k

-

Đưa NST con vào quần thể để tham gia q trình tiến hóa tiếp theo
Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn)

-

Phép tái sinh là quá trình các cá thể được sao chép dựa trên độ thích nghi của
nó. Độ thích nghi là một hàm được gán các giá trị thực cho các cá thể trong
quần thể của nó. Phép tái sinh có thể được mơ phỏng như sau:

+ Tính độ thích nghi của từng cá thể trong quần thể, lập bảng cộng đồn các giá trị
thích nghi đó (theo giá trị gán cho từng cá thể) ta được tổng độ thích nghi. Giả sử


12


quần thể có n cá thể. Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i là Ft.
Tổng độ thích nghi là Fm. Tạo số ngẫu nhiên F có giá trị trong đoạn 0 đến Fm.
+ Chọn cá thể k đầu tiên thỏa mãn F ≥ Ft đưa vào quần thể của thế hệ mới
-

Phép chọn là quá trình loại bỏ các cá thể xấu và để lại những cá thể tốt. Phép
chọn được mô tả như sau

+ Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần
+ Loại bỏ các cá thể cuối dãy, chỉ để lại n cá thể tốt nhất

Hình 2.2 Sự lựa chọn cá thể tốt nhất của quá trình đột biến
GAs cũng như các thuật tốn tiến hố, đều được hình thành dựa trên một quan
niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm "Q
trình tiến hố tự nhiên là q trình hồn hảo nhất, hợp lý nhất và tự nó đã mang tính
tối ưu". Những cá thể có khả năng thích ứng với mơi trường mạnh có khả năng tồn
tại, phát triển và sinh sản cao hơn, trong khi những cá thể có khả năng thích nghi thấp
có nguy cơ tử vong cao hơn hoặc tăng trưởng chậm. Sự thích nghi này được giữ lại
trong cấu trúc NST của chúng. Do đó, q trình tiến hố thể hiện tính tối ưu ở chỗ thế
hệ sau bao giờ cũng tốt hơn thế hệ trước.


13

Ngày nay, GAs càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu hố, một
lĩnh vực có nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng thường
khó và chưa có phương pháp hiệu quả để giải quyết.
2.1.2.2 Các tính chất của giải thuật di truyền
GAs là kỹ thuật chung, giúp giải quyết vấn đề bằng cách mơ phỏng sự tiến hóa
của con người hay của sinh vật nói chung (dựa trên thuyết tiến hóa mn lồi của

Darwin), trong điều kiện qui định sẵn của môi trường. Mục tiêu của GAs không nhằm
đưa ra lời giải chính xác tối ưu mà là đưa ra lời giải tương đối tối ưu.
Một cá thể trong GAs sẽ biểu diễn một giải pháp của bài toán. Tuy nhiên, không
giống với trong tự nhiên là một cá thể có nhiều nhiễm sắc thể (NST) mà để giới hạn
trong GAs, ta quan niệm một cá thể có một NST. Do đó, khái niệm cá thể và NST
trong GAs coi như là tương đương.
Một NST được tạo thành từ nhiều gen, mỗi gen có thể có các giá trị khác nhau để
quy định một tình trạng nào đó. Trong GAs, một gen được coi như một phần tử trong
chuỗi NST.
Một tập hợp các cá thể có cùng một số đặc điểm nào đấy được gọi là quần thể.
Trong thuật giải di truyền, ta quan niệm quần thể là một tập các lời giải của một bài
toán.
2.1.2.3 Các bước cơ bản của giải thuật di truyền
Các bước cơ bản của giải thuật di truyền được thể hiện tại Hình 2.1