Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu bài toán lập lịch và ứng dụng xếp thời khóa biểu cho trường phổ thông vùng cao Việt Bắc

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

HOÀNG PHÚC LỢI

NGHIÊN CỨU BÀI TOÁN LẬP LỊCH VÀ

ỨNG DỤNG XẾP THỜI KHÓA BIỂU CHO

TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2017

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

HOÀNG PHÚC LỢI

NGHIÊN CỨU BÀI TOÁN LẬP LỊCH VÀ

ỨNG DỤNG XẾP THỜI KHÓA BIỂU CHO

TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: TS. TRƢƠNG HÀ HẢI

Thái Nguyên - 2017

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng cá

nhân tôi, không sao chép của ai, do tôi tự nghiên cứu, đọc, dịch tài liệu,

tổng hợp và thực hiện. Nội dung lý thuyết trong trong luận văn tôi có sử

dụng một số tài liệu tham khảo nhƣ đã trình bày trong phần tài liệu tham khảo.

Các số liệu, chƣơng trình phần mềm và những kết quả trong luận văn là trung

thực và chƣa đƣợc công bố trong bất kỳ một công trình nào khác.

Thái nguyên 19 tháng 06 năm 2017

Học viên thực hiện

Hoàng Phúc Lợi

LỜI CẢM ƠN

Lời đầu tiên, em xin gửi lời biết ơn sâu sắc đến TS. Trƣơng Hà Hải

ngƣời đã tận tình hƣớng dẫn, chỉ bảo, giúp đỡ em trong suốt quá trình

làm luận văn.

Em cũng xin gửi lời cảm ơn đến các thầy giáo, cô giáo trƣờng Đại học

Công Nghệ Thông Tin và Truyền Thông Thái Nguyên, các thầy giáo, cô giáo

Viện Công nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ em trong

suốt quá trình học của mình.

Và cuối cùng tôi xin gửi lời cảm ơn tới các đồng nghiệp, gia đình và

bạn bè những ngƣời đã ủng hộ, động viên tạo mọi điều kiện giúp đỡ để

tôi có đƣợc kết quả nhƣ ngày hôm nay.

Thái Nguyên 19, tháng 06 năm 2017

Học Viên

Hoàng Phúc Lợi

iii

MỤC LỤC

LỜI CAM ĐOAN .......................................................................................... i

LỜI CẢM ƠN ............................................................................................... ii

MỤC LỤC .................................................................................................... iii

DANH MỤC HÌNH ẢNH ............................................................................ v

DANH MỤC BẢNG BIỂU ......................................................................... vi

MỞ ĐẦU ....................................................................................................... 1

CHƢƠNG 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH ........................... 4

1.1. Giới thiệu chung về bài toán lập lịch ................................................. 4

1.2. Các đặc trƣng của bài toán lập lịch .................................................... 4

1.3. Một số ví dụ về bài toán lập lịch: ....................................................... 5

1.4. Bài toán xếp thời khóa biểu ở trƣờng phổ thông ............................... 7

1.4.1. Giới thiệu bài toán xếp thời khóa biểu ........................................ 7

1.4.2. Độ phức tạp của bài toán xếp thời khóa biểu .............................. 9

1.4.3. Phân loại mô hình xếp thời khóa biểu ....................................... 10

1.4.4. Các đặc thù của thời khóa biểu hệ trung học phổ thông ........... 12

1.4.5. Nhu cầu bài toán xếp thời khóa biểu ......................................... 14

CHƢƠNG 2: MỘT SỐ HƢỚNG TIẾP CẬN VÀ THUẬT TOÁN GIẢI

BÀI TOÁN XẾP THỜI KHÓA BIỂU. ....................................................... 17

2.1. Đề xuất các giải thuật giải bài toán .................................................. 17

2.1.1. Giải thuật vét cạn. ..................................................................... 17

2.1.2. Giải thuật chia để trị .................................................................. 17

2.1.3. Giải thuật Heuristic: .................................................................. 19

2.2. Đánh giá các phƣơng pháp: .............................................................. 20

2.3. Giới thiệu giải thuật tối ƣu hóa đàn kiến (ANT COLONY

OPTIMIZATION: ACO) ........................................................................ 22

2.4. Mô tả giải thuật tối ƣu hóa đàn kiến ................................................ 24

2.4.1. Trình bày giải thuật ................................................................... 24

2.4.2. Một số vấn đề liên quan ............................................................ 29

CHƢƠNG 3: XÂY DỰNG CHƢƠNG TRÌNH XẾP THỜI KHÓA BIỂU

CHO TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC ......................... 32

3.1. Phân tích quy trình thực hiện bài toán ............................................. 32

3.1.1. Phát biểu bài toán ...................................................................... 32

3.1.2. Bài toán xếp thời khóa biểu trong mô hình tổng thể ................. 33

3.1.3. Đặc điểm công tác, kế hoạch đào tạo ........................................ 33

3.1.4. Quy trình xây dựng kế hoạch đào tạo thời khóa biểu ............... 34

3.2. Sơ đồ xây dựng chƣơng trình xếp thời khóa biểu ............................ 35

3.2.1. Xây dựng hệ thống .................................................................... 39

3.2.2. Đánh giá khả năng ứng dụng giải quyết bài toán xếp thời khóa biểu 42

3.4. Thiết kế chƣơng trình. ...................................................................... 44

3.4.1. Lớp học ..................................................................................... 49

3.4.2. Giáo viên ................................................................................... 50

3.4.3. Phòng học .................................................................................. 50

3.4.4. Nhân viên phòng đào tạo .......................................................... 50

3.4.5 Mô hình ca sử dụng .................................................................... 50

3.5. Các chức năng chính của chƣơng trình ............................................ 51

3.5.1. Chức năng đăng nhập ( chức năng quản lý user ) ..................... 51

3.5.2. Chức năng Quản lý môn học ..................................................... 52

3.5.3. Chức năng Quản lý giáo viên .................................................... 55

3.5.4. Chức năng Quản lý học sinh: .................................................... 58

3.5.5. Chức năng Quản lý lớp học ...................................................... 60

3.6. Kết quả thử nghiệm .......................................................................... 62

ẾT UẬN ................................................................................................. 64

HƢỚNG PHÁT TRIỂN .............................................................................. 65

TÀI LIỆU THAM KHẢO ........................................................................... 66

DANH MỤC HÌNH ẢNH

Hình 2.1: Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm .. 26

Hình 2.2: Lựa chọn đỉnh đi tiếp theo .......................................................... 27

Hình 2.3: Đặc tả thuật toán ACO ................................................................ 28

Hình 3.1: Sơ đồ xây dựng chƣơng trình T B ................................................. 35

Hình 3.2: Chức năng của hệ thống .............................................................. 40

Hình 3.3 Mô hình cơ sở dữ liệu .................................................................. 48

Hình 3.4: Mô hình các ca sử dụng .............................................................. 50

Hình 3.5: Giao diện của chƣơng trình ......................................................... 51

Hình 3.6: Giao diện đăng nhập ................................................................... 52

Hình 3.7: Mô hình chức năng quản lý môn học.......................................... 53

Hình 3.8: Giao diện thêm môn học ............................................................. 54

Hình 3.9:Giao diện chỉnh sửa môn ............................................................. 54

Hình 3.10: Mô hình chức năng quản lý giáo viên ....................................... 55

Hình 3.11:Giao diện thêm giáo viên ........................................................... 56

Hình 3.12:Giao diện chỉnh sửa .................................................................... 56

Hình 3.13:Giao diện thời khóa biểu của từng giáo viên ............................. 57

Hình 3.14: Chức năng Quản lý học sinh ..................................................... 58

Hình 3.15:Cập nhật thông tin học sinh ....................................................... 59

Hình 3.16: Cập nhật lại thông tin học sinh ................................................. 59

Hình 3.17: Mô hình chức năng quản lý lớp học ......................................... 60

Hình 3.18: Giao diện môn học .................................................................... 61

Hình 3.19: Kết quả xếp thời khóa biểu theo lớp ........................................ 61

Hình 3.20: Cập nhật thông tin lớp ............................................................... 62

DANH MỤC BẢNG BIỂU

Bảng 3.1. Ví dụ về TKB của một lớp ......................................................... 36

Bảng 3.2. Ma trận TKB mà kiến xây dựng ................................................. 38

Bảng 3.3. Bảng dữ liệu phân công giảng dạy theo khối ............................. 41

Bảng 3.4. Bảng dữ liệu phân công giảng dạy theo lớp ............................... 41

Bảng 3.5. Bảng dữ liệu phân công giảng dạy theo giáo viên ...................... 42

MỞ ĐẦU

1. Lý do chọn đề tài

Lập lịch biểu là công việc không thể thiếu ở bất kì tổ chức nào hoạt

động trong xã hội hiện nay. Cùng với tiến bộ xã hội, khoa học máy tính đã

có những bƣớc tiến dài, đem lại sự tiện lợi và hiệu quả kinh tế cao trong rất

nhiều lĩnh vực từ công nghiệp cho đến đời sống. Với việc sử dụng máy tính

trong lập lịch, con ngƣời có thể xây dựng đƣợc lịch biểu một cách nhanh

chóng và tối ƣu hơn. Nhiều phần mềm máy tính có chức năng hỗ trợ lập lịch

nhƣ MS.Excel, MS.Project,… nhƣng sự “thiếu thông minh” của chúng vẫn làm

cho con ngƣời phải tiêu tốn nhiều thời gian cũng nhƣ công sức khi lập lịch. Nhu

cầu cần có phần mềm lập lịch thông minh đã trở thành bức thiết.

Tại các trƣờng học, thời khóa biểu kết nối hầu nhƣ toàn bộ các hoạt

động của nhà trƣờng. Trƣớc đây công việc xếp thời khóa biểu chủ yếu

đƣợc làm bằng tay bởi các cán bộ có kinh nghiệm, nắm vững chuyên môn

nghiệp vụ. Do đó việc xây dựng thời khóa biểu phụ thuộc rất lớn vào ngƣời

lập lịch, đồng thời hiệu quả tối ƣu cũng còn bị hạn chế.Vì thế bài toán lập

thời khóa biểu luôn là một trong những vấn đề quan trọng cần giải quyết.

Hiện nay, hầu hết các trƣờng học đã đầu tƣ xây dựng phần mềm xếp

thời khóa biểu, mang lại hiệu quả nhất định trong việc xây dựng lịch biểu

học tập và làm việc. Đối với các trƣờng Trung học phổ thông thì việc ứng

công nghệ thông tin vào xếp thời khóa biểu là rất hạn chế, cụ thể là trƣờng

Phổ thông Vùng cao Việt Bắc. Vì vậy ứng dụng xây dựng thời khóa biểu

cho trƣờng Phổ thông Vùng cao Việt Bắc là nhu cầu cần thiết. Xuất phát từ

nhu cầu đó, em đã lựa chọn đề tài “Nghiên cứu bài toán lập lịch và ứng

dụng xếp thời khóa biểu cho trƣờng Phổ Thông Vùng Cao Việt Bắc”

làm luận văn tốt nghiệp thạc sỹ.

Luận văn nghiên cứu về mô hình bài toán cũng nhƣ quy trình, độ phức tạp

của vấn đề xếp thời khóa biểu nói chung và giải quyết bài toán xếp thời khóa

biểu chính khóa cho các trƣờng Phổ Thông Trung Học nói chung và trƣờng

Phổ Thông Vùng Cao Việt Bắc nói riêng. Sử dụng giải thuật tối ƣu hóa đàn

kiến tự động cập nhật thời khóa biểu và đƣa ra phƣơng án khả thi cho bài

toán xếp thời khóa biểu.

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

Đối tƣợng: Nghiên cứu tổng quan bài toán lập lịch và một số thuật

toán giải bài toán lập lịch.

Phạm vi nghiên cứu: uận văn tập trung nghiên cứu các kiến thức

có liên quan, các cơ sở lý thuyết nhƣ: Bài toán lập lịch. Một số thuật toán

giải bài toán lập lịch và ứng dụng vào bài toán xếp thời khóa biểu.

3. Mục tiêu và nhiệm vụ

- Mục tiêu

Hoàn thành sản phẩm là phần mềm xếp thời khóa biểu cho trƣờng Phổ

thông Vùng cao Việt Bắc.

Tiếp tục phát triển các phần mêm xếp thời khóa biểu cho các trƣờng

Phổ thông trung học trên toàn quốc.

- Nhiêm vụ

Phân tích các số liệu, đề ra giải pháp hợp lý trong việc xây dựng và

phát triển hệ thống.

Nghiên cứu các giải thuật, áp dụng thuật toán tối ƣu hóa đàn kiến giải

quyết bài toán xếp thời khóa biểu cho trƣờng Phổ thông Vùng cao Việt Bắc.

Phân tích, đánh giá, đề ra các phƣơng pháp xếp thời khóa biểu một

cách tự dộng và chính xác.

4. Phƣơng pháp nghiên cứu

- Phƣơng pháp nghiên cứu lý thuyết.

- Phƣơng pháp nghiên cứu tài liệu.

- Phƣơng pháp quan sát.

- Phƣơng pháp phân tích và tổng hợp lý thuyết.

- Phƣơng pháp nghiên cứu thực nghiệm.

- Phân tích thuật toán đã lựa chọn, xây dựng cấu trúc dữ liệu và cài

đặt chƣơng trình.

- Tạo các mẫu thử có chất lƣợng để kiểm nghiệm các tính chất của

thuật toán, kiểm chúng sự thỏa mãn yêu cầu đặt ra của bài toán.

Thực nghiệm:

Xây dựng chƣơng trình thời khóa biểu, tích hợp cơ sở dữ liệu với

phòng Giáo vụ, tổng hợp lại hệ thống để đƣa ra thời khóa biểu trên

Website của trƣờng.

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

Ngoài phần mở đầu và kết luận, bố cục của luận văn đƣợc tổ chức

thành 3 chƣơng, gồm:

Chương 1: Tổng quan về bài toán lập lịch

Giới thiệu về bài toán lập lịch, những đặc trƣng cơ bản và hƣớng tiếp cận

nghiên cứu, bài toán xếp thời khóa biểu ở trƣờng phổ thông. Giới thiệu nghiên

cứu một dạng cụ thể của bài toán lập lịch là bài toán xếp thời khóa biểu.

Chương 2: Một số hướng tiếp cận và thuật toán giải bài toán xếp thời

khoá biểu

Tìm hiểu về một số giải thuật giải bài toán, đánh giá các giải thuật và

đề xuất giải thuật giải bài toán.

Chương 3: Thiết kế chương trình xếp thời khóa biểu chính khóa trường

Phổ Thông Vùng Việt Bắc

Phân tích thiết kế hệ thống, áp dụng giải thuật tối ƣu hóa đàn kiến,

đánh giá khả năng ứng dụng để giải quyết bài toán thời khóa biểu.

Các bƣớc thực hiện: thiết kế dữ liệu, ý tƣởng thuật toán, xây dựng

chƣơng trình, nhận xét.

CHƢƠNG 1:

TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH

1.1. Giới thiệu chung về bài toán lập lịch

Bài toán cần xác định trình tự thời gian thực hiện các công việc trong

điều kiện ràng buộc về tài nguyên cần thiết sử dụng để thực hiện các công

việc bài toán đó đƣợc phân loại là Bài toán lập lịch.

- Lập lịch có thể đƣợc định nghĩa là một bài toán tìm kiếm chuỗi tối

ƣu để thực hiện một tập các hoạt động chịu tác động của một tập các ràng

buộc cần phải đƣợc thỏa mãn. Ngƣời lập lịch thƣờng cố gắng thử đến mức

tối đa sự sử dụng các cá thể, máy móc và tối thiểu thời gian đòi hỏi để

hoàn thành toàn bộ quá trình nhằm sắp xếp lịch. Vì thế bài toán lập lịch là

một vấn đề rất khó để giải quyết. Hiện nay có nhiều khả năng để phát

triển các kỹ thuật hiện tại để giải quyết bài toán này. Những kỹ thuật đó

bao gồm: Các tiếp cận Trí tuệ nhân tạo nhƣ hệ thống tri thức cơ sở

(knowledge-based systems), bài toán thoả mãn ràng buộc, hệ chuyên gia,

mạng Nơron và các tiếp cận của các nghiên cứu hoạt động: lập trình tính

toán, lập trình động, tìm kiếm nhánh và đƣờng biên, kỹ thuật mô phỏng,

tìm kiếm Tabu và phƣơng pháp nút cổ chai

1.2. Các đặc trƣng của bài toán lập lịch

Khi nghiên cứu về bài toán lập lịch cần làm rõ các đặc trƣng cơ bản

của bài toán. Các đặc trƣng cơ bản đó bao gồm: Tập công việc, tài nguyên,

tác vụ, ràng buộc và mục tiêu.

- Tập công việc: Mô tả tính chất công việc (lập danh sách môn học,

lập danh sách giáo viên, lập danh sách phòng học, lập bảng thông tin môn

học.....)

- Tài nguyên: Là các dữ liệu đầu vào để giải quyết bài. Các tài nguyên

này có thể phục hồi hoặc không.

- Thời gian giới hạn: Mô tả các dạng thời gian (trình tự, thời điểm,

khoảng thời gian – ca học – tiết học,....)

- Ràng buộc: Đây là những điều kiện cần thỏa mãn để bài toán có thể

đƣa đƣợc lời giải tốt nhất.

- Mục tiêu: Đánh giá độ tối ƣu của lịch trình lời giải của bài toán. Khi

các mục tiêu đƣợc thỏa mãn thì các ràng buộc cũng đƣợc thỏa mãn.

Đánh giá độ phức tạp của bài toán lập lịch: vấn đề ràng buộc tài

nguyên trong bài toán lập lịch rất đa dạng và phức tạp. Thông thƣờng các

vấn đề liên quan đến ràng buộc về tài nguyên trong bài toán lập lịch thƣờng

xảy ra trong tình huống lƣợng tài nguyên là khan hiếm, hạn chế. Nhƣ vậy

đặc trƣng công việc đối với vấn đề tài nguyên đó là lƣợng thời gian hoàn

thành công việc, yêu cầu phân bổ tài nguyên cho công việc. Các công việc

có thể đƣợc thực hiện theo một số phƣơng pháp khác nhau nhƣng có điểm

chung đó là đƣợc xác định bởi một quy tắc ràng buộc, các công việc đƣợc

thực hiện theo dây chuyền, một số công việc chỉ đƣợc thực hiện sau khi đã

thực hiện xong một số công việc khác.

1.3. Một số ví dụ về bài toán lập lịch:

a. Bài toán lập lịch cho 2 máy:

Xét mỗi một chi tiết phải đƣợc lần lƣợt gia công trên 2

máy A, B. Thời gian gia công chi tiết trên máy A là trên máy B là

(i=1,2,...,N). Hãy tìm lịch trình tự gia công) các chi tiết trên hai

máy sao cho việc hoàn thành gia công tất cả các chi tiết là sớm nhất.

Thuật toán Johnson:

Chia các chi tiết thành 2 nhóm: nhóm gồm các chi tiết thoả mãn

< , tức là và nhóm gồm các chi tiết thoả mãn

tức là . Các chi tiết thoả mãn xếp vào

nhóm nào cũng đƣợc. Sắp xếp các chi tiết trong theo chiều tăng của các

và sắp xếp các chi tiết trong theo chiều giảm của các nối vào

đuôi , dãy thu đƣợc đọc từ trái sang phải) sẽ là lịch gia công.

b. Bài toán lập lịch cho 3 máy:

Xét bài toán gia công N chi tiết trên 3 máy theo thứ tự A,B,C với bảng

thời gian (i=1,2,..N) thoả mãn: hoặc

Thuật toán: Lịch gia công tối ƣu trên 3 máy sẽ trùng với lịch gia công

tối ƣu trên 2 máy: máy thứ nhất với thời gian và máy thứ hai với

thời gian .

Thuật toán More

Có n ôtô đƣa vào xƣởng sửa chữa đƣợc đánh số thứ tự 1,2..,n. Ôtô

phải sửa chữa trong thời gian và thời điểm phải bàn giao là . Mỗi thời

điểm xƣởng chỉ sửa chữa một cái, xƣởng sửa chữa không ngừng và thời

điểm bắt đầu sửa chữa là 0. Hãy đƣa ra một thứ tự sửa chữa sao cho số

lƣợng ôtô đúng hạn là lớn nhất. Sắp xếp theo thứ tự tăng dần của thời điểm

bàn giao. Duyệt từ đầu cho đến khi gặp ôtô quá hạn đầu tiên (Giả sử là ôtô

thứ k).

Tìm từ đầu cho đến ôtô thứ k, ôtô nào có lớn nhất (Giả sử đó là ôtô

thứ m). Nếu ôtô này đã đƣợc chuyển một lần rồi thì dừng chƣơng trình, còn

nếu không thì ta chuyển ôtô này xuống cuối. Rồi trở lại bƣớc 2.

Bài toán lập lịch là dạng bài toán quan trọng đƣợc nghiên cứu trong

các môi trƣờng tính toán. Quá trình lập lịch là quá trình quyết định sẽ thực

thi công việc tại một nguồn tài nguyên cụ thể nào và vào thời điểm nào là

thích hợp nhất bởi công việc đó sẽ ảnh hƣởng rất lớn đến hiệu năng hoạt

động của hệ thống. Nhu cầu cần sử dụng bài toán lập lịch là rất lớn trên

thực tế. Hầu nhƣ mọi lĩnh vực liên quan đến quản lý, điều hành đều phải sử

dụng đến bài toán lập lịch.

Hiện nay có nhiều phƣơng pháp nghiên cứu, phát triển để giải quyết

bài toán này. Những kỹ thuật đó bao gồm:

- Các tiếp cận trí tuệ nhân tạo nhƣ: Hệ thống cơ sở tri thức

(knowledgebased systems), bài toán thoả mãn ràng buộc, hệ chuyên gia,

mạng Neural, tìm kiếm, tìm kiếm chọn lọc, thuật toán Heuristic, thuật toán

tô màu đồ thị, thuật toán luồng…

- Các tiếp cận dựa trên những nghiên cứu hoạt động: Lập trình tính

toán, lập trình động, tìm kiếm nhánh và đƣờng biên, kỹ thuật mô phỏng,

tìm kiếm Tabu search, phƣơng pháp nút cổ chai...

Bài toán lập lịch có rất nhiều ứng dụng trong thực tế nhƣ: Bài toán lập

lịch xếp thời khóa biểu cho các trƣờng đại học, cao đẳng, các trƣờng phổ

thông…, lập lịch phân công công tác cho một công ty, doanh nghiệp, lập

lịch cho hệ thống tính toán lƣới trắc địa, lập lịch cho bộ xử lý CPU…

1.4. Bài toán xếp thời khóa biểu ở trƣờng phổ thông

1.4.1. Giới thiệu bài toán xếp thời khóa biểu

Trong một cơ quan, một tổ chức, một trƣờng học công việc quản lý và

sắp xếp công việc cho các cá nhân, các nhóm trong từng giai đoạn và thời

điểm cũng nhƣ địa điểm một cách hợp lý và khoa học là hết sức cần thiết

và cấp bách. Công việc đó dựa trên các bài toán lập lịch và việc tìm lời giải

tối ƣu cho các bài toán này vẫn là hƣớng nghiên cứu mà rất nhiều cá nhân,

tổ chức hƣớng tới và cũng có nhiều công trình nghiên cứu về vấn đề này.

Trong phạm vi một trƣờng học cũng có nhiều bài toán lập lịch, trong

đó tiêu biểu là bài toán xếp thời khóa biểu. Bài toán này nhằm sắp xếp lịch

hoạt động giảng dạy và học tập của giáo viên và học sinh.

Sau đây chúng ta đi tìm hiểu bài toán lập thời khóa biểu chính khóa,

theo tuần, theo học kỳ, theo năm học của trƣờng Phổ thông trung học:

- Bƣớc 1: Lập kế hoạch đào tạo (dựa vào khung chƣơng trình đào tạo

của Nhà trƣờng theo các qui định của Ngành giáo dục).

- Bƣớc 2: Lập kế hoạch đào tạo theo tuần, theo học kỳ.

- Bƣớc 3: Xây dựng bảng phân công giáo viên.

- Bƣớc 4: Xây dựng bảng phân công từng lớp, từng khối.

- Bƣớc 5: Xây dựng thời khóa biểu.

- Bƣớc 6: Hoàn chỉnh thời khóa biểu tổng thể cho giáo viên, lớp học.

Bài toán xếp thời khóa biểu trong các nhà trƣờng là bài toán cần phải

thỏa mãn những ràng buộc hết sức phức tạp và nhiều khi là mâu thuẫn của

các đối tƣợng. Việc đƣa ra một bảng thời khóa biểu hợp lý không những

làm mất nhiều thời gian và công sức của ngƣời lập lịch mà đôi khi còn gây

ra mâu thuẫn nhƣ thỏa mãn nhu cầu của ngƣời hay nhóm ngƣời này lại

phạm vào nhu cầu của ngƣời hay nhóm ngƣời khác.

Vấn đề xây dựng thời khóa biểu tự động hoặc bán tự động cho các loại

công việc khác nhau bao gồm cả các hoạt động dạy và học trong một trƣờng

học là một vấn đề cấp thiết đã thu hút nhiều sự chú ý trong cả hai lĩnh vực

nghiên cứu và ứng dụng. Tuy nhiên kết quả nghiên cứu đạt đƣợc trong lĩnh vực

này vẫn chƣa đƣợc ứng dụng rộng rãi bởi các nguyên nhân sau:

- Về mặt học thuật, bài toán xếp thời khóa biểu tự động là một bài toán có

độ phức tạp giải thuật rất cao. Chƣa có giải thuật xếp thời khóa biểu một cách

tổng quát.

- Khi áp dụng vào các trƣờng học, mỗi trƣờng có mô hình đào tạo, đặc

thù khác nhau dẫn đến các mối quan hệ ràng buộc khác nhau. Việc đƣa ra

một mô hình biểu diễn đặc trƣng tổng quát cho tất cả các mối quan hệ ràng

buộc này là rất khó.

- Bài toán thời khóa biểu là mô hình quan hệ ràng buộc giữa các đối

tƣợng liên quan trực tiếp đến thời khóa biểu bao gồm giáo viên ngƣời

dạy), học sinh ngƣời học), môn học hay học phần (nội dung dạy và học),

phòng học địa điểm) và cuối cùng là dạy, học nội dung gì, học ở đâu, diễn

ra ở thời điểm nào. Các đối tƣợng trên quyết định đến mô hình chung của

bài toán xếp thời khóa biểu do những đặc thù riêng biệt của chúng.

Bài toán đặt ra bao gồm tất cả các vấn đề có liên quan đến việc xếp

thời khóa biểu ở một trƣờng học. Chẳng hạn nhƣ đặt số học sinh vào một

phòng sao cho tƣơng ứng về sức chứa của nó, tránh việc học trùng giờ tại

một phòng của các lớp chuyên ngành, giáo viên sẽ dạy theo giờ quy định

trong bảng phân công hay đăng ký giảng dạy. Thông thƣờng, công việc này

có thể đƣợc làm bằng tay, nhƣng phải mất nhiều thời gian và phải có kinh

nghiệm xếp lịch nếu không muốn xảy ra sai sót, chẳng hạn nhƣ: chỗ này

thừa phòng, chỗ khác lại thiếu, sai giờ, sai chỗ… vấn đề của bài toán là

ngoài việc thực hiện đúng, chính xác, còn phải tốt hơn, nhanh hơn và hiệu

quả hơn công việc xếp lịch bằng tay mà chúng ta vẫn làm.

1.4.2. Độ phức tạp của bài toán xếp thời khóa biểu

Khi nhắc đến bài toán xếp thời khóa biểu, hầu hết tất cả những ai quan

tâm đến bài toán này đều quan tâm đến độ phức tạp của nó.

Bài toán xếp thời khóa biểu trong các nhà trƣờng là bài toán cần phải

thỏa mãn những ràng buộc hết sức phức tạp và nhiều khi là mâu thuẫn của

các đối tƣợng.

"Độ phức tạp " của bài toán đã trở nên nổi tiếng không chỉ bởi độ khó

của nó, mà còn ở tính thực tiễn, khả năng áp dụng rất cao vào thực tế. Tại tất

cả các trƣờng học, thời khóa biểu học tập của học sinh, giảng dạy của giáo

viên là quyết định hoạt động chính của nhà trƣờng, chính vì vậy xếp thời khóa

biểu đã trở thành vấn đề chính và quan trọng trong mỗi nhà trƣờng.

Việc xếp thời khóa biểu thực sự là một công việc rất khó và mất rất

nhiều thời gian. Xếp thời khóa biểu thể hiện cái khó ở các lý do sau:

- Thứ nhất: Việc xếp thời khóa biểu đòi hỏi tƣ duy, tính toán, suy luận

rất phức tạp, dễ xảy ra nhầm lẫn nhƣ: trùng giờ trùng tiết, thiếu giờ thiếu

tiết,... Nhƣ vậy, việc xếp thời khóa biểu đòi hỏi ngƣời phải có nhiều kinh

nghiệm và hiểu biết về công việc này mới có thể làm đƣợc.

- Thứ hai: Các ràng buộc của giáo viên trong trƣờng rất mâu thuẫn,

chồng chéo lẫn nhau.

- Thứ ba: Công việc xếp thời khóa biểu đòi hỏi phải có tƣ duy đặc

biệt. Ngƣời xếp thời khóa biểu, ngoài việc phải am hiểu về các môn học

cũng nhƣ quy định của Bộ Giáo Dục và Đào Tạo đối với nhà trƣờng về

chƣơng trình môn học, hiểu rõ yêu cầu cầu của các giáo viên trong nhà

trƣờng, phải có tƣ duy nghề nghiệp của công việc xếp thời khóa biểu.

Mỗi trƣờng lại có một đặc thù riêng về công tác đào tạo, số lƣợng giáo

viên, lớp học, phòng học. Do vậy việp xếp thời khóa biểu của các trƣờng

hoàn toàn khác nhau, không thể áp dụng chung cho các trƣờng. Hiện nay cả

nƣớc ta có khoảng 25,000 trƣờng học với các cấp bậc đào tạo khác nhau

nhƣ: cấp Tiểu học, Trung học cơ sở, Phổ thông trung học.

Những điều trên đã khiến cho bài toán xếp thời khóa biểu càng trở nên

phức tạp hơn.

1.4.3. Phân loại mô hình xếp thời khóa biểu

a. Phân loại theo khuôn dạng thời gian thời khóa biểu

Phân loại theo mẫu biểu của thời khóa biểu đƣợc in ra. Trên thực tế có rất

nhiều dạng thời khóa biểu khác nhau, rất đa dạng và tuỳ thuộc vào hoàn cảnh,

điều kiện của từng trƣờng. Có thể liệt kê ra đây một vài kiểu (mẫu) thời khóa

biểu nhƣ sau:

+ Thời khóa biểu TUẦN:

Là mẫu dạng thời khóa biểu cho một tuần và đƣợc dùng làm chuẩn

cho tất cả các tuần của học kỳ hoặc năm học. Đa số các nhà trƣờng của

Việt Nam đều sử dụng khuôn mẫu này.

+ Thời khóa biểu HỌC KỲ:

Là mẫu khuôn dạng thời khóa biểu đƣợc biểu diễn chi tiết đến từng

ngày trong suốt một học kỳ hoặc năm học. Một số các trƣờng đại học, cao

đẳng tại Việt Nam, đặc biệt là các trƣờng quân đội sử dụng khuôn dạng này

của thời khóa biểu.

+ Thời khóa biểu cho mỗi TUẦN:

Là loại thời khóa biểu mô hình tuần nhƣng mỗi tuần lại có một Thời

khóa biểu riêng. Nhƣ vậy ví dụ trong một học kỳ có 25 tuần thì mỗi lớp học

sẽ có đúng 25 thời khóa biểu. Đây là mô hình rất phức tạp và về bản chất

chính là mô hình Thời khóa biểu Học kỳ (loại B), điểm khác duy nhất là

khuôn dạng in ra của thời khóa biểu là TUẦN.

b. Phân loại theo đối tượng xếp thời khóa biểu

Phân loại theo các đối tƣợng trực tiếp liên quan đến dữ liệu bài toán

xếp thời khóa biểu, đó là các đối tƣợng chính bao gồm: giáo viên, học sinh,

học phần (môn học), phòng học.

+ Giáo viên: à ngƣời trực tiếp giảng dạy theo các học phần, môn

học đƣợc quy định chặt chẽ về thời lƣợng, kiến thức và hình thức học.

+ Học sinh: Đối tƣợng học tập trực tiếp của giáo viên giảng dạy. Học

sinh tham gia học tập ở các lớp học.

+ Môn học: Là nội dung các bài giảng của giáo viên và nội dung mà

học sinh học tập, mỗi môn học có đặc trƣng riêng để phân biệt với các môn

học khác.

+ Phòng học: à địa điểm tổ chức các môn học, học phần và bài

giảng do giáo viên đảm nhiệm.

Chính việc phân loại theo khuôn dạng thời gian và phân loại theo đối

tƣợng đã tạo ra sự khác biệt cơ bản của mô hình thời khóa biểu.

c. Yêu cầu đối với các mô hình xếp thời khóa biểu

- Các đối tƣợng chính cần quan tâm là lớp học, giáo viên, phòng học,

môn học.

- Các mô hình đều có các ràng buộc về giáo viên, phòng học do vậy

đều phải kiểm soát đƣợc các trạng thái ràng buộc này trên cơ sở ràng buộc

cứng và mềm.

- Các môn học của cùng một lớp không đƣợc xếp trùng giờ, trùng tiết.

- Phải kiểm soát các môn học để không xảy ra 2 môn học của lớp

trùng nhau về thời gian.

- Có sự phân chia các môn học theo thứ tự ƣu tiên về ý nghĩa môn học

để sắp xếp.

- Với mỗi môn học của thời khóa biểu đƣợc gắn cho một hay nhiều lớp

1.4.4. Các đặc thù của thời khóa biểu hệ trung học phổ thông

Phân tích các đặc thù của thời khóa biểu trên cơ sở các ràng buộc.

Ràng buộc về cơ bản vẫn là các yêu cầu từ phía đối tƣợng đặt ra, bắt buộc

bài toán phải thỏa mãn tất cả, nhƣng phần nghiệp vụ cũng mang lại một

ràng buộc cần thiết nhằm tránh một số trƣờng hợp sai sót để giúp quá trình

thực thi cho ra kết quả đúng.

Vậy liệt kê đƣợc đầy đủ các ràng buộc có thể có trong bài toán là công

việc quan trọng cần làm. Các thành phần ràng buộc của bài toán có thể kể

đến đó là:

- Ràng buộc dữ liệu nhập vào.

- Ràng buộc môn học, thời gian.

a. Ràng buộc dữ liệu nhập vào

Các dữ liệu chính của thời khóa biểu bao gồm:

- Danh sách môn học.

- Danh sách khối học.

- Danh sách lớp học.

- Danh sách giáo viên.

- Danh sách phòng học.

- Bảng phân công giáo viên giảng dạy tại các lớp học.

- Bảng yêu cầu ràng buộc của giáo viên đối với lịch dạy.

- Bảng yêu cầu ràng buộc của phòng học đối với lịch dạy.

Do yêu cầu đặt ra của bài toán xếp thời khóa biểu mà các ràng buộc

dữ liệu phải đƣợc thiết lập sau khi đã nhập các đối tƣợng: giáo viên, học

sinh, phòng học.

+ Đối tượng giáo viên:

Trong mô hình của bài toán xếp thời khóa biểu vai trò các giáo viên là

ngang nhau. Mỗi giáo viên về nguyên tắc sẽ có một thời khóa biểu lịch giảng

dạy riêng của mình trong học kỳ hoặc năm học hiện thời. Những đặc thù sau

cần chú ý khi xem xét dữ liệu thời khóa biểu liên quan đến giáo viên:

Trong mô hình xếp thời khóa biểu thông tin phân bổ việc xếp thời

khóa biểu sơ bộ về là rất quan trọng.

Mỗi giáo viên có một lịch đăng ký giảng dạy cá nhân riêng, do đó phải

nhập bảng lịch này vào để nhập giờ dạy theo lịch của giáo viên trong việc xếp

thời khóa biểu.

+ Đối tượng học sinh:

Học sinh đƣợc phân công vào các lớp học.

Học sinh là đối tƣợng phải tham gia nhiều hoạt động của trƣờng, do đó

cũng có một số lịch thời gian riêng để thực hiện những công việc khác ngoài

học tập. Nhƣ vậy ta phải nhập khoảng thời gian không học tập đƣợc vào làm dữ

liệu cho bài toán.

+ Đối tượng Phòng học:

Phòng học đóng vai trò rất quan trọng trong bài toán xếp thời khóa

biểu. Các phòng học đƣợc dùng cho mục đích học tập và mỗi phòng học

cũng có lịch đăng ký tổ chức học tập riêng.

Phòng học đƣợc gắn phân công tổ chức cho các lớp học.

hi xét đến đối tƣợng phòng học phải xét địa điểm của phòng học ở

đâu, sức chứa bao nhiêu, trang bị trong phòng học, phòng học lý thuyết,

thực hành và chức năng hợp lý …

b. Ràng buộc thời gian, môn học

- Một ngày đƣợc tổ chức học 1 ca, ca sáng học 5 tiết.

- Không có học sinh nào tại một thời điểm đƣợc học nhiều môn.

- Giáo viên không dạy nhiều lớp cùng một thời điểm.

- Phòng học tại một thời điểm chỉ đƣợc tổ chức giảng dạy cho một lớp.

- Lớp học tránh những giờ không đƣợc học do nhà trƣờng quy định

(các ngày nghỉ, lễ Tết…)

- Giáo viên giảng dạy theo các thời điểm đã đăng ký với nhà trƣờng.

Tuy nhiên việc này có thể cản trở việc xếp lịch, dẫn đến không thể xếp đƣợc

nhƣng nếu không giải quyết đƣợc cho giáo viên dạy theo các thời điểm đã đăng

ký thì có thể kết quả xếp lịch thời khóa biểu sẽ khó đƣợc thực hiện.

- Các giờ không cho phép học tại các phòng học, sẽ không có lớp học

nào đƣợc tổ chức quy định của phòng học).

- Tổng số tiết học của các môn học phải đƣợc đảm bảo đúng theo thời

gian quy định của nhà trƣờng.

1.4.5. Nhu cầu bài toán xếp thời khóa biểu

Bài toán xếp thời kháo biểu đã từ lâu trở thành một bài toán hết sức

đƣợc quan tâm của rất nhiều nhà nghiên cứu cũng nhƣ các chuyên gia trong

lĩnh vực liên quan. Điều đƣợc quan tâm của bài toán xếp thời khóa biểu

không chỉ bởi độ phức tạp của nó, mà còn ở tính thực tiễn, khả năng áp dụng

rất cao trên thực tế từ trƣớc đến nay. Bất cứ nhà trƣờng, thời khóa biểu học tập

của học sinh và giảng dạy cảu giáo viên đã và luôn là cầu nối cho hầu hết các

hoạt động của nhà trƣờng. Chính vì lẽ đó bài toán bài toán xếp thời khóa biểu

chở thành nhu cầu cần thiết và quan trọng của nhà trƣờng.

Theo nghiên cứu tại Việt Nam, trƣớc những năm 1986, công việc xếp

thời khóa biểu chủ yếu đƣợc làm bằng tay bởi các nhà quản lý. Điều này vô

cùng khó khăn vì đã tiêu tốn một thời lƣợng thời gian và công sức không

nhỏ của các nhà quản lý đào tạo. Đòi hỏi ngƣời xếp lịch phải có kinh

nghiệm và sự am hiểu cao về lĩnh vực này. Đó là những ngƣời rất khó thay

thế bởi mỗi lần thay đổi, chỉnh sửa thời khóa biểu không thể làm đƣợc bởi

những ngƣời không có chuyên môn. Chính những khó khăn, thách thức đó

cùng với sự phát triển mạnh mẽ của Công nghệ thông tin, việc xây dựng

phƣơng pháp tự động xếp thời khóa biểu đã trở thành tất yếu cần thiết cho

các trƣờng học.

Năm 1986-1987, một nhóm chuyên gia máy tính tại khoa toán Học

viện Kỹ thuật Quân sự đã bắt đầu nghiên cứu bài toán xếp Thời khóa biểu

cho mô hình đại học.Và đó là nền móng cho việc phát triển các phần mềm

thời khóa biểu sau này đi đến những thành công nhất định.

Tuy nhiên do tính chất của mỗi nhà trƣờng là khác nhau nên việc xếp

thời khóa biểu trở nên đa dạng, không thể sử dụng một phần mềm để giải

quyết đƣợc cho tất cả các trƣờng học.

Tại Việt Nam, có đến hàng ngàn trƣờng học, nhƣng hiện nay vẫn chỉ

gần 1/3 số các trƣờng là có ứng dụng của Công nghệ thông tin vào giải

quyết bài toán xếp thời khóa biểu, số còn lại chủ yếu xếp bằng tay. Do vậy

nhu cầu giải quyết và sử dụng bài toán xếp thời khóa biểu còn rất lớn trong

giai đoạn hiện nay. Đặc biệt là ngày càng xuất hiện nhiều các mô hình đào

tạo khác nhau theo chủ trƣơng về cải cách giáo dục tại Việt Nam.

Trƣờng phổ thông Vùng cao Việt Bắc là một trong những trƣờng Dân

tộc nội trú với rất đông các con em dân tộc của các tỉnh miền núi phía Bắc

đang học tập. Là một ngôi trƣờng có đặc thù rất riêng biệt: Mỗi học kỳ

đƣợc chia thành nhiều giai đoạn khác nhau, mỗi giai đoạn số tiết dạy của

từng bộ môn có sự thay đổi để đáp ứng yêu cầu của từng môn và thƣờng

đƣợc làm thủ công nên hiệu quả không mấy khả quan.

Hiện nay có một số phần mềm xếp thời khóa biểu của Cục Công Nghệ

Thông tin, hay một số tổ chức khác dành cho các trƣờng phổ thông trung học

nhƣng hiệu quả không cao, không đáp ứng đƣợc nhu cầu của từng giáo viên.

Vì vậy, các trƣờng thƣờng phải làm thủ công, còn áp dụng vào cho trƣờng

phổ thông Vùng cao Việt Bắc thì hoàn toàn không thể đáp ứng đƣợc.

Công nghệ thông tin đã và đang phát triển rất mạnh mẽ, nhƣng việc

chia thời khóa biểu cho tất cả các trƣờng phổ thông trung học trên cả nƣớc

nói chung, trƣờng phổ thông Vùng cao việt bắc nói riêng vẫn phải làm thủ

công nên hiệu quả không cao lại mất rất nhiều công sức và thời gian. Bài

toán đặt ra là xếp thời khóa biểu cần có sự sắp xếp lịch học cho các lớp tại các

phòng học ở mỗi địa điểm, sao cho vừa hợp lý lại vừa tiện dụng và phù hợp với

từng bộ môn và cơ sở của nhà trƣờng. Nhu cầu của giáo viên khác nhau, một số

giáo viên lại có nhu cầu đến trƣờng vào một số ngày khác nhau trong tuần. Từ

những nhu cầu đó mà việc xếp thời khóa biểu trở nên rất khó khăn thể hiện

ở các lý do sau:

- Thứ nhất: Việc xếp thời khóa biểu đòi hỏi tƣ duy, tính toán, suy luận

rất phức tạp, dễ xảy ra nhầm lẫn nhƣ: trùng giờ trùng tiết, thiếu giờ thiếu

tiết,... Nhƣ vậy, việc xếp thời khóa biểu đòi hỏi ngƣời phải có nhiều kinh

nghiệm và hiểu biết về công việc này mới có thể làm đƣợc.

- Thứ hai: Các ràng buộc của giáo viên trong trƣờng rất mâu thuẫn,

chồng chéo lẫn nhau.

- Thứ ba: Công việc xếp thời khóa biểu đòi hỏi phải có tƣ duy đặc biệt

của công việc xếp thời khóa biểu.

Từ thực tế đó, cần có những phần mềm tự động xếp thời khóa biểu

riêng cho trƣờng. Từ sự cần thiết này, đề tài Nghiên cứu bài toán lập lịch và

ứng dụng xếp thời khóa biểu để làm sao thỏa mãn nhu cầu thực tế, đáp ứng

sự cần thiết, cấp bách của các trƣờng phổ thông trung học nói chung,

trƣờng phổ thông Vùng cao Việt Bắc nói riêng.

CHƢƠNG 2:

MỘT SỐ HƢỚNG TIẾP CẬN VÀ THUẬT TOÁN

GIẢI BÀI TOÁN XẾP THỜI KHÓA BIỂU.

2.1. Đề xuất các giải thuật giải bài toán

2.1.1. Giải thuật vét cạn.

Vét cạn là một trong những giải thuật giải bài toán tối ƣu. Gải thuật

vét cạn là tìm phƣơng án tối ƣu của bài toán bằng cách lựa chọn một

phƣơng án trong tập hợp tất cả các phƣơng án của bài toán để tìm ra

phƣơng án tối ƣu. Trong nhiều bài toán, không gian các phƣơng án quá lớn.

Do vậy, khi áp dụng thuật toán vét cạn không đảm bảo về thời gian cũng

nhƣ kĩ thuật.Trong quá trình duyệt ta luôn giữ lại một phƣơng án là phƣơng

án mẫu, là phƣơng án có giá nhỏ nhất tại thời điểm đó. Phƣơng pháp đánh

giá nhánh cận là phƣơng pháp tính giá của phƣơng án ngay trong quá trình

xây dựng các thành phần của phƣơng án, có nghĩa là ta sẽ tính xem việc

xây dựng phƣơng án theo hƣớng đó có thể có thể tốt hơn phƣơng án mẫu

hay không. Nếu không tốt hơn ta lựa chọn hƣớng khác. Bằng cách này ta

đã hạn chế đƣợc nhiều phƣơng án mà chắc rằng trong đó không chứa

phƣơng án tối ƣu. Một yêu cầu đặt ra là tính toán đặt nhánh cận nhƣ thế

nào, để có thể hạn chế tối đa các phƣơng án phải duyệt.

2.1.2. Giải thuật chia để trị

Đây là kỹ thuật từ trên xuống ( top - down),Có thể nói rằng đây là kỹ

thuật quan trọng nhất, đƣợc áp dụng rộng rãi nhất để thiết kế các giải thuật

có hiệu quả.

Nội dung của nó là: Để giải một bài toán kích thƣớc n, ta chia bài toán

đã cho thành một số bài toán con có kích thƣớc nhỏ hơn. Giải các bài toán

con này rồi tổng hợp kết quả lại để đƣợc lời giải của bài toán ban đầu. Đối

với các bài toán con, chúng ta lại sử dụng kỹ thuật chia để trị để có đƣợc

các bài toán kích thƣớc nhỏ hơn nữa. Quá trình trên sẽ dẫn đến những bài

toán mà lời giải chúng là hiển nhiên hoặc dễ dàng thực hiện, ta gọi các bài

toán này là bài toán cơ sở.

Tóm lại kỹ thuật chia để trị bao gồm hai quá trình: Phân tích bài toán

đã cho thành các bài toán cơ sở và tổng hợp kết quả từ bài toán cơ sở để có

lời giải của bài toán ban đầu. Tuy nhiên đối với một số bài toán, thì quá

trình phân tích đã chứa đựng việc tổng hợp kết quả do đó nếu chúng ta đã

giải xong các bài toán cơ sở thì bài toán ban đầu cũng đã đƣợc giải quyết.

Ngƣợc lại có những bài toán mà quá trình phân tích thì đơn giản nhƣng

việc tổng hợp kết quả lại rất khó khăn.

Hai giải thuật sắp xếp MergeSort và QuickSort thực chất là đã sử dụng

kỹ thuật chia để trị.

Với MergeSort, để sắp một danh sách L gồm n phần tử, chúng ta chia

L thành hai danh sách con L1 và L2 mỗi danh sách có n/2 phần tử. Sắp xếp

L1, L2 và trộn hai danh sách đã đƣợc sắp này để đƣợc một danh sách có

thứ tự. Quá trình phân tích ở đây là quá trình chia đôi một danh sách, quá

trình này sẽ dẫn đến bài toán sắp xếp một danh sách có độ daì bằng 1, đây

chính là bài toán cơ sở vì việc sắp xếp danh sách này là “không làm gì cả”.

Việc tổng hợp các kết quả ở đây là “trộn 2 danh sách đã đƣợc sắp để đƣợc

một danh sách có thứ tự”.

Với QuickSort, để sắp xếp một danh sách gồm n phần tử, ta tìm một

giá trị khóa và phân hoạch danh sách đã cho thành hai danh sách con “bên

trái” và “bên phải “. Sắp xếp “bên trái” và “bên phải” thì ta đƣợc danh sách

có thứ tự. Quá trình phân chia sẽ dẫn đến các bài toán sắp xếp một danh

sách chỉ gồm một phần tử hoặc gồm nhiều phần tử có khoá bằng nhau, đó

chính là các bài toán cơ sở, vì bản thân chúng đã có thứ tự rồi. Ở đây chúng

ta cũng không có việc tổng hợp kết quả một cách tƣờng minh, vì việc đó đã

đƣợc thực hiện trong quá trình phân hoạch.

2.1.3. Giải thuật Heuristic:

Là các giải thuật dựa trên phân tích yếu tố cụ thể gắn với bài toán để

xác định phƣơng hƣớng tìm kiếm lời giải. Nó thể hiện cách giải bài toán

với các đặc tính sau :

- Thƣờng tìm đƣợc lời giải tốt nhƣng không chắc là lời giải tốt nhất)

- Giải bài toán theo thuật giải Heuristic thƣờng dễ dàng và nhanh

chóng đƣa ra kết quả hơn so với giải thuật tối ƣu, vì vậy chi phí thấp hơn.

- Thuật giải Heuristic thƣờng thể hiện khá tự nhiên, gần gũi với cách

suy nghĩ và hành động của con ngƣời.

Có nhiều phƣơng pháp để xây dựng một thuật giải Heuristic, trong đó

ngƣời ta thƣờng dựa vào một số nguyên lý cơ sở nhƣ sau:

- Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó,

khi không gian tìm kiếm lớn, ta thƣờng tìm cách giới hạn lại không gian

tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài

toán để nhanh chóng tìm ra mục tiêu.

- Nguyên lý tham lam (Greedy):

Lấy tiêu chuẩn tối ƣu trên phạm vi toàn cục) của bài toán để làm tiêu

chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bƣớc (hay từng

giai đoạn) trong quá trình tìm kiếm lời giải.

- Nguyên lý thứ tự:

Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không

gian khảo sát nhằm nhanh chóng đạt đƣợc một lời giải tốt.

- Nguyên lý hƣớng đích Hàm Heuristic):

Trong việc xây dựng các thuật giải Heuristic, ngƣời ta thƣờng dùng

các hàm Heuristic. Ðó là các hàm đánh giá thô, giá trị của hàm phụ thuộc

vào trạng thái hiện tại của bài toán tại mỗi bƣớc giải. Nhờ giá trị này, ta có

thể chọn đƣợc cách hành động tƣơng đối hợp lý trong từng bƣớc của thuật

giải. Trong bài toán xếp thời khóa biểu các hƣớng heuristic có thể là:

- Xếp thời khóa biểu các lớp khó xếp trƣớc, ở đây độ khó xếp có thể

đánh giá qua số giờ giảng dạy đƣợc phân cho giáo viên phụ trách lớp. Số

giờ càng lớp, độ khó càng cao.

- Phòng học sử dụng cho lớp đƣợc gán cho nhiều lớp khác: số lớp

đƣợc gán càng lớn, độ khó càng cao.

Hai tiêu chí độ khó này thể hiện thực tế: do giáo viên phụ trách lớp dạy

nhiều nên thời gian tự do lựa chọn của giáo viên giảm. Tƣơng tự với trƣờng

hợp phòng học.

2.2. Đánh giá các phƣơng pháp:

- Giải thuật chia để trị:

+ Ƣu điểm: Chia nhỏ các bài toán nên giảm đƣợc sự phức tạp của bài toán.

+ Nhƣợc điểm: Các bài toán con khi kết hợp lại để tạo bài toán hoàn

chỉnh dễ xảy ra xung đột.

Bài toán xếp thời khóa biểu có độ phức tạp lớn, và là bài toán đa mục

tiêu. Vì vậy cần chia bài toán thành nhiều bài toán nhỏ để giảm bớt độ phức

tạp các bài toán. Sau đó lại kết hợp lời giải các bài toán nhỏ để tạo Thời

khóa biểu tổng thể. Điều này càng dẫn đến xảy ra xung đột vì vậy bài toán

thời khóa biểu không nên áp dụng phƣơng pháp này. Ta chỉ nên kếp hợp

với các phƣơng pháp khác để giải quyết bài toãn xếp thời khóa biểu.

- Giải thuật vét cạn:

+ Ƣu điểm: Vét đƣợc các trƣờng hợp của bài toán.

+ Nhƣợc điểm: Với bài toán lớn nhƣ thời khóa biểu độ phức tạp lớn

nên cần nhiều thời gian để thực hiện.

Nhƣ vậy giải thuật vét cạn về mặt nguyên tắc luôn tìm đƣợc nghiệm

nếu bài toán có nghiệm. Nhƣng trên thực tế, các bài toá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 toán và dung lƣợng bộ nhớ, không cho phép ta thực hiện đƣợc.

- Giải thuật Heuristic:

+ Ƣu điểm: Thuật giải Heuristic thƣờng thể hiện khá tự nhiên, gần gũi

với cách suy nghĩ và hành động của con ngƣời. Dễ dàng và nhanh chóng

đƣa ra kết quả vì vậy chi phí thấp hơn.

+ Nhƣợc điểm: Có nhiều bài toán cho tới nay vẫn chƣa xây dựng

đƣợc thuật toán. Có bài toán xây dựng đƣợc thuật toán song không thể áp

dụng đƣợc do không đủ tài nguyên để cung cấp. Có thể giải quyết một số

bài toán theo những cách khác, thƣờng cho kết quả tốt và thực hiện dễ dàng

hơn so với thuật toán.

Nhƣ vậy, Thuật giải Heuristic thƣờng thể hiện khá tự nhiên, gần gũi

với cách suy nghĩ và hành động của con ngƣời. Dễ dàng và nhanh chóng

đƣa ra kết quả vì vậy chi phí thấp hơn. Do đó có thể áp dụng giải thuật

Heuristic để giải quyết bài toán xếp thời khóa biểu.

Kết luận:

- Xây dựng thời khóa biểu dựa theo các thuật toán trên đã không còn

mới mẻ và cũng chƣa giải quyết đƣợc bài toán một cách tối ƣu, triệt để

hoàn toàn.

- Với mục tiêu giải quyết đƣợc một phƣơng án chấp nhận đƣợc cho bài

toán xếp thời khóa biểu, tác giả không đặt mục tiêu xây dựng theo hƣớng

hoàn toàn tối ƣu nên không đi theo hƣớng đã đƣợc một số các tác giả ứng

dụng để giải quyết bài toán xếp thời khóa biểu.

- Căn cứ vào quy trình xây dựng thời khóa biểu và các yêu cầu thực

tế, em lấy tiêu chí là xây dựng đƣợc một thuật giải riêng phù hợp với quy

trình xếp thời khóa biểu của trƣờng học, tìm ra đƣợc một thời khóa biểu

khả thi, chấp nhận đƣợc.

- Tuy nhiên nhận thấy phƣơng pháp chia nhỏ để giải quyết bài toán và

xây dựng hàm tối ƣu của thuật toán Heuristic là tối ƣu hóa đàn kiến(ANT

COLONY OPTIMIZATION: ACO) là những phƣơng hƣớng tốt để giải

quyết bài toán xếp thời khóa biểu.

2.3. Giới thiệu giải thuật tối ƣu hóa đàn kiến (ANT COLONY

OPTIMIZATION: ACO)

Bài toán tối ƣu hóa tổ hợp (Combinatorial Optimization Problems) là

bài toán hấp dẫn và thú vị phần lớn chúng đều dễ để hình dung nhƣng khó

tìm ra lời giải. Nhiều bài toán tối ƣu hóa tổ hợp là các bài toán NP – khó và

chúng không thể giải đƣợc trong thời gian đa thức. Trên thực tế ngƣời ta

thƣờng giải quyết các bài toán này bằng các phƣơng pháp xấp xỉ, chúng có

nghiệm gần tối ƣu và thời gian chạy khá ngắn. Các thuật toán thuộc loại

này thƣờng đƣợc gọi là các thuật toán heuristic, chúng đƣợc sử dụng để

giải quyết các bài toán cụ thể. Mở rộng của chúng là các bài toán

metaheuristic có thể giải quyết đƣợc cả một lớp các bài toán rộng lớn.

Phƣơng pháp tối ƣu hóa đàn kiến (Ant Colony Optimization: ACO) là một

phƣơng pháp theo hƣớng tiếp cận nhƣ thế.

Tối ƣu đàn kiến (Ant Colony Optimization: ACO) là một phƣơng

Metaheuristic đƣợc đề xuất bởi Dorigo vào năm 1991[3] dựa trên ý tƣởng

mô phỏng cách tìm đƣờng đi từ tổ tới nguồn thức ăn của các con kiến tự

nhiên. Trên đƣờng đi của mình các con kiến thực để lại một vết hóa chất

đƣợc gọi là vết mùi (pheromone trail), đặc điểm sinh hóa học của vết mùi

này là có khả năng ứ đọng, bay hơi và là phƣơng tiện giao tiếp báo cho các

con kiến khác thông tin về đƣờng đi đó một cách gián tiếp. Các con kiến sẽ

lựa chọn đƣờng đi nào tồn đọng lƣợng mùi hay có cƣờng độ vết mùi lớn

nhất tại thời điểm lựa chọn để đi, nhờ cách giao tiếp mang tính gián tiếp và

cộng đồng này mà đàn kiến trong tự nhiên tìm đƣợc đƣờng đi ngắn nhất

trong quá trình tìm thức ăn mang về tổ và ngƣợc lại.

Sử dụng mô hình kiến nhân tạo này Dorigo (1991) đã xây dựng thuật

toán hệ kiến (AS) giải bài toán ngƣời chào hàng. Thuật toán này đã đƣợc

chứng minh tính hiệu quả thông qua thực nghiệm so với các mô phỏng tự

nhiên khác nhƣ SA mô phỏng luyện kim) và GA (giải thuật di truyền).

Thuật toán này về sau đƣợc phát triển và có nhiều áp dụng phong phú trong

thực tế, đƣợc gọi chung là phƣơng pháp ACO.

- ACO là một mô hình để thiết kế các thuật toán metaheuristic cho

việc giải quyết bài toán tối ƣu hóa tổ hợp

- ACO – phƣơng pháp tối ƣu hóa đàn kiến [1] mô phỏng hành vi của

bầy kiến trong tự nhiên nhằm tìm kiếm đƣờng đi ngắn nhất giữa tổ kiến và

nguốn thức ăn dựa trên mật độ mùi (Pheromone) mà các con kiến để lại

trên đƣờng đi. Thuật toán này lần đầu tiên đƣợc ứng dụng giải bài toán

phân loại các trạm làm việc vào năm 1991. Sau đó, rất nhiều các biến thể

của thuật toán dựa trên các nguyên lý cơ bản của nó đƣợc giới thiệu. Đặc

điểm chủ yếu của thuật toán ACO là sự kết hợp của các thông tin về cấu

trúc của lời giải triển vọng với thông tin về cấu trúc của các lời giải tốt

trƣớc đó.

- Hiệu quả nổi trội của thuật toán ACO đã đƣợc thể hiện khi so sánh

với một số thuật toán nổi tiếng khác nhƣ thuật toán di truyền (GA), Tabu-

Search, ocal Search, … Ngƣời ta đã áp dụng rất thành công các thuật toán

kiến trong một số các bài toán tối ƣu thƣờng gặp nhƣ: bài toán ngƣời chào

hàng, bài toán ngƣời đƣa thƣ, bài toán gán, bài toán tô màu đồ thị, bài toán

lập lịch, …trong đó phải kể đến bài toán xếp thời khóa biểu.

Nhờ những thành quả to lớn trong việc ứng dụng phƣơng pháp tối ƣu

đàn kiến vào giải các bài toán tối ƣu tổ hợp khó mở ra một lĩnh vực nghiên

cứu và ứng dụng mới thu hút đƣợc sự quan tâm của đông đảo các nhà khoa

học trên thế giới, Dorigo đã đƣợc Hội đồng châu u trao giải thƣởng đặc

biệt Marie Curie (Marie Curie Excellence Award) trao hai năm một lần

giành cho năm nhà khoa học có nhiều đóng góp cho nền khoa học và công

nghệ châu u vào ngày 05 11 2003. Cho đến nay, các hội nghị về đàn kiến

đã tổ chức 6 lần ANT 98, ANT 2000, ANTS 2002, ANTS 2004, ANTS

2006, ANTS 2008) và ở mỗi hội nghị có khoảng 30-40 báo cáo về các công

trình nghiên cứu lý thuyết và thực nghiệm có ý nghĩa khoa học và ứng

dụng quan trọng góp phần chứng tỏ ACO là phƣơng pháp tối ƣu mới mẻ và

hiệu quả http://iridia.ulb.ac.be/~ants/).

2.4. Mô tả giải thuật tối ƣu hóa đàn kiến

2.4.1. Trình bày giải thuật

Khi áp dụng ACO cho các bài toán cụ thể, có bốn yếu tố quyết định

hiệu quả của thuật toán:

- Xây dựng đồ thi cấu trúc thích hợp: Tùy thuộc vào đặc thù của bài toán

- Xây dựng lời giải tuần tự: Tùy thuộc vào đặc thù của bài toán

- Chọn thông tin heuristic: Thông tin heuristic tốt sẽ làm tăng hiệu quả

của thuật toán. Tuy nhiên có nhiều bài toán không có thông tin này thì có

thể đánh giá chúng nhƣ nhau.

- Chọn quy tắc cập nhật mùi: Quy tắc cập nhật mùi[2],[6] thể hiện

chiến lƣợc học của thuật toán. Hai yếu tố đầu: Đồ thị cấu trúc và thông tin

heuristic phụ thuộc vào bài toán cụ thể, còn quy tắc cập nhật mùi là yếu tố

phổ dụng và thƣờng dùng làm tên để phân biệt cho các thuật toán ACO.

a. Đồ thị cấu trúc

Bài toán tối ưu tổ hợp tổng quát

Mỗi bài toán tối ƣu tổ hợp tổng quát ứng với một bộ ba trong

đó S là tập hữu hạn các trạng thái (lời giải tiềm năng hay phƣơng án), f là

hàm mục tiêu xác định trên S, còn Ω là tập các ràng buộc. Mỗi phƣơng án

thỏa mãn các ràng buộc gọi là phƣơng án chấp nhận đƣợc. Mục

tiêu của chúng là tìm ra phƣơng án tối ƣu hóa toàn cục đối với hàm mục

tiêu , nói cách khác chính là tìm phƣơng án sao cho với

mọi . Đối với bài toán này ta có 3 cách giải quyết đó là: Vét cạn, kỹ

thuật ăn tham hoặc phƣơng pháp tối ƣu trong lĩnh vực NP-khó.

Các tập C, S, Ω có đặc tính nhƣ sau [1,tr.31-32]: C là một tập hữu hạn

mà mỗi phƣơng án của C gồm một bộ ba trong đó S là tập hữu

hạn các trạng thái (lời giải tiềm năng hay phƣơng án), f là hàm mục tiêu

xác định trên S, còn Ω là tập các ràng buộc

1) Ký hiệu X là tập các vectơ trong C độ dài không quá h: X =

. hi đó, mỗi phƣơng án s trong S

đƣợc xác định bởi ít nhất một vectơ trong X nhƣ ở điểm 2).

2) Tồn tại tập con X* của X và ánh xạ từ X* lên S sao cho không rỗng với S, trong đó tập X* có thể đƣợc xây dựng từ tập con C0

của C nhờ mở rộng tuần tự điểm 3 dƣới đây).

3) Từ C0 ta mở rộng tuần tự thành X* nhƣ sau:

i) Ta xem x0 = là mở rộng đƣợc với . ii) Giả sử là mở rộng đƣợc và chƣa thuộc vào X*. Từ tập ràng buộc Ω, xác định tập con của C, sao cho

thì là mở rộng đƣợc.

iii) Áp dụng thủ tục từ các phần tử cho phép ta xây dựng

đƣợc mọi phần tử của X*.

b. Xây dựng đồ thị cấu trúc

Mỗi bài toán tối ƣu tổ hợp đƣợc xem nhƣ một bài toán tìm kiếm vectơ

độ dài không quá trên đồ thị đầy đủ có các đỉnh đƣợc gán nhãn trong tập

. Để tìm các lời giải chấp nhận đƣợc, ta xây dựng đồ thị với tập đỉnh ,

mỗi đỉnh của nó tƣơng ứng với mỗi thành phần của Các lời giải chấp

nhận đƣợc sẽ là các vectơ đƣợc xác định theo thủ tục mở rộng tuần tự hay

mở rộng ngẫu nhiên.

Thông thƣờng, đối với các bài toán thuộc loại NP-khó, ngƣời ta đƣa ra

các phƣơng pháp heuristic tìm lời giải đủ tốt cho bài toán. Các thuật toán

ACO kết hợp thông tin heuristic này với phƣơng pháp học tăng cƣờng, mô

phỏng hành vi của đàn kiến, để tìm lời giải tốt hơn.

Ta gọi đồ thị là đồ thị cấu trúc của bài toán tối ƣu tổ

hợp, trong đó V là tập đỉnh, E là tập cạnh, H là vectơ các trọng số heuristic

của cạnh và là vectơ biểu thị các thông tin học tăng cƣờng . Từ các cạnh ta xây dựng tập X* nhờ mở rộng tập theo thủ tục tuần tự. Nếu không có thông tin heuristics thì ta xem H có các thành phần nhƣ nhau và

bằng 1.

Trƣờng hợp tổng quát, là đồ thị đầy đủ.Tuy nhiên, tùy theo ràng

buộc của bài toán, các cạnh có thể lƣợc bớt để giảm miền tìm kiếm lời giải

theo thủ tục mở rộng tuần tự. Chẳng hạn, với bài toán tìm cực trị của hàm

giải tích , với thuộc tập giá trị hữu hạn , đồ thị cấu trúc có

tầng, tầng chứa các đỉnh thuộc tập , còn tập cạnh chỉ gồm các cạnh

nối các đỉnh thuộc tầng với các đỉnh thuộc tầng

nhƣ trong hình 2.1. hi đó tập là tập , mỗi mở rộng tuần tự của lời

giải sẽ đƣợc xây dựng từ một đỉnh thuộc tập này.

Hình 2.1: Đồ thị cấu trúc tổng quát cho bài toán cực trị hàm

c. Xây dựng lời giải

Lời giải trên đồ thị cấu trúc nhƣ sau: hởi tạo với m

con kiến, tại mỗi lần lặp, kiến sẽ chọn ngẫu nhiên một đỉnh để làm khởi tạo

ban đầu x0 = với . Sau đó các con kiến sẽ đi xây dựng lời

giải theo thủ tục bƣớc ngẫu nhiên.

Từ đỉnh ta tiến hành mở rộng các đỉnh cho đến khi thuộc vào X*, nghĩa là tìm đƣợc lời giải chấp nhận đƣợc. Giả sử con kiến đang ở đỉnh

và có một đỉnh ( để

mở rộng (hay có thể hiểu con kiến từ đỉnh i sẽ lựa chọn đỉnh j) đƣợc chọn

với xác suất nhƣ sau:

{ (2.1)

Trong đó :

, : Giá trị thông tin mùi và thông tin heuristic.

: Hai tham số quyết định sự ảnh hƣởng tƣơng quan giữa thông tin

mùi và thông tin heuristic. Nếu không có học tăng cƣờng. Nếu

chỉ có thông tin học tăng cƣờng biểu thị qua vết mùi đƣợc sử dụng,

không có thông tin heurisric.

: Đỉnh lân cận của đỉnh i mà kiến có thể đi đến.

Quá trình mở rộng tiếp tục cho tới khi kiến tìm đƣợc lời giải chấp

nhận đƣợc trong và do đó .

Hình 2.2: Lựa chọn đỉnh đi tiếp theo

Để tiện trình bày, về sau ta sẽ xem và nhƣ nhau và không phân

biệt với .

d. Cập nhật mùi

Dựa trên lời giải tìm đƣợc, đàn kiến sẽ thực hiện cập nhật mùi theo

cách học tăng cƣờng.

(2.2)

Trong đó: : hệ số bay hơi tỷ lệ lƣợng mùi bị bay hơi), là hằng số

thuộc khoảng (0,1).

: lƣợng mùi do kiến để lại

e. Trình bày về thuật toán ACO cơ bản

Tiến hành sử dụng m con kiến để xây dựng lời giải trên đồ thị cấu

trúc. Quá trình tìm kiếm lời giải trên đồ thị kết thúc theo số bƣớc lặp hoặc

giới hạn thời gian chạy.

Procedure Thuật toán ACO;

Begin

Khởi tạo tham số, ma trận mùi, khởi tạo m con kiến;

Repeat

For =1 to m do

Kiến xây dựng lời giải;

Cập nhật mùi;

Cập nhật lời giải tốt nhất;

Until điều kiện kết thúc);

Đƣa ra lời giải tốt nhất;

End ;

Hình 2.3: Đặc tả thuật toán ACO

Nhận xét chung về các thuật toán ACO

- Nhờ kết hợp thông tin heuristic, thông tin học tăng cƣờng và mô

1) Việc tìm kiếm ngẫu nhiên dựa trên các thông tin heuristic trở nên linh

hoạt và mềm dẻo trên miền rộng hơn so với các phƣơng pháp heuristic đã có. Do

đó, cho ta lời giải tốt hơn và có thể tìm đƣợc lời giải tối ƣu.

2) Học tăng cƣờng thông qua thông tin về cƣờng độ vết mùi cho phép từng

bƣớc thu hẹp không gian tìm kiếm, mà vẫn không loại bỏ các lời giải tốt, do đó

nâng cao chất lƣợng thuật toán.

- Khi áp dụng phƣơng pháp ACO cho các bài toán cụ thể, các yếu tố sau có

ảnh hƣởng quyết định đến hiệu quả thuật toán:

1) Xây dựng đồ thị cấu trúc thích hợp. Việc xây dựng đồ thị cấu trúc để

tìm đƣợc lời giải cho bài toán theo thủ tục tuần tự không khó. hó khăn chính là

với các bài toán cỡ lớn, không gian tìm kiếm quá rộng, đòi hỏi ta sử dụng các

ràng buộc một cách hợp lý để giảm miền tìm kiếm của kiến.

2) Chọn thông tin heuristic. Thông tin heuristic tốt sẽ tăng hiệu quả thuật

toán. Tuy nhiên, trong nhiều bài toán không có thông tin này thì có thể đánh giá

chúng nhƣ nhau. hi đó, ban đầu thuật toán chỉ đơn thuần chạy theo phƣơng

thức tìm kiếm ngẫu nhiên, vết mùi thể hiện định hƣớng của học tăng cƣờng và

thuật toán vẫn thực hiện đƣợc.

3) Chọn quy tắc cập nhật mùi. Quy tắc cập nhật mùi thể hiện chiến lƣợc

học của thuật toán. Trong khi đồ thị cấu trúc và thông tin heuristic phụ thuộc vào

bài toán cụ thể, quy tắc cập nhật mùi lại là yếu tố phổ dụng và thƣờng dùng để đặt

tên cho thuật toán. Có nhiều quy tắc cập nhật mùi đã đƣợc đề xuất, luận văn này sẽ

tìm quy tắc thích hợp cho hai loại bài toán, tùy theo thông tin heuristic ảnh hƣởng

nhiều hay ít tới thủ tục tìm kiếm lời giải.

phỏng hoạt động của đàn kiến, các thuật toán ACO có các ƣu điểm sau:

2.4.2. Một số vấn đề liên quan

a. Đặc tính hội tụ

Gutjahr là một trong những ngƣời đầu tiên nghiên cứu đặc tính hội tụ

của thuật toán MMAS (Max – Min Ant System), nhƣng chƣa xét đến yếu

tố có sử dụng thông tin heuristic. Ký hiệu là xác suất tìm thấy lời giải

của thuật toán MMAS[5] trong vòng phép lặp, là lời giải tốt nhất ở

bƣớc lặp . Nhờ sử dụng mô hình Markov không thuần nhất, Gutjahr đã

chứng minh rằng với xác suất bằng 1 ta có:

(2.3)

(2.4) 1) , 2) = với mọi cạnh thuộc lời giải tối ƣu

Mô hình này của Gutjahr không áp dụng đƣợc cho ACS. Trong trƣờng

hợp MMAS không sử dụng thông tin heuristic, Stützle và Dorigo[4] đã chứng

minh rằng:

(2.5) đủ lớn ,

(2.6) do đó .

Các tác giả cũng suy ra rằng kết quả này cũng đúng cho cả thuật toán

ACS. Với giả thiết tìm đƣợc lời giải tối ƣu sau hữu hạn bƣớc, Stützle và

Dorigo suy ra rằng vết mùi của các cạnh thuộc lời giải tối ƣu tìm đƣợc sẽ

hội tụ đến , còn vết mùi trên các cạnh không thuộc lời giải sẽ hội tụ về hoặc .

Plelegrini và Elloro chỉ ra rằng sau một thời gian chạy, đa số vết mùi

trên cạnh trở nên bé và chỉ có số ít cạnh có giá trị vết mùi là lớn vƣợt trội.

b. ACO kết hợp với tìm kiếm địa phương

Môt số tài liệu chỉ ra rằng với các phƣơng pháp metaheuristic, một

cách tiếp cận đầy hứa hẹn cho phép nhận đƣợc lời giải có chất lƣợng cao là

kết hợp với thuật toán tìm kiếm địa phƣơng.

Mô hình ACO có thể bao gồm cả tìm kiếm địa phƣơng. Sau khi kiến

xây dựng xong lời giải, có thể áp dụng tìm kiếm địa phƣơng để nhận đƣợc

lời giải tối ƣu địa phƣơng.Việc cập nhật mùi đƣợc thực hiện trên các cạnh

thuộc lời giải tối ƣu địa phƣơng này. ết hợp xây dựng lời giải với tìm

kiếm địa phƣơng sẽ là một cách tiếp cận có triển vọng, là do trên thực tế,

cách xây dựng lời giải của ACO có sử dụng lân cận khác với tìm kiếm địa

phƣơng. Thực nghiệm cho thấy khả năng kết hợp tìm kiếm địa phƣơng cải

tiến đƣợc lời giải là khá cao.

c. Thông tin heuristic

Ta biết rằng thuật toán ACO mà không sử dụng tìm kiếm địa phƣơng,

thông tin heuristic sẽ rất cần thiết để có đƣợc lời giải tốt. Trên thực tế, ở

giai đoạn đầu vết mùi đƣợc khởi tạo nhƣ nhau. hi đó vết mùi không thể

giúp kiến tìm đƣờng đi dẫn tới các lời giải tốt, vì chƣa khác nhau nhiều.

Vai trò chính của thông tin heuristic là để khắc phục điều này, giúp kiến có

thể xây dựng đƣợc các hành trình tốt ngay trong giai đoạn đầu. Trong nhiều

trƣờng hợp, nhờ sử dụng tìm kiếm địa phƣơng, kiến vẫn có thể tìm đƣợc lời

giải tốt ngay trong giai đoạn đầu, không cần sử dụng thông tin heuristic nào

cả, mặc dù có làm cho quá trình tìm kiếm chậm hơn.

d. Số lượng kiến

Nếu không sử dụng tìm kiếm địa phƣơng và thông tin heuristic ít

(hoặc không có), trong giai đoạn đầu vết mùi không thể giúp kiến tìm

đƣờng đi dẫn tới các lời giải tốt. Nếu sử dụng số lƣợng kiến ít, trong giai

đoạn đầu sẽ không tìm đƣợc lời giải tốt và nhƣ vậy, việc cập nhật mùi đƣợc

cập nhật dựa trên các lời giải không tốt. hi đó, sẽ hƣớng việc tìm kiếm

xung quanh lời giải không tốt và do đó thuật toán sẽ không hiệu quả. Có thể

khắc phục phần nào nhƣợc điểm này bằng cách tăng số kiến, để tăng khả năng

tìm đƣợc lời giải tốt ở mỗi vòng lặp. Khi có sử dụng tìm kiếm địa phƣơng hoặc

thông tin heuristic mạnh, sử dụng nhiều kiến là lãng phí.

e. Tham số bay hơi

Ở mỗi vòng lặp, khi xây dựng đƣợc lời giải tốt (sử dụng tìm kiếm địa

phƣơng hoặc thông tin heuristic mạnh), tham số bay hơi sẽ đƣợc xác lập có

giá trị lớn, điều này giúp kiến quên đi những lời giải đã xây dựng, tập trung

công việc tìm kiếm xung quanh lời giải tốt mới đƣợc xây dựng. Trong

trƣờng hợp ngƣợc lại, ở mỗi vòng lặp, khả năng kiến tìm đƣợc lời giải tốt

không cao thì tham số bay hơiphải đƣợc thiết lập với giá trị nhỏ.

CHƢƠNG 3:

XÂY DỰNG CHƢƠNG TRÌNH XẾP THỜI KHÓA BIỂU

CHO TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC

3.1. Phân tích quy trình thực hiện bài toán

3.1.1. Phát biểu bài toán

Tại tất cả các trƣờng học, thời khóa biểu học tập của học sinh, giảng

dạy của giáo viên là quyết định hoạt động chính của nhà trƣờng, chính vì

vậy xếp thời khóa biểu đã trở thành vấn đề chính và quan trọng trong mỗi

nhà trƣờng.

Hiện nay cả nƣớc ta có khoảng 25,000 trƣờng học với các cấp bậc

khác nhau nhƣ: Tiểu học, Trung học cơ sở, Phổ thông trung học. Nghĩa là

đang có từng đó giáo viên làm nhiệm vụ xếp thời khóa biểu.

Việc xếp thời khóa biểu thực sự là một công việc rất khó và mất rất

nhiều thời gian. Xếp thời khóa biểu thể hiện cái khó ở các lý do sau:

- Thứ nhất: Việc xếp thời khóa biểu đòi hỏi tƣ duy, tính toán, suy luận

rất phức tạp, dễ xảy ra nhầm lẫn nhƣ: trùng giờ trùng tiết, thiếu giờ thiếu

tiết,... Nhƣ vậy, việc xếp thời khóa biểu đòi hỏi ngƣời phải có nhiều kinh

nghiệm và hiểu biết về công việc này mới có thể làm đƣợc.

- Thứ hai: Các ràng buộc của giáo viên trong trƣờng rất mâu thuẫn,

chồng chéo lẫn nhau.

- Thứ ba: Công việc xếp thời khóa biểu đòi hỏi phải có tƣ duy đặc

biệt. Ngƣời xếp thời khóa biểu, ngoài việc phải am hiểu về các môn học

cũng nhƣ quy định của Bộ Giáo Dục và Đào Tạo đối với nhà trƣờng về

chƣơng trình môn học, hiểu rõ yêu cầu của các giáo viên trong nhà trƣờng,

phải có tƣ duy nghề nghiệp của công việc xếp thời khóa biểu.

Từ thực tế đó, việc xây dựng một chƣơng trình xếp thời khóa biểu tự

động thay thế việc xếp thời khóa biểu cho trƣờng phổ thông Vùng cao Việt Bắc

cũng nhƣ các trƣờng phổ thông khác trên cả nƣớc là cần thiết và cấp bách.

Chƣơng trình xếp thời khóa biểu tự động cần đáp ứng đƣợc các vấn đề sau:

- Cập nhật đƣợc các thông tin cần thiết của từng giáo viên, của từng

lớp học và của từng môn học

- Đƣa ra thời khóa biểu chính xác và hợp lý cho từng lớp học và từng

giáo viên đƣợc phân công giảng dạy.

3.1.2. Bài toán xếp thời khóa biểu trong mô hình tổng thể

Trong mô hình tổng thể quản lý đào tạo của mỗi nhà trƣờng, bài toán

xếp thời khóa biểu ở trƣờng phổ thông là một khâu quan trọng. Có 2 chức

năng khác biệt nhau của thời khóa biểu đó là:

- Bài toán xếp thời khóa biểu.

- Bài toán quản lý thời khóa biểu.

Hai chức năng trên có đặc thù chung là cùng liên quan chặt chẽ đến dữ

liệu thời khóa biểu nhƣng về bản chất chúng hoàn toàn khác biệt nhau.

Bài toán xếp thời khóa biểu có chức năng chính là tạo ra các mẫu thời

khóa biểu phục vụ cho công việc học tập và giảng dạy của học sinh, giáo

viên trong nhà trƣờng. Đây là khâu đầu tiên của việc tin học hóa quản lý

đào tạo nhà trƣờng.

Còn bài toán quản lý thời khóa biểu lại có chức năng chính là quản lý,

truy vấn và tìm kiếm thông tin thời khóa biểu. Bài toán này có quan hệ chặt

chẽ với các bài toán quản lý khác của nhà trƣờng.

3.1.3. Đặc điểm công tác, kế hoạch đào tạo

Việc lập kế hoạch đƣợc thực hiện vào đầu các khóa học, đầu các năm

học và đầu các học kỳ nhằm xác định những công việc cần phải thực hiện,

những yêu cầu đặt ra trong công tác đào tạo. Công việc đƣợc thực hiện dựa

trên các quy chế, quy định của Bộ Giáo dục và Đào tạo và những quy định

của nhà trƣờng.

Hệ thống có một số đặc điểm chính nhƣ sau:

- Công tác xây dựng kế hoạch toàn khóa: Đƣợc thực hiện dựa trên

chƣơng trình đào tạo đã đƣợc phê duyệt, thực hiện vào đầu mỗi khóa học,

nhằm xác định các môn học bắt buộc, môn học tự chọn. Ngoài ra là kế

hoạch tổng thể về tổ chức đào tạo.

- Công tác lập kế hoạch học kỳ: Thực hiện dựa trên kế hoạch đào tạo

toàn khóa để xác định các môn học đƣợc giảng dạy trong học kỳ. Dựa

trên số lƣợng học sinh, điều kiện bảo đảm cơ sở vật chất, giáo viên để làm

bảng phân công giảng dạy.

- Xây dựng thời khóa biểu: Dựa trên bảng phân công giảng dạy, các

yêu cầu khác để xây dựng kế hoạch thời gian cụ thể cho việc giảng dạy của

từng lớp học. Đây là mục tiêu chính mà em nghiên cứu để giải quyết.

3.1.4. Quy trình xây dựng kế hoạch đào tạo thời khóa biểu

Trên cơ sở những nghiên cứu tổng quan về bài toán lập lịch, và dựa

trên đặc điểm, tình hình, điều kiện cụ thể của từng nhà trƣờng để xây dựng

kế hoạch đào tạo - thời khóa biểu. Luận văn lựa chọn nghiên cứu ứng dụng

đối với Trƣờng Phổ thông vùng cao Việt Bắc với quy trình xây dựng thời

khóa biểu nhƣ sau:

- Bƣớc 1: Lập kế hoạch đào tạo (dựa vào khung chƣơng trình đào tạo

của Nhà trƣờng theo các qui định của Ngành giáo dục).

- Bƣớc 2: Lập kế hoạch đào tạo theo tuần, theo học kỳ.

- Bƣớc 3: Xây dựng bảng phân công giáo viên.

- Bƣớc 4: Xây dựng bảng phân công từng lớp, từng khối.

- Bƣớc 5: Xây dựng thời khóa biểu.

- Bƣớc 6: Hoàn chỉnh thời khóa biểu tổng thể cho giáo viên, lớp học.

3.2. Sơ đồ xây dựng chƣơng trình xếp thời khóa biểu

Kế hoạch GD đƣợc phê duyệt

Xác định giáo viên Xác định môn học

Kế hoạch giảng dạy từng môn của mỗi lớp Xác định các lớp và khối học

Đ TKB:=0 In ra TKB Kết thúc

Hoàn thành TKB?

Số tiết của môn đủ?

Chọn môn học cho từng tiết của mỗi lớp S Đ

Giáo viên giảng dạy bị trùng lịch?

Xếp môn học vào từng tiết của mỗi lớp

Hình 3.1: Sơ đồ xây dựng chương trình TKB

Khi xây dựng bài toán xếp thời khóa biểu, các dữ liệu đầu vào và đầu

ra của bài toán gồm:

Dữ liệu đầu vào:

- Danh sách giáo viên.

- Danh sách lớp học.

- Danh sách môn học.

- Danh sách phòng học.

Dữ liệu đầu ra:

- Kết quả thời khóa biểu.

Áp dụng thuật toán ACO để áp dụng giải bài toán xếp thời khóa biểu

nhƣ sau:

Dựa vào khung chƣơng trình đào tạo của nhà trƣờng theo các qui

định của Ngành giáo dục.

Đầu tiên phân tích các dữ liệu của bài toán, và mã hóa số tiết học,

môn học.

Đối với mô hình đào tạo của trƣờng VCVB thì số tiết trung bình của

các lớp là 27 đến 29 tiết cho các khối học.

Thời gian học là ca sáng, gồm năm tiết, tiết thứ nhất của ngày thứ hai

là tiết Chào cờ, tiết thứ năm của ngày thứ bảy là tiết Sinh hoạt, hai tiết chào

cờ và sinh hoạt này là cố định trong cả năm học cho tất cả các khối trong

toàn trƣờng. Thứ hai và thứ bảy tất cả các lớp học sẽ đƣợc xếp cố định là 5

tiết học. Các tiết còn lại sẽ đƣợc sắp xếp theo quy định tùy thuộc vào từng

khối.

Bảng 3.1. Ví dụ về TKB của một lớp

1 2 28 29 ...

Chào cờ Văn Sử Sinh hoạt ...

Trong đó, các chỉ số từ 1 đến 29 sẽ tƣơng ứng là số tiết trong 1 tuần.

Áp dụng thuật toán ACO vào bài toán:

Bƣớc 1 Xây dựng lời giải.

Lời giải trên đồ thị cấu trúc nhƣ sau: hởi tạo với m

kiến, tại mỗi lần lặp, kiến sẽ chọn ngẫu nhiên một đỉnh để làm khởi tạo ban

đầu x0 = với . Sau đó các con kiến sẽ đi xây dựng lời giải

theo thủ tục bƣớc ngẫu nhiên.

Từ đỉnh ta tiến hành mở rộng các đỉnh cho đến khi thuộc vào X*, nghĩa là tìm đƣợc lời giải chấp nhận đƣợc. Giả sử con kiến đang ở đỉnh

và có một đỉnh ( để

mở rộng (hay có thể hiểu con kiến từ đỉnh i sẽ lựa chọn đỉnh j) đƣợc chọn

với xác suất nhƣ sau:

{

Trong đó :

, : Giá trị thông tin mùi và thông tin heuristic.

: Hai tham số quyết định sự ảnh hƣởng tƣơng quan giữa thông tin

mùi và thông tin heuristic. Nếu không có học tăng cƣờng. Nếu

chỉ có thông tin học tăng cƣờng biểu thị qua vết mùi đƣợc sử dụng,

không có thông tin heurisric.

: Đỉnh lân cận của đỉnh i mà kiến có thể đi đến.

Quá trình mở rộng tiếp tục cho tới khi kiến tìm đƣợc lời giải chấp

nhận đƣợc trong và do đó .

Để tiện trình bày, về sau ta sẽ xem và nhƣ nhau và không phân

biệt với .

Mỗi kiến nhân tạo đi xây dựng lời giải bằng cách điền môn lên ma

trận môn một cách ngẫu nhiên.

Ma trận môn là một ma trận với các cột là các hớp học, các hàng là

các tiết học đƣợc sắp xếp theo thứ tự.

Ví dụ: Các lớp đƣợc xếp:

10A1, 10A2...

11A1, 11A2...

12A1, 12A2...tùy thuộc vào số lớp của nhà trƣờng.

Số tiết học đƣợc xếp: 1, 2, ...29.

Bảng 3.2. Ma trận TKB mà kiến xây dựng

1 2 ... 28 29

Chào cờ Văn ... Sử 10A1 Sinh hoạt

10A2 Chào cờ Sinh hoạt

... ... Sinh hoạt

11A1 Chào cờ Sinh hoạt

11A2 Chào cờ Sinh hoạt

... Chào cờ Sinh hoạt

12A1 Chào cờ Sinh hoạt

12A2 Chào cờ Sinh hoạt

... Chào cờ Sinh hoạt

Các con kiến sẽ xây dựng một lời giải cho riêng mình bằng cách ghi

nhớ bảng 3.2 trong quá trình lựa chọn môn học để điền vào bảng. hi đi

xây dựng lời giải, tiết thứ nhất của của tất cả các lớp học sẽ đƣợc cố định là

tiết chào cờ, tiết thứ năm của ngày thứ bảy sẽ là tiết sinh hoạt. Các tiết còn

lại sẽ đƣợc xây dựng nhƣ sau: Các kiến nhân tạo sẽ đi xây dựng lời giải

bằng cách điền ngẫu nhiên các môn học lên các ô còn lại của bảng 3.2. theo

thứ tự từ cột 2 đến cột 28. Quá trình này diễn ra liên tục cho đến khi các

kiến có thể điền hết các môn học cho tất cả các lớp học lên ma trận đó.

Trong trƣờng hợp các kiến không điền đƣợc các môn học lên toàn bộ ma

trận thì quá trình này sẽ đƣợc dừng lại.

Bƣớc 2 Xét lời giải tốt.

Sau khi kết thúc quá trình xây dựng lời giải của mỗi kiến, thì lời giải

tốt nhất của kiến k (k 1..m) sẽ đƣợc lựa chọn làm phƣơng án cập nhật vết

mùi.

Bƣớc 3 Tăng vết mùi cho lời giải tốt ( Cập nhật mùi ).

Dựa trên lời giải tìm đƣợc, đàn kiến sẽ thực hiện cập nhật mùi theo

cách học tăng cƣờng.

Trong đó: : hệ số bay hơi tỷ lệ lƣợng mùi bị bay hơi), là hằng số

thuộc khoảng (0,1).

{

. Trong đó kí hiệu là Chọn = 1 và

lời giải tốt nhất các kiến tìm đƣợc cho tới lần lặp thứ t. Nếu kí hiệu hiểu là lời giải tốt nhất trong bƣớc lặp thứ t. Nếu không tốt hơn

ta có , lúc này sẽ quan tâm tới lời giải gần đúng

Quá trình này sẽ đƣợc thực hiện lặp liên tục cho đến khi gặp các điều

kiện dừng:

1. Tại bƣớc lặp thứ t, tồn tại một kiến xây dựng đƣợc lời giải tốt ƣu

(xây dựng đƣợc TKB cho toàn bộ các lớp của các khối). Lúc này lời giải tối

ƣu này sẽ đƣợc chọn làm T B cho toàn trƣờng.

2. Vƣợt quá thời gian quy định (>5 phút) mà các con kiến vẫn không

xây dựng đƣợc lời giải tối ƣu thì thuật toán sẽ dừng và thông báo: Không

xây dựng đƣợc thời khóa biểu.

3.2.1. Xây dựng hệ thống

Hệ thống đƣợc xây dựng dựa trên thuật toán ACO sử dụng ngôn ngữ

lập trình PHP….

Các chức năng chính của hệ thống:

Đăng nhập vào hệ thống.

Quản lý, lƣu trữ các thông tin về học sinh, lớp, giáo viên, môn học:

Thêm mới, cập nhật, xóa.

Xếp lịch: Thực hiện thuật toán ACO để xếp thời khóa biểu.

Hiển thị kết quả: Sau khi xếp lịch xong hệ thống hiển thị kết quả

ngay trên website và mỗi giáo viên, mỗi lớp học đều có thể xem lịch học

riêng của mình.

Mô hình biểu diễn các chức năng của hệ thống:

S1: Dữ liệu đầu vào cho hệ thống, bao gồm các thông tin về học sinh,

giáo viên, môn học.

S2: Thực hiện thuật toán ACO để xếp thời khóa biểu.

S3: Ngƣời dùng yêu cầu hiển thị các kết quả, hệ thống trả về các kết

quả: Thời khóa biểu toàn trƣờng, thời khóa biểu của từng giáo viên, thời

khóa biểu của từng lớp, và hiển thị các kết quả này ra ngoài màn hình.

S4, S5, S6: Các chức năng tự động kết nối với cơ sở dữ liệu.

Hình 3.2: Chức năng của hệ thống

Bảng 3.3. Bảng dữ liệu phân công giảng dạy theo khối

Mã khối Tên khôi Mô tẩ Môn học Số tiết .....

K12 hối 12 Toán 4 .....

Ban KHTN

K12 hối 12 Lý 3 .....

Ban KHTN

K12 hối 12 Hóa 3 .....

Ban KHTN

K12 hối 12 Sinh 2 .....

Ban KHTN

K11 hối 11 Toán 3 .....

Ban Cơ bản

K11 hối 11 Hóa 2 .....

Ban Cơ Bản

K11 hối 11 Sinh 2 .....

Ban Cơ Bản

K10 hối 10 Ban XH Văn 4 .....

K10 hối 10 Ban XH Sử 3 .....

K10 hối 10 Ban XH Địa 2 .....

..... ..... ..... ..... ..... .....

Bảng 3.4. Bảng dữ liệu phân công giảng dạy theo lớp

Lớp

Toan

Vat ly

Sinh học Hoa hoc

Tin hoc Van hoc

...

Lan1(4)

Quân1(2) Quyền(2) Đoàn(2)

Thái(5)

...

2A1

Ngọc2(2) Đoàn(2)

Thái(5)

...

Hiếu1(4)

2A2

Tĩnh(4)

Hương1(2 ) Nga(2)

Chuyên(1) Hương2(2

Lan2(2)

Thảo2(3)

...

1A1

Ninh(3)

Hường(2) Nga2(1)

Lan2(2) Hà van(3)

...

) Đức(2)

1A2

Ninh(3)

Tú1(2)

Nga2(1)

Đoàn(2)

Trung(3)

...

0A1

Lan1(4)

Ngân(2)

Chuyên(1) Lưu(2)

Hương(3)

...

0A2

...

Chuân(2 ) Chuân(2 ) ...

...

Bảng 3.5. Bảng dữ liệu phân công giảng dạy theo giáo viên

Khoi 10

Khoi 11

Khoi 12

Nguyễn T.Hồng Hạnh

1A2(4), 1A9(3)

Tô Thị Thoa

Nguyễn Phương Hằng

2A8(4), 2A9(4)

Nguyễn Minh Ngọc

0A8(3), 0A12(3)

Bùi Thị Thúy Hà

2A10(4), 2A11(4)

Bùi T. Lan Anh

0A9(3)

2A1(5), 2A3(5)

Lưu T.Thu Hoài

1A1(4), 1A7(3)

Nông Thị Mai

2A4(5)

Phùng Thị Oanh

1A6(3)

2A5(4), 2A6(4)

Phạm Thị Lan

0A2(4), 0A11(3)

Lại T.Quỳnh Nguyên

2A2(5)

1A10(3), 1A12(3)

Nguyễn Việt Hà

1A3(4), 1A4(4)

2A7(4)

Dương Văn Sáng

0A1(4)

Ng Ngọc Tĩnh

0A4(4)

1A11(3)

Vũ Thanh Hiếu

0A7(3), 0A14(3)

Đỗ Thùy Ninh

0A5(3), 0A6(3), 0A13(3)

......................

..................

........................

...........

Tên giáo viên

3.2.2. Đánh giá khả năng ứng dụng giải quyết bài toán xếp thời khóa

biểu

Hệ thống quản lí đào tạo trƣờng phổ thông Vùng cao Việt Bắc nhằm

mục đích tạo một hệ thống quản lý việc đào tạo niên chế bao gồm các phân

hệ sau:

- Phân hệ Quản lý Giáo viên: quản lý thông tin giáo viên...

- Phân hệ Quản lý kế hoạch đào tạo: quản lý hệ đào tạo, loại hình đào

tạo, ngành đào tạo.

- Phân hệ Phân công giảng dạy_TKB: xếp thời khóa biểu cho học

sinh tự động có hỗ trợ bằng phƣơng pháp thủ công, xếp thời khóa biểu

giảng dạy cho giáo viên.

- Phân hệ Quản lý hệ thống: Mỗi ngƣời dùng sẽ có một tài khoản sử

dụng (gồm Username và password) để đăng nhập tùy theo chức vụ và

quyền hạn.

- Ưu, nhược điểm của thuật toán

+ Các tiêu chí xây dựng thuật toán căn cứ thực tế công việc xếp lịch,

mô phỏng lại quá trình xếp lịch thời khóa biểu.

+ Thuật toán đáp ứng đƣợc công việc xếp lịch thực tế tại trƣờng phổ

thông Vùng cao Việt Bắc, quá trình xếp lịch hoàn toàn tự động và xử lý

đƣợc những trƣờng hợp phức tạp.

+ Đánh giá đƣợc mức ƣu tiên thứ tự xếp các lớp học phần.

+ Tuy nhiên thuật toán chƣa xây dựng đƣợc hết các phƣơng án tối ƣu.

Các vấn đề về tài nguyên cần phải đƣợc nghiên cứu sâu, rộng hơn để đáp

ứng đƣợc công việc xếp thời khóa biểu thực tế một cách linh hoạt, triển

khai đƣợc thời khóa biểu cho hoạt động dạy và học.

- So với một số thuật toán lập lịch khác:

+ So với mức độ của các thuật toán di truyền, thuật toán Tabu

search… thì việc mô tả của thuật toán còn đơn giản do vậy cần phải tiếp tục

nghiên cứu để cải tiến các hàm đánh giá để nâng cao hiệu quả công việc

xếp thời khóa biểu.

+ Các thuật toán lập lịch khác nêu ý tƣởng xây dựng các phƣơng pháp

tối ƣu, nhƣng thực tế độ khó của bài toán xếp thời khóa biểu không hoàn

toàn nằm ở giải thuật, mà phụ thuộc rất lớn vào tài nguyên nên vẫn không

có kết quả xếp đƣợc 100%. Điều đó khẳng định các thuật toán chƣa giải

quyết đƣợc tất cả các công việc xếp thời khóa biểu mà vẫn cần có các biện

pháp xử lý về nghiệp vụ, chuyên môn.

3.4. Thiết kế chƣơng trình.

Bƣớc 1- Xác định Danh sách các thuộc tính:

Mã Giáo viên

Tên giáo viên

Mã học sinh

Tên học sinh

Ngày sinh

Mã lớp

Tên lớp

Sĩ số

Mã môn học

Tên môn học

Mã khối

Tên khối

Đặc trƣng khối

Tiết

Thứ

Số tiết học của môn theo khối

Bƣớc 2- Xác định Các thực thể:

E1-GIAOVIÊN

#Mã Giáo viên

Tên giáo viên

E2-HOCSINH

#Mã học sinh

Tên học sinh

Họ đệm

Ngày sinh

Gioitinh

E3-LOP

#Mã lớp

Tên lớp

Sĩ số

E4-MONHOC

#Mã môn học

Tên môn học

E5-KHOI

#Mã khối

Tên khối

Đặc trƣng khối

Bƣớc 3- Xác định các mối quan hệ:

Giữa MONHOC và KHOI có mối quan hệ N-N:

N-N

R1 số tiết

KHOI MONHOC

Giữa GIAOVIEN và LOP có mối quan hệ THOIKHOABIEU cấp N-N:

N-N

LOP GIAOVIEN TKB Tiết Thứ

Giữa GIAOVIEN, CHUNHIEM và LOP có mối quan hệ 1-N:

GIAOVIEN (CN)

CHUNHIEM

1-N

LOP

Một giáo viên chỉ dạy 1 môn:

1-N

DẠY MON GIAOVIEN

THUỘC

LOP

HOCSINH

Một học sinh chỉ thuộc 1 lớp:

Một lớp chỉ trong 1 khối

1-N

KHOI TRONG LOP

C N

∞

Bƣớc 4- Xây dựng mô hình khái niệm dữ liệu:

HOCSINH

LOP

∞

GV #MaGV TênGV

#MaLop Tên lop Sĩsố

TKB thứ tiết

Thuoc

#MaHS Hodem Ten Ngaysinh Gioitinh

∞

Trong

DAY

∞

KHOI

MONHOC

∞

#MaMon TênMon

#MaKhoi TenKhoi ĐặctrungKhoi

MON- KHOI số tiết tiết

Bƣớc 5- Xác định Mô hình quan hệ

Từ mô hình khái niệm chuyển sang mô hình quan hệ :

1-GV(MaGV, TênGV, Mamôn)

2-MONHOC(Mamôn, tênmôn)

3-LOP(Mãlop, tênlop, siso, Makhoi, MãGVCN)

4-KHOI(makhoi, tênkhoi)

5-HOCSINH(MaHS, hodem, ten, ngaysinh. gioitinh, Malop)

6-MON-KHOI(Mamon, Makhoi, Số tiết)

7-TKB(MaGV, Thu, Tiết, Malop)

Bƣớc 6- Chuẩn hóa mô hình quan hệ đến 3 NF

Cả 7 lƣợc đồ trên đều đạt 3NF

Bƣớc 7- Đặc tả thiết kế CSDL mức logic

Từ kết quả bƣớc 6 chuyển thành Sơ đô THỰC THỂ_Mối quan hệ :

∞ 1 HOCSINH TKB LOP GV

1 ∞ 1 ∞ ∞ 1

#MaGV TênGV MaMon

#MaGV #Thứ #Tiết MaLop

#MaLop Tên lop Sĩsố MaKhối MaGV(CN) #MaHS Hodem Ten Ngaysinh Gioitinh MaLop

∞ ∞

1 1

∞

MONHOC KHOI MON-KHOI

#MaMon TênMon

#MaKhoi TenKhoi ĐặctrungKhoi #MaMon #MaKhoi Số tiết

Hình 3.3 Mô hình cơ sở dữ liệu

Khi tạo một lịch lớp học chúng ta cần xem xét đến rất nhiều các yêu

cầu về số lƣợng giáo viên, học sinh, số lớp học, phòng học và nhiều yếu tố

khác. Các yêu cầu này có thể đƣợc chia thành nhiều nhóm tuỳ theo tầm

quan trọng của chúng. Các yêu cầu bắt buộc (nếu vi phạm một trong những

yêu cầu này, lịch học sẽ thành vô hiệu, bất khả thi)

- Lớp chỉ có thể diễn ra trong phòng học

- Không giao viên hay một lớp nào có thể ở nhiều lớp học cùng một lúc

- Lớp học phải đủ chỗ cho tất cả học sinh ( số lƣợng học sinh của một

lớp đƣợc xếp vào lớp đó ).

Một số yêu cầu không bắt buộc nếu vi phạm lịch học vẫn khả thi:

- Thời gian học của lớp đƣợc tiên cho giáo viên

- Phòng học có thể do giáo viên chọn

- Phân bổ (thời gian hoặc không gian) của các lớp học dành cho các

lớp hoặc giáo viên.

Các yêu cầu bắt buộc hoặc không bắt buộc của khối học tùy thuộc vào

hoàn cảnh cụ thể. Trong hệ thống lập lịch thời khóa biểu này chỉ đề cập đến

những yêu cầu bắt buộc.

3.4.1. Lớp học

Mỗi học sinh nằm trong một lớp học đƣợc cấp một mã riêng cho lớp dùng

để phân biệt các lớp với nhau, đồng thời mã lớp này cũng đƣợc dùng làm tên tài

khoản đăng nhập vào hệ thống cho mỗi lớp học và chỉ có học sinh của lớp đó

biết mật khẩu.

Các thông tin quản lý học sinh: Mã học sinh, họ và tên, ngày sinh giới

tính, ngày sinh, địa chỉ.

Học sinh đăng nhập vào hệ thống bằng tài khoản theo lớp đã đƣợc cấp

(Tên tài khoản chính là mã lớp học) sau khi đăng nhập, tài khoản của lớp

học sinh có thể theo dõi đƣợc thời khóa biểu của lớp mình đang học.

3.4.2. Giáo viên

Mỗi giáo viên cũng đƣợc cấp một mã giáo viên, đồng thời mã giáo

viên này dùng để đăng nhập vào hệ thống thông qua tài khoản của mỗi giáo

viên và đƣợc quyền sử dụng các chức năng: Xem lịch dạy của cá nhân.

3.4.3. Phòng học

Phần phòng học chứa ID và tên của phòng học, phòng học này là cố định.

3.4.4. Nhân viên phòng đào tạo

Tài khoản của nhân viên phòng đào tạo sau khi đăng nhập vào hệ

thống đƣợc cấp quyền sử dụng các chức năng của hệ thống:

Thêm mới, cập nhật, xóa thông tin học sinh

Thêm mới, cập nhật, xóa thông tin lớp học

Thêm mới, cập nhật, xóa thông tin giáo viên

Thêm mới, cập nhật, xóa thông tin về môn học

Xếp thời khóa biểu toàn trƣờng.

3.4.5 Mô hình ca sử dụng

Hình 3.4: Mô hình các ca sử dụng

3.5. Các chức năng chính của chƣơng trình

- Đăng nhập.

- Chức năng quản lý học sinh.

- Chức năng quản lý giáo viên.

- Chức năng quản lý lớp học.

- Chức năng quản lý môn học.

Hình 3.5: Giao diện của chương trình

3.5.1. Chức năng đăng nhập ( chức năng quản lý user )

- Thông tin vào. Nhập tài khoản và mật khẩu.

Mỗi ngƣời dùng sẽ có một tài khoản sử dụng (gồm Username và

password) để đăng nhập tùy theo chức vụ và quyền hạn.

- Thông tin ra: Kết quả đăng ký.

Hình 3.6: Giao diện đăng nhập

3.5.2. Chức năng Quản lý môn học

Là chức năng để quản lý các thông tin cần về môn học nhƣ: thêm môn

học, chỉnh sửa môn học và xóa môn học. Chức năng quản lý môn học bao

gồm các nút chức năng: thêm môn, chỉnh sửa môn, xóa môn học. Có thể

điều chỉnh thêm các môn học, sửa đổi các môn học, cũng nhƣ xóa bỏ môn

học sao cho phù hợp theo quy định của Bộ Giáo Dục và Đào Tạo.

Hình 3.7: Mô hình chức năng quản lý môn học

- Nút thêm môn học:

Nút thêm môn dùng để thêm môn học nếu cần thiết. Với quy định của

Bộ Giáo Dục và Đào Tạo thì số môn học của trƣờng Phổ thông Vùng cao

Việt Bắc là 13 môn bao gồm các môn: Toán, Vật lý, Hóa học, Sinh học,

Lịch sử, Văn học, Địa lý, Tin học, Tiếng anh, Thể dục, Giáo dục quốc

phòng, Giáo dục công dân, Công nghệ. Ngƣời quản trị thực hiện nhập mã

môn học, tên môn rồi thực hiên thêm môn tại nút thêm.

Mô tả: Thêm các thông tin cần thiết.

- Thông tin vào: Thêm thông tin cần thiết về môn.

- Thông tin ra: Thông tin đã đƣợc thay đổi

Hình 3.8: Giao diện thêm môn học

- Nút chỉnh sửa môn:

Tại đây ngƣời quản trị có thể dùng nút chỉnh sửa môn chỉnh sửa các

môn học để phù hợp với quy định của Bộ Giáo Dục và Đào Tạo cho từng

cấp học và từng khối. Đối với khối 10, khối 11, khối 12 thì số môn học là

khác nhau do vậy cần chỉnh sửa các môn cho phù hợp.

Mô tả: Chỉnh sửa các thông tin cần thiết.

- Thông tin vào: Thêm, bớt thông tin cần thiết về môn.

- Thông tin ra: Thông tin đã đƣợc thay đổi

Hình 3.9:Giao diện chỉnh sửa môn

- Nút xóa môn:

Để xóa các môn học khi cần thiết, nếu môn học đó không có trong quy

định của Bộ Giáo Dục và Đào Tạo hoặc cần có sự thay đổi thay đổi. Tại

mỗi học kỳ, sự thay đổi các môn học, số tiết là cần thiết để phù hợp cho các

khối tùy theo đặc thù của từng trƣờng.

3.5.3. Chức năng Quản lý giáo viên

Chức năng quản lý giáo viên là chức năng để quản lý các thông tin

cần thiết về các giáo viên nhƣ: Tên giáo viên, tuổi, chuyên môn giảng dạy...

và bao gồm các nút chức năng nhƣ: Thêm giáo viên, chỉnh sửa, xóa, thời

khóa biểu.

Hình 3.10: Mô hình chức năng quản lý giáo viên

- Nút thêm giáo viên:

Nút thêm giáo viên dùng để ngƣời quản trị có thể cập nhập thêm giáo

viên cũng nhƣ các thông tin về giáo viên nhƣ: Mã giáo viên, Họ tên, Bộ

môn giảng dạy. Để thêm một giáo viên mới theo yêu cầu ngƣời quản trị chỉ

cần nhập những thông tin nhƣ: Mã giáo viên, Họ tên giáo viên và bộ môn

giảng dạy về giáo viên cần thêm vào danh sách.

Mô tả: Thêm thông tin về giáo viên cần đƣợc cập nhật.

- Thông tin vào: Thêm thông tin cần thiết về giáo viên.

- Thông tin ra: Thông tin đã đƣợc thay đổi

Hình 3.11:Giao diện thêm giáo viên

- Nút chỉnh sửa:

Tại nút chức năng chỉnh sửa ngƣời quản trị có thể thay đổi các thông

tin về các giáo viên: Mã giáo viên, Họ tên giáo viên, Bộ môn giảng dạy.

Mô tả: Thay các thông tin cần sửa đổi.

- Thông tin vào: Chỉnh sửa các thông tin cần thiết.

- Thông tin ra: Thông tin đã đƣợc thay đổi

Hình 3.12:Giao diện chỉnh sửa

- Nút thời khóa biểu:

Các giáo viên có thể sử dụng nút Thời khóa biểu để xem thời khóa

biểu đƣợc phân công giảng dạy cụ thể trong tuần sau khi đã đƣợc ngƣời

quản trị xếp lịch.

Mô tả: Giáo viên có thể tra cứu thông tin cần thiết.

- Thông tin đầu vào: Tra cứu thời khóa biểu theo tên bằng tài khoản cá

nhân.

- Thông tin đầu ra: Kết quả thời khóa biểu cụ thể của giáo viên.

Hình 3.13:Giao diện thời khóa biểu của từng giáo viên

- Nút xóa

Nút chức năng xóa này dùng để xóa thông tin của giáo viên khỏi danh

sách khi cần thiết.

3.5.4. Chức năng Quản lý học sinh:

Ngƣời quản trị Ngƣời làm công tác quản lý của phòng đào tạo ) có

thể thêm học sinh vào các lớp học cũng nhƣ đăng nhập hay chỉnh sửa các

thông tin có liên quan cho các học sinh nhƣ: Mã học sinh, Họ và Tên...

Hình 3.14: Chức năng Quản lý học sinh

- Nút thêm học sinh vào danh sách lớp:

Với chức năng thêm học sinh vào danh sách còn thiếu của các lớp hay

bổ sung thêm các học sinh mới thì ngƣời quản trị sẽ cập nhật tại nút thêm

học sinh bằng cách đƣa các thông tin cần thiết nhƣ: Mã học sinh, Họ và

Tên, Ngày sinh, lớp học.

Mô tả: Thêm các thông tin cần thiết.

- Thông tin vào: Thêm thông tin cần thiết về học sinh.

- Thông tin ra: Thông tin đã đƣợc thay đổi

Hình 3.15:Cập nhật thông tin học sinh

- Nút chỉnh sửa:

Tại nút chỉnh sửa ngƣời quản trị có thể thay đổi các thông tin cần thiết

về các học sinh nhƣ ngày tháng năm sinh, tên tuổi địa chỉ,lớp học...

Mô tả: Thêm các thông tin cần thiết.

- Thông tin vào: Chỉnh sửa thông tin cần thiết về học sinh.

- Thông tin ra: Thông tin đã đƣợc thay đổi

Hình 3.16: Cập nhật lại thông tin học sinh

- Nút xóa:

Nút này dùng để xóa thông tin của học sinh khỏi danh sách lớp

3.5.5. Chức năng Quản lý lớp học

Với quyền quản trị phòng đạo tạo) thì có thể sử dụng nút sắp xếp thời

khóa biểu để xếp thời khóa biểu cho toàn trƣờng. Chức năng quản lý này bao

gồm các chức năng: Chỉnh sửa, xóa, môn học, thời khóa biểu.

Hình 3.17: Mô hình chức năng quản lý lớp học

- Nút môn học:

Nút chức năng môn học dùng với chức năng nhập các môn học cho

từng khối, từng lớp cùng với số tiết của môn đó trong tuần và cũng có thể

chỉnh sửa môn, xóa môn theo yêu cầu thực tế của nhà trƣờng.

Hình 3.18: Giao diện môn học

- Nút thời khóa biểu:

Sau khi ngƣời quản trị xếp thời khóa biểu cho toàn trƣờng, các lớp có

thể xem thời khóa biểu của lớp mình bằng cách, sử dụng nút chức năng

thời khóa biểu và tài khoản để truy cập và xem thời khóa biểu.

Mô tả: Các lớp có thể tra cứu thông tin cần thiết.

- Thông tin đầu vào: Tra cứu thời khóa biểu theo lớp bằng tài khoản.

- Thông tin đầu ra: Kết quả thời khóa biểu cụ thể của lớp.

Hình 3.19: Kết quả xếp thời khóa biểu theo lớp

- Nút chỉnh sửa:

Để phù hợp với những yêu cầu cần thiết.Tại nút chỉnh sửa ngƣời quản

trị có thể chỉnh sửa các thông tin liên quan đến các học sinh nhƣ mã lớp,

tên lơp, sĩ số, khối lớp.

Mô tả: Thêm các thông tin cần thiết.

- Thông tin vào: Chỉnh sửa thông tin cần thiết về lớp.

- Thông tin ra: Thông tin đã đƣợc chỉnh sửa, thay đổi

Hình 3.20: Cập nhật thông tin lớp

- Nút xóa:

Nút đƣợc dùng để xóa một lớp khỏi danh sách lớp học

3.6. Kết quả thử nghiệm

Việc ứng dụng thuật toán ACO đã giải quyết đƣợc bài toán xếp thời

khóa biểu cho trƣờng phổ thông Vùng cao Việt Bắc.

Bằng việc ứng dụng công nghệ WEB PHP sử dụng xampp,....đã xây

dựng hệ thống website xếp thời khóa biểu cho phòng đào tạo.

Nhận xét về chƣơng trình

- Ƣu điểm:

+ Đƣợc cài đặt bằng ngôn ngữ PHP nên dễ cài triển khai trên các hệ

thống website của các trƣờng

+ Tốc độ sắp xếp lịch nhanh

+ Giao diện thân thiện, dễ sử dụng

+ Tính an toàn và bảo mật của hệ thống là tƣơng đối tốt qua việc thể

hiện việc đăng nhập của từng giáo viên và học sinh.

- Nhƣợc điểm:

+ Chƣa xử lý cho toàn bộ các trƣờng và các mô hình đạo tạo từ hệ trung

cấp, cao đẳng và đại học theo chƣơng trình hiện hành.

KẾT LUẬN

Luận văn đã tìm hiểu về cơ sở lý thuyết, và đề xuất phƣơng pháp giải

bài toán xếp thời khóa biểu trƣờng phổ thông là giải thuật tối ƣu hóa đàn

kiến.

Phƣơng pháp tối ƣu đàn kiến là phƣơng pháp tƣơng đối mới mẻ và tỏ

ra đặc biệt hiệu quả, điều này đã đƣợc chứng minh thông qua thực nghiệm.

Phƣơng pháp tối ƣu đàn kiến luôn đƣợc quan tâm, phát triển kể từ khi giới thiệu

cho đến nay thể hiện qua sự phong phú, đa dạng của các thuật toán. Các thuật

toán trực tiếp đƣa ra hƣớng tiếp cận mới giải các bài toán tối ƣu tổ hợp, qua đó

có nhiều ứng dụng trong thực tiễn trên các lĩnh vực nhƣ: Sản xuất, truyền

thông, sinh học, hoạt động xã hội …..

Bài toán xếp thời khóa biểu là một trong những bài toán khó, đƣợc đề

xuất từ lâu, đƣợc đầu tƣ nghiên cứu, phát triển một cách nghiêm túc và có

nhiều ứng dụng thực tế, đặc biệt là trong các quá trình tự động xếp thời

khóa biểu trong ngành giáo dục vào nhiều ngành khác nhau trong thực tế.

Việc sử dụng phƣơng pháp tối ƣu đàn kiến để giải bài toán xếp thời khóa

biểu đƣợc đề xuất với thuật toán ACO, nó có kết quả tốt hơn rất nhiều.

Luận văn đã xây dựng đƣợc chƣơng trình xếp thời khóa biểu tự động

cho trƣờng phổ thông Vùng cao Việt Bắc dựa trên các ràng buộc và tài

nguyên của trƣờng.

HƢỚNG PHÁT TRIỂN

Đối với thuật toán ACO giải bài toán có không gian tìm kiếm rộng

nên kết quả chƣa đƣợc thực sự tốt. Các bƣớc tiếp theo của thuật toán ACO

có thể đƣợc thiết kế và áp dụng vào các kỹ thuật trình độ cao hơn, chúng ta

thấy rằng phƣơng pháp tối ƣu đàn kiến hết sức phong phú, đa dạng, là một

hƣớng tiếp cận mới, mạnh mẽ và triển vọng còn có khả năng khai thác

nghiên cứu và cải tiến mạnh hơn nữa trong tƣơng lai.

Trong phạm vi nghiên cứu của đề tài, thuật toán và chƣơng trình áp

dụng cho bài toán xếp thời khóa biểu là đặc thù riêng của trƣờng Phổ thông

Vùng cao Việt Bắc. Hƣớng phát triển tiếp theo sẽ mở rộng cho mô hình bài

toán xếp thời khóa biểu của hầu hết các trƣờng phổ thông theo các cấp học

và hƣớng đến cho mô hình các trƣờng trung cấp, cao đẳng và đại học, theo

cả hệ niên chế và tín chỉ đang áp dụng hiện nay.

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Đỗ Đức Đông và Hoàng Xuân Huấn 2011), “Về biến thiên

của vết mùi trong phƣơng pháp ACO và các thuật toán mới”, Tạp

chí Tin học và điều khiển học, T.27, tr. 263-275.

Tiếng Anh

Christine Solnon (2008), Combining two Pheromone Structures

[2] forSolving the Car Sequencing Problem with AntColony

Optimization, Preprint submitted to Elsevier Science

[3] M. Dorigo, V. Maniezzo and A. Colorni (1991), The Ant System:

An autocatalytic optimizing process, Technical Report 91-016

Revised, Dipartimento di Elettronica, Politecnico di Milano,

Milano, Italy.

[4] Marco Dorigo and Thomas Stützle, 2004, Ant Conoly

Optimization, A Bradford Book, The MIT Press, Cambridge,

Massachusetts, London, England.

[5] T. Stützle, H. H. Hoos (2000). An analytical upper bound on the

minimum number of recombinations in the historyof SNP

sequences in populations. Information Processing Letters,

109(9):427- 431, 2009

[6] Zhaojun Zhang, Zuren Feng (2011), Two-Stage updating

Pheromone for Invariant Ant Colony Optimization algorithm,

Expert System with Applications, Published by Elsevier Ltd

Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu bài toán lập lịch và ứng dụng xếp thời khóa biểu cho trường phổ thông vùng cao Việt Bắc

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

HOÀNG PHÚC LỢI

NGHIÊN CỨU BÀI TOÁN LẬP LỊCH VÀ

ỨNG DỤNG XẾP THỜI KHÓA BIỂU CHO

TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

HOÀNG PHÚC LỢI

NGHIÊN CỨU BÀI TOÁN LẬP LỊCH VÀ

ỨNG DỤNG XẾP THỜI KHÓA BIỂU CHO

TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Ngƣời hƣớng dẫn khoa học: TS. TRƢƠNG HÀ HẢI

DANH MỤC BẢNG BIỂU

Lớp

Toan

Vat ly

Sinh học Hoa hoc

Tin hoc Van hoc

...

Khoi 10

Khoi 11

Khoi 12

#MaLop Tên lop Sĩsố

#MaHS Hodem Ten Ngaysinh Gioitinh

#MaMon TênMon

#MaKhoi TenKhoi ĐặctrungKhoi

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Kháo luận tốt nghiệp: Vận dụng lí thuyết học tập trải nghiệm vào dạy học Thống kê - Xác suất ở lớp Hai

Luận văn Thạc sĩ: Xây dựng hệ thống điều khiển và thu nhận dữ liệu cho Robot dịch vụ

Luận văn Thạc sĩ: Thế giới nhân vật trong truyện ngắn Lê Minh Khuê sau năm 1975

Luận văn Thạc sĩ: Tác động của cấu trúc vốn đến hiệu quả hoạt động của các ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Kiểm soát rủi ro tín dụng bán lẻ tại Ngân hàng Thương mại Cổ phần Đầu tư và Phát triển Việt Nam chi nhánh Thủ Thiêm

Luận văn Thạc sĩ: Các yếu tố ảnh hưởng đến hiệu quả kinh doanh của ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Các nhân tố ảnh hưởng đến hành vi sử dụng dịch vụ ngân hàng điện tử tại Ngân hàng Thương mại Cổ phần Ngoại thương Việt Nam – Chi nhánh Thủ Đức

Luận văn Thạc sĩ: Các yếu tố tác đồng đến nợ xấu tại Ngân hàng Nông nghiệp và Phát triển Nông thôn - Chi nhánh Tiền Giang

Luận văn Thạc sĩ: Yếu tố ảnh hưởng đến quyết định sử dụng dịch vụ thanh toán không dùng tiền mặt tại Ngân hàng TMCP Công thương Việt Nam (Vietinbank)

Luận văn Thạc sĩ tóm tắt: Pháp luật về du lịch biển, thực tiễn tại tỉnh Bình Định

Luận văn Thạc sĩ: Ảnh hưởng của các yếu tố thương hiệu với vai trò trung gian của Marketing truyền miệng đến quyết định chọn việc làm của nhân viên GenZ tại chuỗi nhà hàng gà rán Popeyes khu vực Thành Phố Hồ Chí Minh

Luận văn Thạc sĩ: Ảnh hưởng của Marketing mix đến ý định học cao học của sinh viên khối ngành kinh tế thuộc Trường Đại học Công nghệ Thành phố Hồ Chí Minh

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA