ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
 

NGUYỄN ĐỨC VIỆT

GIẢI BÀI TỐN LẬP LỊCH THEO TÍN CHỈ SỬ
DỤNG GIẢI THUẬT TÌM KIẾM TABU

LUẬN VĂN THẠC SĨ CƠNG NGHỆ THÔNG TIN

Hà Nội – 2014

LUAN VAN CHAT LUONG download : add


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
 

NGUYỄN ĐỨC VIỆT

GIẢI BÀI TỐN LẬP LỊCH THEO TÍN CHỈ SỬ
DỤNG GIẢI THUẬT TÌM KIẾM TABU
Nghành:
Chun nghành:
Mã số:

Cơng nghệ thơng tin
Kỹ thuật phần mềm
60480103

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. LÊ NGUYÊN KHÔI

Hà Nội – 2014

LUAN VAN CHAT LUONG download : add


Lời cảm ơn
Đầu tiên, tôi xin chân thành cảm ơn TS. Lê Nguyên Khôi đã tận tâm hướng
dẫn chỉ bảo và giúp đỡ tơi hồn thành đề tài luận văn này. Một lần nữa, em xin
chân thành cảm ơn thầy.
Với lịng biết ơn sâu sắc nhất, tơi xin gửi đến q thầy cơ ở khoa Cơng nghệ
Thơng tin, phịng Đào tạo trường Đại học Công nghệ – Đại học Quốc gia Hà Nội
đã tạo điều kiện thuận lợi, dồn bao công sức tâm huyết để truyền đạt vốn kiến thức
quý báu cho các học viên cao học như tôi trong suốt thời gian học tập tại trường.
Tôi cũng xin gửi lời cám ơn đến gia đình, bạn bè và đồng nghiệp, những
người đã luôn bên tôi, động viên và khuyến khích tơi trong q trình thực hiện đề
tài nghiên cứu của mình.
Tuy đã có những cố gắng nhất định, tiếp cận với thực tế để tìm hiểu và áp
dụng khoa học vào cuộc sống, nhưng do thời gian và trình độ cịn nhiều hạn chế
nên luận văn này khó tránh khỏi các thiếu sót. Kính mong nhận được sự đóng góp ý
kiến của thầy cơ và các bạn.
Sau cùng, tơi xin kính chúc q thầy cơ trong khoa Cơng nghệ Thông tin
cũng như Ban Giám đốc Đại học Công nghệ - Đại học Quốc Gia Hà Nội dồi dào
sức khỏe, niềm tin để tiếp tục thực hiện sứ mệnh cao đẹp của mình là truyền đạt
kiến thức cho thế hệ mai sau.
Trân trọng.

Hà Nội, ngày 11 tháng 08 năm 2014
Học viên

Nguyễn Đức Việt

LUAN VAN CHAT LUONG download : add


4

Lời cam đoan

Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là
trung thực và không trùng lặp với các đề tài khác của cá nhân tôi, được thực hiện
dưới sự hướng dẫn khoa học của Tiến sĩ Lê Nguyên Khôi.
Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này
đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc
Học viên

Nguyễn Đức Viêt

LUAN VAN CHAT LUONG download : add


MỤC LỤC

Lời cảm ơn ........................................................................................................................... 3
 
Lời cam đoan ........................................................................................................................ 4
 

MỤC LỤC ............................................................................................................................ 5
 
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .......................................................... 7
 
DANH MỤC CÁC BẢNG ...................................................................................................8
 
DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ ........................................................................9
 
MỞ ĐẦU ............................................................................................................................ 10
 
1.
  Lý do chọn đề tài: ............................................................................................................... 10
 
2.
  Mục đích nghiên cứu........................................................................................................... 10
 
3.
  Nhiệm vụ nghiên cứu .......................................................................................................... 11
 
4.
  Đối tượng và phạm vi nghiên cứu....................................................................................... 11
 
5.
  Phương pháp nghiên cứu .................................................................................................... 11
 

Chương 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH HIỆN NAY VÀ CÁC CÁCH
TIẾP CẬN .......................................................................................................................... 12
 
1.1 Bài tốn lập thời khóa biểu cho trường phổ thông (School timetabling) ............................. 13

 
1.2 Bài tốn lập thời khóa biểu cho trường đại học (University timetabling) ........................... 13
 
1.3 Bài toán lập lịch thi (Examination timetabling) ................................................................... 14
 
1.4 Bài tốn lập lịch theo tín chỉ ................................................................................................ 15
 
1.5 Ưu điểm của phương thức đào tạo theo tín chỉ .................................................................... 17
 
1.6 Các cách tiếp cận hiện nay ................................................................................................... 18
 

Chương 2: TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP TÌM KIẾM ..................................21
 
2.1 Xung đột tối thiểu (Min-conflict) ........................................................................................ 21
 
2.2 Thuật giải mô phỏng luyện kim (Simulated Annealing) ..................................................... 21
 
2.3 Thuật giải leo đồi (Hill-climbing) ........................................................................................ 22
 
2.4 Tìm kiếm Tabu (Tabu search).............................................................................................. 22
 
2.5 Thuật giải di truyền (Genetic Algorithm) ............................................................................ 23
 

LUAN VAN CHAT LUONG download : add


6
2.6 Kết luận ................................................................................................................................ 23

 

Chương 3: CƠ SỞ TÌM KIẾM TABU ............................................................................... 24
 
3.1 Lược Sử Về Tabu Search ..................................................................................................... 24
 
3.1.1 Giới Thiệu ..................................................................................................................... 24
 
3.1.2 Tabu Search – Một Dạng Meta-heuristic ...................................................................... 25
 
3.1.3 Các Giai Đoạn Phát Triển Của Tabu Search ................................................................. 25
 
3.2 Nguyên Lý Chung Của Tabu Search ................................................................................... 26
 
3.3 Cách Sử Dụng Bộ Nhớ ........................................................................................................ 27
 
3.3.1 Một Minh Họa ............................................................................................................... 28
 
3.4 Chiến Lược Tăng Cường (Intensification) và Chiến Lược Đa Dạng (Diversification) ...... 30
 
3.5 Lập Trình Với Bộ Nhớ Tương Thích (Adaptive Memory Programming)........................... 31
 
3.6 Các Nhân Tố Của Bộ Nhớ Tương Thích ............................................................................. 31
 

Chương 4: BÀI TỐN LẬP LỊCH THEO TÍN CHỈ ......................................................... 33
 
4.1 Các khái niệm ...................................................................................................................... 33
 
4.2 Mơ hình của bài tốn............................................................................................................ 35

 
4.3 Các ràng buộc cứng.............................................................................................................. 36
 
4.4 Các ràng buộc mềm ............................................................................................................. 36
 
4.5 Ví dụ minh họa: ................................................................................................................... 37
 
4.6 Hướng tiếp cận cho bài toán ................................................................................................ 38
 
4.6.1 Bước 1: Khởi tạo lời giải ban đầu ngẫu nhiên .............................................................. 39
 
4.6.2 Bước 2: Cải thiện chất lượng lời giải bằng giải thuật tìm kiếm Tabu ........................... 40
 
4.7 Định dạng tập tin dữ liệu CSV đầu vào: .............................................................................. 44
 
4.8 Khảo sát và thống kê kết quả thực nghiệm thực tế .............................................................. 45
 
4.9 So sánh kết quả thực nghiệm với kết quả của phần mềm Open Course Timetable ............. 47
 

KẾT LUẬN ........................................................................................................................ 49
 
TÀI LIỆU THAM KHẢO ..................................................................................................50
 

LUAN VAN CHAT LUONG download : add


7


DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
STT
1
2
3
4
5
6
7
8
9
10
11
12

Ký hiệu / Chữ viết tắt
AI
AMP
CS
CSP
CSV
GA
LP
MC
MCRW
OR
SA
TS

Dạng đầy đủ / Ý nghĩa

Artificial Intelligent
Adaptive Memory Programming
Constraint Satisfaction
Constraint Satisfaction Problem
Comma-separated values
Genetic Algorithms
Linear Programming
Min-conflict
Min-conflict Random Walk
Operation Research
Simulated Annealing
Tabu Search


 

LUAN VAN CHAT LUONG download : add


8

DANH MỤC CÁC BẢNG
Bảng 1 - Mơ tả cách tính của hàm mục tiêu ........................................................... 38
 
Bảng 2 – Bảng mơ tả ánh xạ tập dữ liệu và mơ hình hệ thống ................................ 45
 
Bảng 3 – Ví dụ ánh xạ từ tập dữ liệu vào mơ hình hệ thống ................................... 45
 
Bảng 4 – Thống kê kết quả thực nghiệm ................................................................. 46
 

Bảng 5 – So sánh giữa phần mềm vTimeTabler và Open Course TimeTabler ....... 47
 

LUAN VAN CHAT LUONG download : add


9

DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ
Hình 1 – Biểu diễn khái niệm bài tốn sắp thời khóa biểu ...................................... 13
 
Hình 2 – Bốn chiều Tabu Search ............................................................................. 28
 
Hình 3 – Bài tốn cây tối ưu minh họa .................................................................... 29
 
Hình 4 – Tăng cường và Đa dạng ............................................................................ 30
 
Hình 5 – Mối quan hệ giữa Giảng viên, Lớp học và Mơn học ................................ 33
 
Hình 6 – Khởi tạo lời giải ngẫu nhiên ban đầu ........................................................ 39
 
Hình 7 – Sơ đồ cài đặt giải thuật.............................................................................. 42
 
Hình 8 – Phép chuyển mới....................................................................................... 43
 
Hình 9 – Biểu đồ minh họa quá trình tìm kiếm lời giải ........................................... 46
 

LUAN VAN CHAT LUONG download : add



10

MỞ ĐẦU
1. Lý do chọn đề tài:
Bài toán lập lịch ln là một bài tốn cổ điển thuộc lớp bài tốn NP-khó. Từ
lâu đã thu hút được sự quan tâm, nghiên cứu và phát triển của nhiều tổ chức giáo
dục, các nhà khoa học bởi tính ứng dụng cao và độ phức tạp của nó. Các bài tốn
lập lịch thường rất phong phú, đa dạng bởi các ràng buộc và yêu cẩu của từng
doanh nghiệp, tổ chức, trường học.
Trong nhiều thập niên qua đã có rất nhiều các phương pháp giải được đưa
ra. Tuy nhiên, tính hiệu quả của lời giải cho lớp bài tốn vẫn cịn nhiều bàn cãi. Bài
tốn lập lịch có thể được dịnh nghĩa là một bài tố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 tài
nguyên nhân lực, vật lực, máy móc và tối thiểu thời gian địi hỏi để hồn thành tồn
bộ quá trình nhằm sắp xếp lịch tối ưu nhất. Vì thế bài tốn lập lịch là một vấn đề rất
khó để giải quyết.
Những năm gần đây, đã có nhiều hướng phát triển phong phú của các giải
thuật nhằm đưa ra lời giải tốt nhất cho bài toán này. Với đề tài “Giải bài tốn lập
lịch theo tín chỉ sử dụng giải thuật tìm kiếm Tabu”, khóa luận mạnh dạn nghiên cứu
một phương pháp mới cho việc giải các bài toán lập lịch cho mơ hình các đơn vị,
các cơ sở đào tạo có hình thức tổ chức, hoạt động giống với các Trung tâm Đào tạo
Chứng chỉ Quốc tế theo Tín chỉ.
2. Mục đích nghiên cứu
Bài tốn lập lịch đã từ lâu trở thành một bài toán nổi tiếng và thu hút được
sự quan tâm của rất nhiều nhà nghiên cứu, nhiều chuyên gia trong các lĩnh vực liên
quan. Sự “nổi tiếng” của bài tốn này khơng chỉ được đo bởi độ phức tạp của vấn
đề, mà cịn ở tính thực tiễn, khả năng áp dụng rất cao trên thực tế. Do đó mục tiêu
của luận văn là: Nghiên cứu kỹ thuật của giải thuật tìm kiếm Tabu cho bài tốn lập

lịch theo tín chỉ.
Luận văn sẽ xem xét áp dụng kỹ thuật này vào việc xây dựng chương trình
lập lịch cho mơ hình một trung tâm đào tạo theo tín chỉ.

LUAN VAN CHAT LUONG download : add


11

3. Nhiệm vụ nghiên cứu
Nghiên cứu, tìm hiểu giải thuật tìm kiếm Tabu và trên cơ sở đó tiếp cận để
giải bài tốn lập lịch, sắp xếp thời khóa biểu cho mơ hình giảng dạy trong các trung
tâm đào tạo theo tín chỉ hiện nay.
4. Đối tượng và phạm vi nghiên cứu
Tìm hiểu bài tốn lập lịch và các hướng giải quyết truyền thống
Tìm hiểu về giải thuật tìm kiếm Tabu
Ứng dụng thuật giải tìm kiếm Tabu vào bài tốn lập lịch
Xây dựng ứng dụng lập thời khóa biểu cho các trung tâm đào tạo theo tín
chỉ
5. Phương pháp nghiên cứu
Dựa trên tài liệu thu thập từ nhiều nguồn (tài liệu, bài báo do giảng viên
hướng dẫn cung cấp, sách, báo, tạp chí, internet…) tổng hợp, phân tích và trình bày
lại theo sự hiểu biết của bản thân
Mở rộng các cách tiếp cận trước đây trên cơ sở phân tích đặc thù bài toán
cần giải quyết để đưa ra những ý kiến, đề xuất cải tiến hợp lý.
Ứng dụng những kết quả dựa trên nghiên cứu trên vào thực tế.
 

LUAN VAN CHAT LUONG download : add



12

Chương 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH HIỆN NAY VÀ CÁC
CÁCH TIẾP CẬN

Bài tốn lập lịch ln là một bài tốn khó, mang tính khoa học đồng thời
tính thực tiễn cũng rất cao. Không chỉ Việt Nam mà trên toàn cầu từ lâu việc lập
lịch đã trở thành một vấn đề có tính thời sự, một bài tốn gây được sự chú ý, quan
tâm của nhiều người.
Bài toán lập thời khóa biểu là một nhánh của bài tốn lập lịch trong đó đưa
ra một chuỗi các sự kiện (thông thường là các môn học, bài giảng hoặc các môn
thi) và bao gồm các giáo viên và học viên trong một khoảng thời gian định trước và
thỏa mãn một tập hợp các ràng buộc của từng loại thời khóa biểu khác nhau.
Mỗi bài tốn có các tính chất riêng, khi sắp lịch thi bài toán đặt ra là phải
đáp ứng được yêu cầu về thời gian (như không được trùng hay quá sát nhau) giữa
các lần thi liên tiếp của cùng một học sinh, sinh viên. Còn khi sắp lịch cho trường
phổ thơng thì chúng ta cần quan tâm giờ rảnh mà giáo viên đăng ký và các tiết
trống giữa giờ học của học sinh đóng vai trị rất quan trọng cho việc đánh giá kết
quả của thời khóa biểu. Đối với đại học, bài toán cần giải quyết cũng là việc tránh
xung đột giữa các thành phần tham gia trong thời khóa biểu (giáo viên, lớp học,
phịng học và thiết bị). Vì thế, mục tiêu cuối cùng của người sắp thời khóa biểu là
tạo ra một thời khóa biểu với ít xung đột nhất.
Cũng đã có các khảo sát về bài tốn sắp thời khóa biểu. Như việc đưa ra
tổng quan các vấn đề về sắp thời khóa biểu thuộc ba dạng ta đã đề cập ở trên của
Schaerf, 1995 [1]. Các khảo sát về sắp lịch thi Carter & Laporte, 1996 [2] và sắp
lịch cho trường đại học Carter & Laporte, 1998 [3] Bardadym, 1996 [4].

LUAN VAN CHAT LUONG download : add



13

Người

(a)

(b)

Lớp học

Sự kiện

Thời gian

Giáo viên

Buổi học

Địa điểm

Mơn học

Phịng học

Hình 1 – Biểu diễn khái niệm bài tốn sắp thời khóa biểu
Khái niệm được thể hiện bằng hình hộp, các quan hệ là các đường nối các
hình hộp đó. Các khái niệm và các quan hệ giữa các khái niệm đó trong một bài
tốn lập lịch được mơ tả tổng qt ở hình (a) và được mơ tả cụ thể hơn ở hình (b)


1.1 Bài tốn lập thời khóa biểu cho trường phổ thơng (School timetabling)
Bài tốn lập thời khóa biểu cho trường phổ thơng hay bài tốn phân chia
giáo viên, lớp học trong một tuần đối với tất cả các môn học của một trường học.
Với ba tập hợp cho trước là tập giáo viên, tập lớp học và tập tiết học và một ma trận
ràng buộc số bài giảng một giáo viên được phân cơng dạy một lớp.
Bài tốn yêu cầu phân chia các bài giảng vào các tiết sao cho khơng giáo
viên hay lớp học nào có cùng một bài giảng trong cùng một thời gian và mỗi giáo
viên đều có một số lượng nhất định các bài giảng với mỗi lớp học.

1.2 Bài tốn lập thời khóa biểu cho trường đại học (University timetabling)
Bài toán lập thời khóa biểu cho trường đại học là bài tốn lập lịch cho các
bài giảng (lectures) vào từng khóa học với một số lượng phòng học và tiết học cho
trước. Điểm khác biệt chính với bài tốn lập thời khóa biểu trường phổ thơng là đặc
trưng của các khóa học ở trường đại học, các sinh viên tham dự khóa học, trong khi
các lớp học ở trường phổ thông được tạo bởi tập hợp các học sinh và có thể coi như
là một thực thể đơn. Ở các trường đại học, hai khóa học khác nhau có thể có trùng
sinh viên tham dự và điều đó có thể tạo ra xung đột và sẽ không thể lập lịch được

LUAN VAN CHAT LUONG download : add


14

trong cùng một tiết học. Thêm vào đó, các giáo viên ở trường phổ thông luôn dạy
nhiều hơn một lớp trong khi ở trường đại học một giảng viên thường chỉ dạy một
vài khóa học hay một vài mơn học trong một kỳ. Cuối cùng, với bài toán trường đại
học kích cỡ các phịng học chiếm một vai trị quan trọng trong khi với bài tốn
trường phổ thơng vấn đề này là khơng quan trọng bởi vì trong hầu hết các trường
phổ thơng mỗi lớp có một phịng học riêng.


1.3 Bài toán lập lịch thi (Examination timetabling)
Bài toán lập lịch thi tương tự như bài tốn lập thời khóa biểu cho trường đại
học nhưng ta cần phân biệt sự khác nhau giữa hai bài toán này. Bài toán lập lịch thi
có những đặc điểm khác sau đây:
• Chỉ có một kỳ thi cho mỗi một mơn thi.
• Các điều kiện xung đột nói chung là hạn chế. Thực tế, chúng ta có thể chấp
nhận một sinh viên có thể bỏ qua một bài giảng do sự chồng chéo các môn
học; nhưng khơng có sinh viên nào được phép bỏ qua một kỳ thi hết mơn đã
học vì nếu sinh viên không qua được kỳ thi này coi như trượt môn đó.
• Và một số ràng buộc khác như hầu hết một sinh viên sẽ chỉ có một mơn thi
trong một ngày và khơng có nhiều q các mơn thi liên tiếp nhau với một
sinh viên.
• Thời gian thi của các mơn thi có thể khác nhau, ngược lại với bài tốn lập
thời khóa biểu cho trường đại học thì thời gian học được tính bằng tiết (45 –
50 phút tùy quy định của trường).
• Có thể có nhiều hơn một mơn được thi trong một phịng nhưng lại thì khơng
thể có nhiều bài giảng được diễn ra trong một phịng tại một thời điểm.


 

LUAN VAN CHAT LUONG download : add


15

1.4 Bài tốn lập lịch theo tín chỉ
Trước hết để xây dựng được mơ hình bài tốn lập lịch theo tín chỉ ta cần
phải tìm hiểu và trả lời được câu hỏi “Tín chỉ là gì?”
Có rất nhiều định nghĩa về tín chỉ, khoảng 60 định nghĩa khác nhau, có định

nghĩa coi trọng khía cạnh định tính, có định nghĩa coi trọng khía cạnh định lượng,
có định nghĩa nhấn mạnh vào chuẩn đầu ra của sinh viên, có định nghĩa lại nhấn
mạnh vào các mục tiêu của chương trình học. Một định nghĩa về tín chỉ được các
nhà quản lý và nhà nghiên cứu giáo dục ở Việt Nam biết đến nhiều nhất có lẽ là của
học giả người Mỹ gốc Trung Quốc James Quann thuộc ĐH Washington. Cách hiểu
của ông về tín chỉ được theo bảo dịch của Bộ Giáo dục và Đào tạo như sau:
“Tín chỉ học tập là một đại lượng đo toàn bộ thời gian bắt buộc của một
người học bình thường để học một mơn cụ thể, bao gồm: 1. Thời gian lên lớp; 2.
Thời gian ở trong phịng thí nghiệm, thực tập hoặc các phần việc khác đã được quy
định ở thời khoá biểu; 3. Thời gian dành cho đọc sách, nghiên cứu giải quyết vấn
đề, viết hoặc chuẩn bị bài...; đối với môn học lý thuyết một tín chỉ là một gìờ lên
lớp (với 2 giờ chuẩn bị bài) trong tuần và kéo dài trong một học kỳ 15 tuần; đối với
các môn học ở sudio hay phịng thí nghiệm, ít nhất là 2 giờ trong một tuần (với 1
giờ chuẩn); đối với các mơn tự học, ít nhất là 3 giờ trong một tuần. “
Theo cách hiểu của PGS.TS Hoàng Văn Vân khoa sau ĐH – ĐH Quốc gia
Hà Nội như sau:
“Tín chỉ là đại lượng dùng để đo khối lượng kiến thức, kỹ năng của một
môn học mà người học cần phải tích luỹ trong một khoảng thời gian nhất định
thơng qua các hình thức: 1. Học tập trên lớp; 2. Học tập trong phịng thí nghiệm,
thực tập hoặc làm các phần việc khác (có sự hướng dẫn của giáo viên); 3. Tự học
ngoài lớp như đọc sách, nghiên cứu, giải quyết vấn đề hoặc chuẩn bị bài... Tín chỉ
cịn được hiểu là khối lượng lao động của người học trong một khoảng thời gian
nhất định trong những điều kiện học tập tiêu chuẩn.”
Như vậy, có 7 điểm cần phải làm rõ từ định nghĩa về tín chỉ này.
Thứ nhất, hoạt động dạy - học theo tín chỉ được tổ chức theo ba hình thức:
lên lớp, thực hành, và tự học. Trong ba hình thức tổ chức dạy - học này, hai hình
thức đầu được tổ chức có sự tiếp xúc trực tiếp giữa giáo viên và sinh viên (giáo

LUAN VAN CHAT LUONG download : add



16

viên giảng bài, hướng dẫn, sinh viên nghe giảng, thực tập dưới sự hướng dẫn của
giáo viên...), hình thức thứ ba khơng có sự tiếp xúc giữa giáo viên và sinh viên
(giáo viên giao nội dung để sinh viên tự học, tự nghiên cứu, tự thực hành). Ba hình
thức tổ chức dạy - học này tương ứng với ba kiểu giờ tín chỉ: giờ tín chỉ lên lớp, giờ
tín chỉ thực hành và giờ tín chỉ tự học. Theo đó, một giờ tín chỉ lên lớp bao gồm 1
tiết (50 phút) giáo viên giảng bài và 2 tiết sinh viên tự học, tự nghiên cứu ở nhà;
một giờ tín chỉ thực hành bao gồm 2 tiết giáo viên hướng dẫn, điều khiển và giúp
đỡ sinh viên thực hành, thực tập; và một giờ tín chỉ tự học bao gồm 3 tiết sinh viên
tự học, tự nghiên cứu, tự thực hành theo những nội dung giáo viên giao và những gì
sinh viên thấy cần phải nghiên cứu hoặc thực hành thêm (những hoạt động học tập
này có thể được thực hiện ở nhà hoặc ở trong phịng thí nghiệm, trong studio...).
Thứ hai, trong ba hình thức tổ chức dạy - học, cụ thể là trong ba kiểu giờ tín
chỉ, lượng kiến thức sinh viên thu được có thể khác nhau nhưng để thuận tiện cho
việc tính tốn (giờ chuẩn cho giáo viên, kinh phí cho từng mơn học, nhân lực để
phục vụ cho dạy - học...), ba kiểu giờ tín chỉ này được coi là có giá trị ngang nhau.
Thứ ba, có hai thuật ngữ dễ gây nhầm lẫn: đó là, một giờ tín chỉ (a credit
hour) và một tín chỉ (a credit). Trong các tài liệu nghiên cứu của các nhà nghiên
cứu Âu - Mỹ, hai thuật ngữ này thường được sử dụng thay cho nhau, chỉ chung một
giá trị. Trong cách hiểu của chúng tơi, tín chỉ và giờ tín chỉ là hai khái niệm có nội
dung khác. Theo đó, một tín chỉ gồm 15 giờ tín chỉ, thực hiện trong một học kỳ,
kéo dài 15 tuần, mỗi tuần 01 giờ tín chỉ.
Thứ tư, có thể có những mơn học chỉ gồm một kiểu giờ tín chỉ, nhưng có
thể có những mơn học gồm nhiều hơn một kiểu giờ tín chỉ. Trong mọi trường hợp,
cơng thức tính cho mỗi môn học là không đổi: 1+ 0 + 2 cho môn học thuần lý
thuyết, 0+ 2 + 1 cho môn học thuần thực hành, thực nghiệm, và 0+ 0 + 3 cho môn
học thuần tự học.
Thứ năm, người học trong phương thức đào tạo theo tín chỉ được cấp bằng

theo hình thức tích lũy đủ tín chỉ, và đánh giá theo thang điểm A, B, C, D, F trong
đó F là mức chưa đạt yêu cầu phải học và thi lại tín chỉ đó.
Thứ sáu, định nghĩa tín chỉ trên mới đo năng lực học tập của người học
thông qua thời lượng và số lượng tín chỉ được tích luỹ, nó chưa đo được mục tiêu
hay chất lượng đầu ra của quá trình học tập. Tuy nhiên người học được cấp bằng

LUAN VAN CHAT LUONG download : add


17

khơng chỉ phụ thuộc vào số tín chỉ mà họ tích lũy đủ mà cịn phụ thuộc vào điểm
trung bình chung quy định cho từng thời kỳ, từng kiểu văn bằng (cử nhân, thạc sĩ,
tiến sĩ). Những quy định này phần lớn là do từng trường ĐH quyết định.
Cuối cùng, thứ bảy, khác với phương thức đào tạo truyền thống, phương
thức đào tạo theo tín chỉ xem tự học như là một thành phần hợp pháp trong cơ cấu
giờ học của sinh viên: ngoài việc nghe giảng và thực hành trên lớp, sinh viên được
giao những nội dung để tự học, tự thực hành, tự nghiên cứu; những nội dung này
được đưa vào thời khoá biểu để phục vụ cho công tác quản lý và phải đưa vào nội
dung các bài kiểm tra thường xuyên và bài thi hết môn học.

1.5 Ưu điểm của phương thức đào tạo theo tín chỉ
Thứ nhất, việc tự học, tự nghiên cứu của sinh viên được coi trọng được tính
vào nội dung và thời lượng của chương trình. Đây là phương thức đưa giáo dục ĐH
về với đúng nghĩa của nó, người học tự học, tự nghiên cứu, giảm sự nhồi nhét kiến
thức của người dạy, và do đó phát huy được tính chủ động, sáng tạo của người học.
Thứ hai, chương trình được thiết kế theo phương thức đào tạo tín chỉ bao
gồm một hệ thống những môn học thuộc khối kiến thức chung, những môn học
thuộc khối kiến thức chuyên ngành, những môn học thuộc khối kiến thức cận
chuyên ngành. Mỗi khối lượng kiến thức đều có số lượng mơn học lớn hơn số

lượng các mơn học hay số lượng tín chỉ được yêu cầu. Sinh viên có thể tham khảo
giáo viên hoặc cố vấn để chọn những môn học phù hợp với mình, để hồn thành
một văn bằng và để phục vụ cho nghề nghiệp tương lai của mình.
Thứ ba, sinh viên được cấp bằng khi đã tích luỹ đầy đủ số lượng tín chỉ do
trường ĐH quy định; do vậy họ có thể hồn thành những điện kiện để được cấp
bằng tuỳ theo khả năng và nguồn lực của mình.
Thứ tư, phản ánh được những mối quan tâm và những yêu cầu của người
học như là những người sử dụng kiến thức và nhu cầu của các nhà sử dụng lao
động trong các tổ chức quản lý kinh doanh và tổ chức quản lý hành chính nhà
nước.

LUAN VAN CHAT LUONG download : add


18

Thứ năm, phương thức đào tạo này sẽ tạo được sự liên thông giữa các cơ sở
đào tạo ĐH trong nước và nước ngoài.
Bên cạnh những ưu điểm cho giáo viên và sinh viên cịn có các lợi ích cho
các nhà quản lý giáo dục. Vì nó vừa là thước đo khả năng học tập của người học,
vừa là thước đo hiệu quả của giáo viên; là cơ sở để các trường ĐH tính tốn ngân
sách chi tiêu, nguồn nhân lực; và là cơ sở để báo các số liệu của trường cho các cơ
quan cấp trên và các đơn vị liên quan. Một khi thước đo giờ tín chỉ được phát triển
và kiện tồn, việc sử dụng nó như là một phương tiện giám sát bên ngoài, để báo
cáo và quản lý hành chính hữu hiệu hơn.
Chính vì thế mà đào tạo theo tín chỉ có sức hấp dẫn với các nước trên thế
giới trong đó có Việt Nam. Ngày nay, trong xu thế hội nhập vừa tạo ra thời cơ đồng
thời vừa là thách thức đối với nước ta trên lĩnh vực Giáo dục - Đào tạo. Việt Nam
đang trên đà phát triển vì vậy cần có tư duy mới để bứt phá đưa đất nước phát triển
điều đó phụ thuộc rất nhiều vào giáo dục nước nhà, tạo ra con người chủ động, tích

cực, sáng tạo. Muốn vậy, cần có hệ thống giáo dục hợp lý, để nâng cao chất lượng
Giáo dục - Đào tạo cho hệ thống trung học chuyên nghiệp (THCN), CĐ, ĐH cần
chuyển đổi từ phương thức đào tạo theo niên chế sang đào tạo theo hệ thống tín chỉ.
Phương thức đào tạo này có ý nghĩa to lớn trong việc hội nhập và tiến dần đến
phương thức đào tạo tiên tiến, tạo nhiều cơ hội cho người học - chủ nhân tương lai
của đất nước.

1.6 Các cách tiếp cận hiện nay
Bài toán thời khóa biểu nói riêng và các bài tốn tối ưu tổ hợp nói chung rất
khó giải. Sự khó khăn của chúng được thể hiện ở độ phức tạp tính tốn và với
những bài tốn thuộc lớp NP-khó như vậy thời gian để giải thường tăng theo hàm
mũ của kích thước bài toán.
Như chúng ta đã biết, trong thuật toán “vét cạn” (brute force) (tìm kiếm
theo bề rộng hoặc theo độ sâu), thì về mặt nguyên tắc các phương pháp tìm được
nghiệm của bài tốn nếu bài tốn đó có nghiệm. Song trên thực tế những bài tốn
NP-khó khơng thể áp dụng được phương pháp này vì ta phải phát triển một không

LUAN VAN CHAT LUONG download : add


19

gian tìm kiếm rất lớn trước khi tìm được lời giải, nhưng do những hạn chế về thời
gian tính tốn và dung lượng bộ nhớ không cho phép chúng ta làm được điều đó.
Bài tốn sắp lịch cho trường đại học có mục tiêu chính là việc sắp các phân
cơng giảng dạy hàng tuần. Bài toán này bao gồm việc sắp các phân công giảng dạy
vào các tiết theo một cách nào đó mà giảng viên (hay lớp học) có liên quan không
được phép tham gia một lúc hai phân công, và các ràng buộc khác cần phải được
thỏa mãn. Bài tốn này thuộc loại NP-khó và thường được giải quyết bằng các
phương pháp Heuristic.

Thông thường, người giáo vụ cần phải mất vài ngày để sắp được một thời
khóa biểu bằng tay. Mà lời giải cịn có thể chứa những kết quả khơng tốt lắm, ví dụ
như việc giáo viên bị trống tiết giữa trong một buổi giảng. Ngoài ra trong quá trình
sắp người giáo vụ phải tương tác rất nhiều với giảng viên để thỏa thuận giờ giảng
khi xảy ra việc tranh chấp tài nguyên.
Bởi lý do ở trên, nhu cầu đặt ra là cần một chương trình sắp thời khóa biểu
tự động. Trong hơn bốn mươi năm qua, bắt đầu từ thập niên 60, với Gotlieb (1963)
[5] và những người khác, nhiều bài báo có liên quan đến việc sắp thời khóa biểu tự
động đã xuất hiện ở các hội nghị và tạp chí khoa học, và các ứng dụng đã bắt đầu
được phát triển cho ra các kết quả khá tốt.
Các kỹ thuật sơ khai của Schmidt-Strohlein, 1979 [6]; Junginger, 1986 [7]
được dựa trên việc giả lập quá trình sắp lịch của con người trong việc giải bài toán.
Các kỹ thuật này được gọi là heuristics trực tiếp (direct heuristic) được dựa trên
việc mở rộng liên tục (successive augmentation). Nghĩa là, họ sẽ sắp một phần thời
khóa biểu, lần lượt từng phân công, cho đến khi tất cả các phân công đã được sắp
hoặc không sắp được thêm phân công nào nữa do vi phạm các ràng buộc.
Sau này, các nhà nghiên cứu đã bắt đầu áp dụng các kỹ thuật tổng quát hơn
trên bài toán này. Do đó ta thấy các thuật tốn dựa trên lập trình tuyến tính (integer
programming) của Tripathy trong các năm 1984, 1992 [8, 9], luồng mạng (network
flow) của Ostermann-de Werra, 1983 [10], và cịn những loại khác nữa. Ngồi ra
bài tốn này cũng được giải quyết bằng cách đưa nó về bài tốn nổi tiếng: tơ màu
đồ thị (graph coloring) của Neufeld-Tartar, 1974 [11].
Gần đây nhất, những tiếp cận dựa trên những hướng nghiên cứu mới bao
gồm tôi luyện thép (simulated annealing) (Abramson, 1991 [12]), Tabu search

LUAN VAN CHAT LUONG download : add


20


(Costa, 1994 [13]), thuật giải di truyền (genetic algorithms) (Colorni, Dorigo, và
Maniezzo, 1992 [14]), thỏa mãn ràng buộc (constraint satisfaction) (Yoshikawa,
Kaneko, Nomura và Watanabe, 1994 [15]) và một kết hợp của các phương pháp
khác (Cooper và Kingston, 1993 [16]) nhằm tìm ra lời giải “tốt nhất có thể” cho lớp
các bài tốn NP-khó nói chung và có thể áp dụng riêng cho nhánh bài toán lập lịch
được đề cập trong luận văn này. Trong chương 2 chúng ta sẽ cùng nhau tìm hiểu
chi tiết hơn một vài thuật tốn phổ biến hiện nay.

LUAN VAN CHAT LUONG download : add


21

Chương 2: TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP TÌM KIẾM

Tìm kiếm cục bộ dựa vào một ý tưởng tổng quát và đơn giản. Gọi P là một
bài toán tối ưu tổ hợp cần giải, và s là lời giải hiện hành giả sử là một lời giải khả
thi của P, và có hàm chi phí f(s). Miền lân cận N(s) được định nghĩa cho s, là tập
những lời giải láng giềng khả thi s’ của s sao cho từ s ta có thể đạt tới s’ nhờ vào
một bước chuyển m. Bước chuyển có tác dụng biến đổi s thành ra một lời giải láng
giềng. Thao tác biến đổi này được lặp cho đến khi hội tụ về một lời giải tốt. Lời
giải này là lời giải cận tối ưu, mà trong một số bài tốn thực tế, khơng sai biệt gì
nhiều với lời giải tối ưu.

2.1 Xung đột tối thiểu (Min-conflict)
Thuật giải xung đột tối thiểu (Min-conflict) [17], viết tắt là MC đã được
dùng khá phổ biến để giải hệ ràng buộc quá mức. Thuật giải MC chọn ngẫu nhiên
một biến nào đó dính líu đến một ràng buộc bị vi phạm và rồi chọn một trị từ miền
trị của biến này sao cho tối thiểu hoá số lượng những vị phạm ràng buộc có thể xảy
ra. Vì thuật giải MC thuần túy có thể khơng thốt ra được điểm tối ưu cục bộ,

Thuật giải thường kết hợp với một chiến lược bước ra ngẫu nhiên (random walk).
Với một biến nào đó được chọn, chiến lược bước ra ngẫu nhiên lấy ngẫu nhiên một
trị từ miền trị của biến này với xác xuất p, và áp dụng theo Thuật giải MC với xác
xuất 1- p. Giá trị của thông số p có ảnh hưởng lên hiệu quả của Thuật giải. Thuật
giải này được gọi là MCRW (Min-conflict Random Walk)

2.2 Thuật giải mô phỏng luyện kim (Simulated Annealing)
Mô phỏng luyện kim (Simulated Annealing) [18] viết tắt SA, là một kỹ
thuật tìm kiếm ngẫu nhiên (stochastic search) tỏ ra rất hữu hiệu cho những bài tốn
tối ưu hóa qui mơ lớn. Trong kỹ thuật này, nhiệt độ là biến được khởi tạo ở một giá
trị cao và dần dần giảm dần xuống trong quá trình tìm kiếm. Trong quá trình tìm
kiếm SA thay lời giải hiện thời bằng cách chọn ngẫu nhiên lời giải láng giềng với

LUAN VAN CHAT LUONG download : add


22

một xác suất phụ thuộc vào sự chênh lệch giữa giá trị hàm mục tiêu và tham số điều
khiển là biến nhiêt độ toàn cục. Tại những giá trị nhiệt độ cao, các bước chuyển
được chấp nhận một cách ngẫu nhiên bất luận chúng là bước chuyển có cải thiện
hàm chi phí của lời giải hay khơng. Khi nhiệt độ được giảm xuống, xác xuất xuất
hiện lời giải có cải thiện sẽ tăng lên và xác xuất xuất hiện lời giải khơng cải thiện sẽ
giảm xuống. Có một số cách thức giảm nhiệt độ dần xuống được dùng trong một
Thuật giải SA, được gọi là lịch biểu làm nguội (cooling schedule).

2.3 Thuật giải leo đồi (Hill-climbing)
Thuật giải leo đồi (Hill-climbing) [19] chính là nền tảng cơ sở của các kỹ
thuật tìm kiếm cục bộ. Mặc dù đây là Thuật giải đơn giản nhưng lại nó lại rất mạnh
và hiệu quả trong việc giải quyết các bài toán phải thỏa mãn các ràng buộc lớn

(CSP – Constraint Satisfaction Problem). Thuật ngữ “leo đồi” (hill-climbing) xuất
phát từ cơ chế “tu chỉnh lập”: ở mỗi bước của việc tìm kiếm, chúng ta sẽ chọn một
bước chuyển mà nó cải thiện giá trị hàm mục tiêu để thực hiện. Trong thuật giải leo
đồi, chỉ những bước chuyển cải thiện được hàm chi phí hoặc khơng làm cho hàm
chi phí thay đổi mới được chọn vì vậy việc tìm kiếm sẽ liên tục bước lên vị trí cao
hơn cho đến khi nó gặp điều kiện dừng.

2.4 Tìm kiếm Tabu (Tabu search)
Tìm kiếm Tabu được đề xuất bởi Glover năm 1986 ([20]). Đây là một
phương pháp dị tìm trong khơng gian lời giải bằng cách di chuyển từ một lời giải s
tại lượt lặp t về một lời giải tốt nhất s’ trong tập con N* của miền lân cận N(s). Vì
s’ khơng nhất thiết cải thiện chi phí của s, một cơ chế được đặt ra để ngăn chặn q
trình khỏi lặp vịng trên một chuỗi các lời giải. Một cách để tránh sự lặp vịng là
cấm q trình tìm kiếm quay về những lời giải đã gặp rồi, nhưng làm như vậy đòi
hỏi phải lưu trữ khá nhiều thơng tin. Thay vì làm thế, chỉ một vài thuộc tính của
những lời giải đã gặp sẽ được lưu trong danh sách tabu (tabu list) và bất kỳ lời giải
nào sở hữu những thuộc tính này sẽ khơng được xét đến trong θ lần lặp, ví dụ như
ta có thể lưu trong danh sách tabu này chi phí của lời giải đã gặp được tính tốn

LUAN VAN CHAT LUONG download : add


23

thông qua hàm phạt. Cơ chế này thường được gọi là bộ nhớ ngắn hạn và θ được gọi
là kỳ hạn tabu. Tìm kiếm tabu được phát triển thành nhiều dạng cải tiến như giải
thuật tìm kiếm Tabu thích ứng (Reactive Tabu Search) và tìm kiếm tabu với hai
danh sách tabu: bộ nhớ ngắn hạn (short term memory) và bộ nhớ dài hạn (long term
memory).


2.5 Thuật giải di truyền (Genetic Algorithm)
Thuật giải di truyền (GA) (Goldberg, 1989 [21]) đã tỏ ra khá thành công
trong một số những áp dụng. GA mượn ý tưởng trong q trình tiến hóa của sinh
vật.
Ý tưởng chính của Thuật giải là duy trì một quần thể các lời giải ứng viên.
Các lời giải ứng viên này sẽ được cho cơ hội riêng lẻ để sản sinh ra con cái tùy
thuộc vào độ thích nghi (fitness) của chúng. Độ thích nghi được đo bằng một hàm
mục tiêu. Thuật giải GA đã được áp dụng vào việc giải hệ ràng buộc ([22]).
Việc dùng Thuật giải GA vào các bài tốn tối ưu hóa có ràng buộc làm phát
sinh nhiều vấn đề mà các nhà nghiên cứu phải quan tâm giải quyết. Một trong
những vấn đề quan trọng là làm thế nào để đưa các ràng buộc vào các hàm thích
nghi (fitness function) để điều khiển q trình tìm kiếm một cách đóng đắn.

2.6 Kết luận
Sự thành cơng của bất kỳ Thuật giải tìm kiếm cục bộ nào nêu trên cũng tùy
thuộc vào các đặc điểm thi công, tức là tùy thuộc vào các tham số kỹ thuật đặc thù
mà người sử dụng phải xác định khi áp dụng Thuật giải tìm kiếm cục bộ đó vào bài
tốn cụ thể. Quá trình thực nghiệm để xác định các thơng số kỹ thuật của một Thuật
giải tìm kiếm cục bộ nào đó khi áp dụng vào một bài tốn cụ thể được gọi là q
trình điều chỉnh thơng số (parameter tuning).
Trong những năm gần đây việc kết hợp các loại giải thuật tìm kiếm cục bộ
và một số giải thuật khác là một trong số các cách tiếp cận mới nhất. Trong chương
3 chúng ta sẽ tìm hiểu chi tiết giải thuật tìm kiếm Tabu

LUAN VAN CHAT LUONG download : add


24

Chương 3: CƠ SỞ TÌM KIẾM TABU


3.1 Lược Sử Về Tabu Search
3.1.1 Giới Thiệu
Sự phức tạp trong các vấn đề tối ưu được gặp trong thực tế như các vấn đề
trong ngành viễn thơng, hậu cần, kế hoạch tài chính, vận chuyển và việc sản xuất
đã thúc đẩy mạnh việc phát triển các kỹ thuật tối ưu mạnh mẽ. Những kỹ thuật này
thường là kết quả của các ý tưởng phát sinh từ các lĩnh vực nghiên cứu khác nhau,
với hy vọng có thể phát triển được các phương pháp hiệu quả và có thể xử lý được
những phức tạp trong các vấn đề về tối ưu.
Dạng cơ bản nhất của TS được đề nghị từ ý tưởng của Fred Glover [24].
Phương pháp này được dựa trên các quy trình được thiết kế để vượt qua các giới
hạn của tính khả thi hoặc tối ưu cục bộ.
Tabu search là một loại “meta-heuristic” dẫn dường cho một quy trình tìm
kiếm “heuristic cục bộ” để mở rộng không gian lời giải ra bên ngồi vùng tối ưu
cục bộ. Quy trình cục bộ này là việc tìm kiếm sử dụng một thao tác gọi là “phép
chuyển” (move) để tạo ra các lời giải xung quanh lời giải ban đầu. Và một trong
các thành phần chính của TS chính là “bộ nhớ thích nghi” (adaptive memory), giúp
tạo ra các hướng tìm kiếm linh hoạt hơn.
Cùng với phương pháp “tôi luyện thép” và “thuật giải di truyền”, tabu
search được đánh giá là “rất có triển vọng” cho các ứng dụng thực tế trong báo cáo
của hội đồng Committee on the Next Decade of Operations Research (CONDOR
1988) [23]. Sự phát triển nhanh và mạnh của tabu search trong 20 năm qua đã
chứng minh được đánh giá đó là chính xác. Cách tiếp cận “thuần” (pure) và “lai”
(hybrid) đã lập kỷ lục mới trong việc tìm kiếm các lời giải tốt hơn cho những vấn
đề về kế hoạch sản xuất, phân chia tài nguyên, thiết kế mạng trong viễn thông và
nhiều lĩnh vực khác nữa.

 

LUAN VAN CHAT LUONG download : add



25

3.1.2 Tabu Search – Một Dạng Meta-heuristic
Nền tảng của tabu search phản ánh chủ đề về các heuristic tốt được thúc đẩy
bởi nhiều thuật tốn tốt có liên quan. Hơn nữa, các heuristic và thuật tốn tương tự
nhau có thể kế thừa những lợi ích từ các nguyên lý tổng hợp từ các phạm vi trí tuệ
nhân tạo (artificial intelligent – AI) và vận trù học (operation research – OR). Thiết
kế hiệu quả của các phương pháp này có thể góp phần để phát triển những phiên
bản nguyên lý mới và sâu sắc hơn trong các lĩnh vực của AI và OR có liên quan về
các kỹ thuật cải thiện việc giải quyết vấn đề.
Ngày nay nhiều nhà nghiên cứu trong lĩnh vực AI và OR đã quên rằng hai
ngành này đã phát triển cùng nhau và chia sẻ nhiều kiến thức cho nhau. Cả hai
ngành đều bắt đầu từ những kết quả của việc phát triển các phương thức giải quyết
vấn đề. Những bài báo đầu tiên về heuristic chấp nhận các tiếp cận có ý thức về cầu
nối giữa AI và OR (ví dụ Simon và Newell, 1958 [30]; Fisher và Thompson, 1963
[31]; Crowston, 1963 [32]). Tuy nhiên không lâu sau hai lĩnh vực này bắt đầu chia
rẽ, với OR thì tập trung về các kết quả, trong khi AI thì chú trọng về tượng trưng và
các phân tích định lượng.
Trong thời gian việc phân chia giữa hai ngành vẫn chưa rõ ràng, vẫn có vài
cố gắng để giới thiệu những tiếp cận không truyền thống trong lĩnh vực tối ưu.
Cùng lúc đó cũng có những cố gắng để giới thiệu xác suất và các khái niệm thiết kế
tích hợp vào trong các quy trình heuristic. Khơng may, những phát triển này lại bị
nhận chìm trong nhiều năm. Nhưng chúng cung cấp nền tảng cho các ý tưởng nổi
lên lại vào giữa cuối thập niên 80 và trở thành nguồn gốc của các chiến lược mà
bây giờ là trái tim của tabu search.

3.1.3 Các Giai Đoạn Phát Triển Của Tabu Search
Bốn giai đoạn phát triển chính của tabu search gồm: (1) các chiến lược kết

hợp các luật quyết định dựa trên tái cấu trúc logic và tìm kiếm với các chiều sâu
biến đổi (non-monotonic search), (2) Khả năng khôi phục và xung đột hệ thống, (3)
bộ nhớ linh hoạt dựa trên tính vừa xảy ra và tính thường xuyên và (4) các quy trình
được chọn để kết hợp các lời giải, áp dụng cho quần thể được duy trì có hệ thống.
Giai đoạn phát triển đầu tiên đến từ việc nghiên cứu các luật quyết định cho
vấn đề phân công việc. Fisher và Thompson (1963) [31] giới thiệu sự đổi mới của

LUAN VAN CHAT LUONG download : add