ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Thùy
ỨNG DỤNG NGÔN NGỮ LẬP TRÌNH RÀNG BUỘC COMET VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Hà Nội – 2010
i
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Thùy
ỨNG DỤNG NGÔN NGỮ LẬP TRÌNH RÀNG BUỘC COMET VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hƣớng dẫn: Th.S Lê Hồng Hải
Hà Nội - 2010
ii
LỜI CẢM ƠN
Trước hết, em xin chân thành cảm ơn đến quý thày cô trường Đại học Công
Nghệ đã tận tình dạy bảo em trong suốt thời gian học tập tại trường.
Em xin gửi lời biết ơn sâu sắc đến Thạc sĩ Lê Hồng Hải đã dành nhiều thời
gian và tâm huyết hướng dẫn nghiên cứu, giúp em hoàn thành khóa luận tốt nghiệp.
Em cũng xin chân thành cảm ơn Ban Giám hiệu trường Đại học Công nghệ
cùng quí thày cô trong Khoa công nghệ thông tin đã tạo điều kiện để em học tập
và hoàn thành tốt khóa học.
Trong khóa luận không thể tránh khỏi những thiếu sót. Em rất mong nhận
được được những đóng góp quí báu của thày cô và các bạn để khóa luận được
hoàn thiện hơn.
Hà Nội, tháng 5 năm 2010
Sinh viên
1
Nguyễn Thị Thùy
TÓM TẮT KHÓA LUẬN
Lập Thời khóa biểu là công việc cần thiết và quan trọng mà tất cả các tổ
chức giáo dục phải thực hiện nhằm đƣa ra biểu đồ kế hoạch năm học, lịch giảng
dạy và học tập cho giáo viên, học sinh. Trƣớc đây, khi CNTT chƣa đƣợc phát triển
mạnh mẽ và ứng dụng rộng rãi thì công việc này thƣờng đƣợc thực hiện một cách thủ công trên giấy, tiêu tốn nhiều chi phí, thời gian và công sức.
Bài toán lập Thời khóa biểu tronng trƣờng học là một một trƣờng hợp riêng
của bài toán lập lịch đƣợc xếp vào hàng các bài toán khó chƣa có giải thuật tối ƣu
nhất. Có rất nhiều thuật toán, phƣơng pháp tiếp cận khác nhau đƣợc các nhà khoa
học trên thế giới đƣa ra nhằm giải quyết bài toán này. Song, một phƣơng pháp tiếp
cận khá là mới và đƣợc cho là giải pháp tối ƣu cho các bài toán lập lịch đó là ứng
dụng ngôn ngữ lập trình ràng buộc vào giải quyết các bài toán tổ hợp.
Với mục tiêu xây dựng một chƣơng trình lập thời khóa biểu hoạt động hiệu
quả, khóa luận xin trình bày về ngôn ngữ lập trình ràng buộc Comet và ứng dụng
Comet để giải quyết bài toán lập thời khóa biểu. Comet là ngôn ngữ lập trình ràng
buộc mới đƣợc phát triển và ứng dụng. Đây là ngôn ngữ lập trình điển hình nhất
cho việc giải quyết các bài toán tổ hợp nhƣ lập lịch, lập kế hoạch … Đây cũng là
một ngôn ngữ lập trình hƣớng đối tƣợng, dễ sử dụng và cấu trúc câu lệnh tƣơng
2
đối giống với ngôn ngữ lập trình C++.
MỤC LỤC
LỜI CẢM ƠN ....................................................................................................... 1
TÓM TẮT KHÓA LUẬN ..................................................................................... 2
MỤC LỤC ............................................................................................................ 3
BẢNG CÁC KÝ HIỆU VIẾT TẮT ....................................................................... 5
BẢNG CÁC THUẬT NGỮ CHUYÊN NGÀNH .................................................. 5
DANH SÁCH CÁC HÌNH VẼ ĐƢỢC SỬ DỤNG ............................................... 6
CHƢƠNG 1: MỞ ĐẦU ........................................................................................ 7
1.1. Ý nghĩa ứng dụng Comet vào giải quyết các vấ đề tối ƣu hóa tổ hợp ... 7
1.2. Cấu trúc khóa luận ............................................................................. 10
CHƢƠNG 2: LẬP TRÌNH RÀNG BUỘC .......................................................... 11
2.1. Lập trình ràng buộc là gì? .................................................................. 11
2.2. Nguồn gốc lập trình ràng buộc ........................................................... 11
2.3. Mô hình lập trình ràng buộc .............................................................. 12
2.4. Ứng dụng của ngôn ngữ lập trình ràng buộc (CP) .............................. 14
CHƢƠNG 3: NGÔN NGỮ LẬP TRÌNH COMET .............................................. 16
3.1. COMET là gì? ................................................................................... 16
3.2. Lập trình Comet ................................................................................. 17
3.2.1. Mô hình lập trình Comet ...................................................... 17
3.2.2. Ví dụ .................................................................................... 20
3
3.3. Ƣu điểm của Comet ........................................................................... 23
CHƢƠNG 4: ỨNG DỤNG COMET VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU ............................................................................................................................ 26
4.1. Đặt vấn đề xây dựng bài toán ............................................................. 26
4.2. Giải quyết bài toán ............................................................................. 28
4.3. Thực nghiệm ...................................................................................... 30
4.3.1. Các chức năng quản lý giảng viên, môn học, phòng học, khoa ...................................................................................................... 31
4.3.2. Chức năng phân công giảng dạy ........................................... 36
4.3.3. Chức năng xếp Thời khóa biểu ............................................. 37
4.3.4. Chức năng xem thời khóa biểu theo tên lớp, tên giảng viên, tên
phòng học ...................................................................................... 38
CHƢƠNG 5: KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ..................................... 40
4
TÀI LIỆU THAM KHẢO ................................................................................... 41
BẢNG CÁC KÝ HIỆU VIẾT TẮT
Ký hiệu Từ viết tắt
ACM Association for Computing Achinery
AI Artificial Intelligence
API Application Programming Interface
CHIP Constraint Handling In Prolog
CLP Constraint Logic Programming
CBLS Constraint-Based Local Search
CP Constraint Programming
LP Logic Programming
BẢNG CÁC THUẬT NGỮ CHUYÊN NGÀNH
Các thuật ngữ Ý nghĩa
Artificial Intelligence Trí tuệ nhân tạo
Application Programming Interface Giao diện lập trình ứng dụng
Constraint Programming Lập trình ràng buộc
Logic Programming Lập trình logic
Search Tìm kiếm
5
Search Tree Cây tìm kiếm
DANH SÁCH HÌNH ẢNH ĐƢỢC SỬ DỤNG
Hình 1-1. Bài toán 4-Hậu ...................................................................................... 8
Hình 1-2. Một nhánh trong cây tìm kiếm của bài toán 4-Hậu ................................ 9
Hình 2-1. Mô hình CP ......................................................................................... 12
Hình 2-2. Ứng dụng CP vào phân tích chuỗi protein ........................................... 15
Hình 3-1. Thành phần tìm kiếm trong Comet ...................................................... 19
Hình 3-2. Code bài toán 16-Hậu bằng Comet ...................................................... 20
Hình 3-3. Kết quả bài toán 16-Hậu bằng Comet .................................................. 22
Hình 3-4. Kết quả trực quan bài toán 16-Hậu visualization.................................. 24
Hình 4-1. Mô hình chƣơng trình .......................................................................... 30
Hình 4-2. Quản lý giảng viên .............................................................................. 31
Hình 4-3. Quản lý phòng học .............................................................................. 32
Hình 4-4. Quản lý môn học ................................................................................. 33
Hình 4-5. Quản lý lớp học ................................................................................... 34
Hình 4-6. Quản lý khoa ....................................................................................... 35
Hình 4-7. Chức năng phân công giảng dạy .......................................................... 36
Hình 4-8. Chức năng xếp Thời khóa biểu ............................................................ 37
Hình 4-9. Xem Thời khóa biểu theo lớp .............................................................. 38
Hình 4-10. Xem Thời khóa biểu theo giảng viên ................................................. 39
6
Hình 4-11. Xem Thời khóa biểu theo phòng học ................................................. 39
CHƢƠNG 1: MỞ ĐẦU
Ngày nay, với sự phát triển mạnh mẽ của CNTT góp phần mang lại những
thành tựu rực rỡ cho các lĩnh vực, hoạt động trong đời sống. Cùng với sự phát triển
của CNTT, các thế hệ ngôn ngữ lập trình lần lƣợt ra đời nhằm đáp ứng các yêu cầu
công nghệ. Đóng góp quan trọng vào sự phát triển và ứng dụng CNTT, ngôn ngữ lập trình ràng buộc Comet thật sự mang lại tiện ích lớn trong việc giải quyết các
bài toán tổ hợp nhƣ lập lịch, lập kế hoạch.
1.1. Ý nghĩa ứng dụng lập trình ràng buộc đối với vấn đề tối ƣu
hóa tổ hợp
Trong lĩnh vực nghiên cứu khoa học máy tính, các bài toán về tối ƣu hóa tổ
hợp đƣợc đánh giá là các bài toán khó NP[1], đặc trƣng bởi bộ dữ liệu lớn, các
ràng buộc phức tạp. Để giải quyết vấn đề này hiệu quả đòi hỏi phải có kinh nghiệm
và kỹ năng. Trên thế giới có rất nhiều những công trình nghiên cứu, các thuật toán
đƣợc ứng dụng và phát triển để giải quyết vấn đề này: các thuật toán quay lui, vét
cạn, các thuật toán về quy hoạch động. Tuy nhiên, trong lập trình truyền thống
chƣa có giải thuật hiệu quả nhất, đáp ứng đƣợc thời gian xử lý là đa thức. Do đó,
đây vẫn là bài toán khó chƣa có lời tối ƣu nhất.
Trong những năm gần đây, CP nổi lên nhƣ một công nghệ quan trọng, giải
quyết hiệu quả các bài toán tối ƣu hóa tổ hợp, ứng dụng thành công trong nhiều
lĩnh vực: hàng không, khoa học máy tính, công nghiệp sản xuất…CP thực sự là
một giải pháp tối ƣu, đƣợc giới chuyên môn đánh giá cao về khả năng giải quyết các vấn đề phức tạp trong cuộc sống thực thế.
Dƣới đây, ta sẽ xét bài toán N-Hậu trong lập trình truyền thống với giải
thuật vét cạn, quay lui.
Bài toán N-Hậu
Bài toán 4-queens là bài toán đặt 4 quân hậu trên bàn cờ vua kích thƣớc 4*4 sao cho không có quân hậu nào có thể “ăn” đƣợc quân hậu khác, hay nói cách khác
7
không quân hậu nào có thể di chuyển theo quy tắc cờ vua. Do đó, lời giải của bài
toán là một cách xếp bốn quân hậu trên bàn cơ vua sao cho không có hai quân nào đứng trên cùng hàng, hoặc cùng cột hoặc cùng đƣờng chéo.
Hình 1-1. Bài toán 4-Hậu
Đây là bài toán tổ hợp kinh điển, có nhiều giải thuật: quay lui, vét cạn, quy
hoạch động. Tuy nhiên, độ phức tạp của các thuật toán này thƣờng là...Chƣa có
giải thuật thỏa mãn thời gian chạy là đa thức. Dƣới đây, ta xét bài toán này trong
môi trƣờng lập trình truyền thống ( bằng ngôn ngữ lập trình C/C++ hoặc Java...)
với giải thuật vét cạn, quay lui (gọi đệ quy). Tƣ tƣởng cơ bản của giải thuật vét
cạn, quay lui là ta thử đặt một quân cờ vào một ô trong bàn cơ, sau đó lần lƣợt đặt
từng quân cơ tiếp theo vào các ô cờ khác. Trong trƣờng hợp không thỏa mãn điều kiện ràng buộc của bài toán (Không có hai quân cờ nào “ăn” đƣợc nhau) thì quay
lui trở lại bƣớc trƣớc đó và đặt lại quân cờ sao cho thỏa mãn điều kiện bài toán.
Giải thuật này đƣợc mô tả trực quan hơn trong một nhánh của cây tìm kiếm bài
8
toán 4-Queens (Hình 1-2).
Hình 1-2. Một nhánh trong cây tìm kiếm của bài toán 4-Hậu
Trong lập trình truyền thống không hỗ trợ chƣơng trình tự động
backtracking, coder phải tự viết chức năng thực hiện backtracking để tìm kiếm tất cả các lời giải thỏa mãn điều kiện bài toán.
So với lập trình truyền thống, lập trình ràng buộc hỗ trợ chƣơng trình tự
động backtracking, giải quyết vấn đề phân theo hai thành phần. Thứ nhất, vấn đề
đƣợc mô hình hóa bởi tập các ràng buộc trên miền giới hạn của các biến. Thứ hai,
là giải quyết các ràng buộc bằng cách sử dụng những thông tin đã đƣa ra trong mô
hình để tự động tìm kiếm giải pháp. Quá trình này hệ thống tự động thực hiện,
không có sự can thiệp của con ngƣời. Chúng ta sẽ tìm hiểu sâu về lập trình ràng
9
buộc trong chƣơng tiếp theo.
1.2. Giới thiệu cấu trúc khóa luận
Cấu trúc khóa luận gồm 5 chƣơng:
Chƣơng 1: Mở đầu
Chƣơng 2: Lập trình ràng buộc
Chƣơng 3: Ngôn ngữ lập trình Comet
Chƣơng 4: Áp dụng Comet vào bài toán ứng dụng “Lập thời khóa
biểu” cho trường đại học
10
Chƣơng 5: Kết luận và hướng phát triển.
CHƢƠNG 2 LẬP TRÌNH RÀNG BUỘC
Trong một vài năm gần đây, lập trình ràng buộc (CP) đã thu hút sự chú ý
một số lƣợng lớn các chuyên gia CNTT vì khả năng giải quyết các vấn đề khó
khăn trong thực tế. Theo [5] CP đƣợc ACM (Association for Computing Achinery)
nhận định là một trong những hƣớng chiến lƣợc trong nghiên cứu tin học. Tuy
nhiên CP vẫn là một trong những công nghệ ít đƣợc biết đến và hiểu rõ.
2.1. Lập trình ràng buộc là gì?
Lập trình ràng buộc (CP - Constraint Programming) là ngôn ngữ lập trình ràng buộc, công nghệ điển hình giải quyết hiệu quả vấn đề mô hình hóa và tối ƣu
hóa tổ hợp, đặc biệt là trong lĩnh vực quy hoạch và lập lịch. CP nghiên cứu các hệ
thống tính toán dựa trên các ràng buộc. Ý tƣởng cơ bản của CP là giải quyết vấn đề
bằng cách nêu rõ ràng buộc (các điều kiện, thuộc tính, yêu cầu) và tìm kiếm giải
pháp thỏa mãn tất cả các ràng buộc.
Lập trình ràng buộc ( CP ) là một cách tiếp cận mới về vấn đề giải quyết
thỏa mãn các ràng buộc và các vấn đề tối ƣu hóa đang đƣợc sử dụng trong nhiều
ứng dụng thƣơng mại. CP kết hợp tìm kiếm vét cạn, quay lui từ những ngôn ngữ
lập trình logic với kỹ thuật ràng buộc từ lĩnh vực nghiên cứu trí tuệ nhân tạo.
Monash là ngƣời tiên phong trong lĩnh vực này và đƣợc biết đến với công việc
thiết kế ngôn ngữ lập trình ràng buộc logic và ngôn ngữ lập trình chức năng ràng
buộc.
2.2. Nguồn gốc của lập trình ràng buộc
Lập trình ràng buộc (CP) đƣợc phát triển khá sớm so với những ngôn ngữ
11
lập trình phổ biến hiện nay nhƣ Java (1990s). Vào thập niên 60, 70, những ý tƣởng đầu tiên về lập trình ràng buộc có thể đƣợc tìm thấy trong lĩnh vực nghiên cứu trí tuệ nhân tạo (AI) mà cụ thể là ngôn ngữ lập trình logic Prolog (Alain Colmerauer, 1972). Một số ứng dụng đầu tiên của ngôn ngữ này đã đạt đƣợc
những thành tựu đáng kể nhƣ: hệ thống tƣơng tác đồ họa Sketchpad của Ivan Sutherland (1963), hệ thống ThingLab của Alan Borning (1981).
Tuy nhiên, phải đến dòng ngôn ngữ lập trình logic ràng buộc (CLP-
Constraint Logic Programming) mới đánh dấu bƣớc phát triển chính của lập trình
ràng buộc. CLP đƣợc phát triển bởi hai nhà khoa học Jaffar & Lassez (1987)[5],
dựa trên nền tảng lập trình logic, kết hợp cả hai khía cạnh khai báo của lập trình
logic (LP) với giải quyết các ràng buộc. Tiếp theo, một số dòng ngôn ngữ lập trình
ràng buộc lần lƣợt đƣợc phát triển, có t hể kể ra nhƣ: concurrent logic
programming (1980s) , concurrent constraint programming(1990s). Và hiện nay,
Comet đƣợc đánh giá là ngôn ngữ lập trình ràng buộc có ƣu thế nổi bật nhất.
Chúng ta sẽ tìm hiểu ngôn ngữ lập trình Comet trong chƣơng tiếp theo.
2.3. Mô hình lập trình ràng buộc
CP = Model + Search
Hình 2-1. Mô hình CP[3]
Bản chất của CP là kiến trúc hai thành phần: một mô hình lƣu trữ ràng buộc và mô hình tìm kiếm. Mô hình lƣu trữ ràng buộc là tập hợp các ràng buộc mô tả thuộc tính của biến, các mối liên quan, ràng buộc của biến trên miền giá trị, là một hệ thống lý luận về các thuộc tính cơ bản của hệ thống ràng buộc. Mô hình lƣu
12
trữ ràng buộc chứa đựng các ràng buộc đã tích lũy tại một số bƣớc tính toán, hỗ trợ
các truy vấn và toán tử thực hiện trên trên nó. Thành phần tìm kiếm trong CP là duyệt cây với thuật toán backtracking, về bản chất giống nhƣ phƣơng pháp tìm
kiếm nhánh và cận của lập trình truyền thống.
Bài toán: SEND + MORE = MONEY
Để hiểu rõ thêm về các ràng buộc, chúng ta hãy xét một bài toán chơi chữ
cổ điển của Henry Dudeney công bố trên tạp chí Strand năm 1924[10].
Phƣơng trình của bài toán
Mỗi ký tự đại diện cho một con số khác sau, các chữ số hàng đầu của một
số nhiều hơn một chữ số phải là những số khác không. Và một lời giải đúng là tìm
ra giá trị số tƣơng ứng cho từng ký tự và thỏa mãn phƣơng trình trên.
Ở đây. Chúng ta sẽ đề cập đến một phƣơng pháp, áp dụng lập trình ràng
buộc vào giải quyết bài toán.
sendmore(Digits) :- Digits = [S,E,N,D,M,O,R,Y], % Khởi tạo biến Digits :: [0..9], % Xác định miền giá trị của biến S #\= 0, % Constraint: S, M phải khác 0 M #\= 0, alldifferent(Digits), % giá trị của các biến là khác nhau 1000*S + 100*E + 10*N + D % ràng buộc theo biểu thức + 1000*M + 100*O + 10*R + E #= 10000*M + 1000*O + 100*N + 10*E + Y, labeling(Digits). % Tìm kiếm
Code bài toán
Cấu trúc chƣơng trình chƣơng trình có ba phần rõ ràng:
Khai báo các biến và miền giá trị của biến:
Các biến chính là các chữ cái tƣơng ứng trong đề bài: S, E, N, D, M, O, R,
13
Y . Các biến này có miền giá trị thuộc vào đoạn [0,9].
Ràng buộc giữa các biến
Mỗi chữ cái có giá trị là một số nhất đinh, các biến phải có giá trị khác
nhau. S, M là hai biến tƣơng ứng với giá trị đứng đầu các số, vì vậy, S, M là
phải là các chữ số khác 0. Bên cạnh đó, tất cả các biến phải thỏa mãn biểu
thức mà đầu bài đã đƣa ra SEND + MORE = MONEY.
Tìm kiếm: labeling(Digits) // Chƣơng trình sẽ duyệt theo từng biến. Phần
tìm kiếm độc lập với các ràng buộc giữa các biến.
Lời giải cho bài toán:
O = 0, M = 1, Y =2, E = 5, N = 6, D = 7, R = 8, S = 9.
9567
+
1085
10652
2.4. Ứng dụng lập trình ràng buộc
Từ thập niên 90 trở lại đây, nền kinh tế trên toàn thế giới tăng trƣởng mạnh
mẽ, các doanh nghiệp tổ chức thƣơng mại không ngừng ra đời và phát triển lớn
mạnh. Bên cạnh đó, khoa học kỹ thuật công nghệ thu đƣợc những thành tựu rực rỡ,
đem đến những công nghệ tiên tiến nhất và hàng loạt công nghệ, kỹ thuật đƣợc
ứng dụng rộng rãi và thành công trong các ngành kinh tế, thƣơng mại, góp phần
thúc đẩy sự tăng trƣởng kinh tế. Xu hƣớng hiện nay, các ngành công nghiệp, các
lĩnh vực hoạt động sản xuất ứng dụng công nghệ CP ngày càng tăng lên nhanh
chóng. Số lƣợng các công ty ứng dụng thành công công nghệ này tăng lên hàng
năm, có thể kể tên một số công ty, tổ chức điển hình: sân bay Quốc tế Hong Kong, British Airway, SAS, Swissair, cảng Quốc tế Hong Kong, Michelin, Dassault,
14
Ericsson[5] … Đối với lĩnh vực hàng không, CP đƣợc ứng dụng để lập lịch các chuyến bay, hoạt động chuyển phát nhanh…Trong công nghiệp sản xuất, CP ứng dụng trong việc quản lý chuỗi cung ứng sản xuất, lập lịch, phẩn bổ tài nguyên, nguồn lực …
Không chỉ đƣợc ứng dụng thành công trong các ngành kinh tế, công nghệ
CP còn đƣợc ứng dụng thành công trong các lĩnh vực khác nhƣ:
- Lĩnh vực khoa học máy tính: Đồ họa máy tính (thể hiện gắn kết hình học trong phân tich phối cảnh), xử lỹ ngôn ngữ tự nhiên (phân tích cú pháp), hệ
thống cơ sở dữ liệu (bảo đảm/phục hồi tính nhất quán của dữ liệu) …
- Lĩnh vực đời sống, sinh hoạt: Lập thời gian biểu, lập lịch…
- Lĩnh vực sinh học: phân tích phân tử sinh học (chuỗi DNA-protein)…
Kỹ thuật lập trình ràng buộc có thể sử dụng hiệu quả để dự đoán cấu trúc
của một phân tử protein, đƣợc coi là vấn đề quan trọng nhất trong tin sinh học.
15
Hình 2-2. Ứng dụng CP vào phân tích chuỗi protein
CHƢƠNG 3
NGÔN NGỮ LẬP TRÌNH COMET
3.1. COMET là gì?
Tối ƣu hóa tổ hợp là vấn đề mà chúng ta thƣờng xuyên bắt gặp trong cuộc
sống, hoạt động sản xuất, trong các lĩnh vực hoạt động: từ ngành công nghiệp hàng không với các dịch vụ chuyển phát nhanh, chuỗi quản lý cung ứng trong công
nghiệp sản xuất, vấn đề phân phối tài nguyên, nguồn lực… Đây là bài toán khó
mang tính thách thức, là một nhánh nghiên cứu trong lĩnh vực khoa học máy tính, thu hút sự quan tâm, nghiên cứu của các chuyên gia, nhà khoa học trên thế giới.
Bởi bản chất phức tạp của vấn đề tối ƣu hóa, chƣa có phƣơng pháp tiếp cận độc lập
nào có khả năng giải quyết hiệu quả trên tất cả các phƣơng diện. Tuy nhiên, Comet
chính là giải pháp tối ƣu nhất cho bài toán tối ƣu hóa tổ hợp. Theo[7], Comet là
công cụ đƣợc trao tặng giải thƣởng bởi khả năng giải quyết hiệu quả vấn đề tối ƣu
hóa tổ hợp trên nhiều nhiều lĩnh vực nhƣ lập lịch, phân phối tài nguyên, nguồn
lực... Comet là hệ thống lai ghép lập trình ràng buộc(Constraint Programming), lập
trình toán học (Mathematical Programming) với tìm kiếm cục bộ dựa trên ràng
buộc (Constraint-Based Local Search).
Comet là một dòng ngôn ngữ lập trình ràng buộc. Một trong những điểm
sáng tạo chính của Comet là tìm kiếm địa phƣơng dựa trên ràng buộc (CBLS –
Constraint-Based Local Search), một mô hình tính toán dựa trên ý tƣởng quy định
các thuật toán tìm kiếm lân cận với hai thành phần[7]: một mô hình mô tả các ứng
dụng ràng buộc, các ràng buộc kết hợp, các hàm đối tƣợng; một thủ tục tìm kiếm
đƣợc biểu diễn ở mức độ trừu tƣợng cao. CBLS đƣợc xây dựng dựa trên cấu trúc của các thuật toán tìm kiếm, tách biệt mô hình ràng buộc khỏi phần tìm kiếm, tăng
16
tính sử dụng lại của nhiều ứng dụng, khai thác cấu trúc vấn đề để đạt hiệu suất cao. Đồng thời, Comet là ngôn ngữ lập trình hƣớng đối tƣợng bao gồm công cụ tìm kiếm địa phƣơng dựa trên ràng buộc, giải quyết lập trình ràng buộc, giải quyết lập trình toán học.
3.2. Lập trình Comet
3.2.1. Mô hình lập trình Comet
import cotfd:
Solver
// khai báo biến
solver
// post các ràng buộc
} using {
// Tìm kiếm
}
Cấu trúc chung của chƣơng trình code bởi comet[8]
Cấu trúc chung của chƣơng trình code comet gồm 3 phần: phần khai báo
các biến, phần đƣa ra các ràng buộc (constraint) và phần tìm kiếm (constraint- based local search)
Khai báo biến (variables)
Trong cấu trúc chƣơng trình Comet, khi khai báo biến là biến ràng buộc
phải khai báo kèm theo tập xác định của biến. Có thể khai báo biến theo cấu trúc
sau:
var
Ví dụ: Khai báo một biến nguyên có miền giá trị [1, 10]
set {int} dom = {1,3,7};
var
17
Hoặc
Thiết lập biến miền giá trị dom = {1,3,7}, khai báo biến số nguyên y có giá trị
nằm trong miền giá trị dom.
Ràng buộc
Ràng buộc đơn giản chỉ là một quan hệ logic giữa các ẩn số hoặc biến, với
giá trị trong miền giới hạn. Ràng buộc giới hạn các giá trị hợp lệ của biến, tác động
lên miền giá trị để loại bỏ những giá trị không phù hợp sử dụng một thuật toán
phức tạp lọc tất cả không gian tìm kiếm để loại bỏ những giá trị không phù hợp.
Nhƣ vậy, ràng buộc có 2 tính năng chính:
- Kiểm tra tính hợp lệ: Xác định các giải pháp thỏa mãn tất cả các ràng buộc,
nếu không thỏa mãn thì chƣơng trình tự động backtracking.
- Lọc miền giá trị: Sử dụng thuật toán loại bỏ những giá trị không phù hợp.
Mỗi ràng buộc phải đƣợc đẩy lên chƣơng trình với phƣơng thức post trong
khối lệnh solver{} / solverall{} hoặc such that {}(như trong cấu trúc của chương
trình comet).
Dƣới đây là một vài ví dụ đơn giản mô tả các ràng buộc.
solve
cp.post(x != 0);
cp.post(x != 1);
}
Ví dụ 1: Khai báo ràng buộc của biến x là phải khác giá trị 0 và 1
cp.post(x!=y);
Ví dụ 2: Đƣa ra ràng buộc của biến x phải có giá trị khác biến y
cp.post(x>y => a 18 Ví dụ 3: Đƣa ra ràng buộc theo kiểu logic, nếu x lớn hơn y thì a phải nhỏ hơn b. Comet hỗ trợ một số hàm ràng buộc của hệ thống: alldifferent Hàm hệ thống Chức năng Ràng buộc tất cả các biến phải khác binaryKnapsack nhau cardinality Ràng buộc tổng khối lƣợng các danh
mục Ràng buộc về số lần xuất hiện của Table mỗi giá trị Ràng buộc tuples hợp lệ Tìm kiếm (Search) Cũng giống nhƣ mô hình Search trong CP, Search trong Comet gồm hai thành phần: Duyệt cây (Search Tree) và chiến lƣợc tìm kiếm (strategy). Tuy nhiên, tìm kiếm trong mô hình của lập trình ràng buộc là cách thức duyệt cây không đơn định với một thuật toán tìm kiếm backtracking ( mặc định của thuật toán duyệt cây là tìm kiếm theo độ sâu) còn tìm kiếm trong Comet có thể là đơn định, tại mỗi nút của cây tìm kiếm bạn thể kiếm soát những nhánh cây con dƣới cái nút đó. 19 Hình 3-1. Thành phần tìm kiếm trong Comet Bài toán: 16-Hậu Bài toán 16-Hậu chỉ là mở rộng hơn của bài toán 4-Hậu, điều kiện ràng buộc của hai bài toán là nhƣ nhau. Ở chƣơng mở đầu, ta đã xét bài toán 4-Hậu
trong lập trình truyền thống với giải thuật vét cạn và quay lui. Trong chƣơng này, ta sẽ xét bài toán 16-Hậu với ngôn ngữ lập trình ràng buộc Comet để thấy đƣợc những ƣu điểm của lập trình ràng buộc so với lập trình truyền thống. Code bài toán 16-Hậu Hình 3-2. Code bài toán 16 – Hậu bằng Comet 20 Trong đoạn code của chƣơng trình, khai báo biến ràng buộc là Q[i,j] có giá
trị là 0 hoặc 1. Lời giải đúng cho bài toán là xếp đủ các con hậu sao cho trên mỗi
hàng ngang, hàng cột, hàng chéo của bàn cờ, tổng số con hậu luôn là 1. Ràng buộc của bài toán là: Ràng buộc theo hàng: Với i: 1 -> 15 thì tổng số con hậu trên một cp.post(sum(j in S)Q[j,i] == 1); hàng luôn chỉ bằng 1 Ràng buộc theo cột: Với i: 1 -> 15 thì tổng số con hậu trên một cột cp.post(sum(j in S)Q[i,j] == 1); luôn chỉ bằng 1 Ràng buộc theo hàng chéo: i: 1 -> 15 thì tổng số con hậu trên từng cp.post(sum(j in 1..i) Q[j,j+(n-i)]<=1); //chéo phải trên cp.post(sum(j in 1..i) Q[j+(n-i),j]<=1); //chéo trái dưới cp.post(sum(j in 1..i) Q[-j+i+1,j]<=1); // chéo trái trên cp.post(sum(j in 1..i) Q[n-j+1,n-i+j]<=1); //Chéo phải
dưới đƣờng chéo luôn <= 1 forall(i in S, j in S){ try } Tìm kiếm dựa trên ràng buộc Q[i,j] == 0 hoặc Q[i,j] == 1 Cấu trúc chƣơng trình Comet phân rõ mô hình hai thành phần: phần đƣa ra các ràng buộc nằm trong khối lệnh solver trong khối lệnh using {}. Chƣơng trình Comet rất đơn giản, chúng ta chỉ đƣa ra
các ràng buộc của bài toán và điều kiện tìm kiếm mà không cần quan tâm chƣơng 21 trình sẽ tìm kiếm nhƣ thế nào. Đó là một thế mạnh của ngôn ngữ lập trình Comet.
Bên cạnh đó, sự phân chia rõ từng thành phần giúp cho ngƣời lập trình dễ dàng
thêm bớt các ràng buộc mà không ảnh hƣởng gì đến sự vận hành chƣơng trình. Lời giải của bài toán Hình 3–3. Kết quả bài toán 16 – queens bằng Comet Công cụ lập trình Comet hiện nay hay đƣợc sử dụng là Comet Studio. Đây là kết
quả bài toán sắp xếp 16 quân hậu trên bàn cờ 16*16 nhƣ đã nêu ở trên. Kết quả của chƣơng trình là các mảng một chiều 2 chiều với các số 0 và 1. Số 1 biểu thị vị 22 trí có thể đặt quân hậu trên bàn cờ. Số 0 là vị trị không đƣợc phép đặt quân hậu. Là ngôn ngữ lập trình hƣớng đối tƣợng có cấu trúc gần giống ngôn ngữ lập int a = 3; cout << a++ << endl; cout << ++a << endl; cout << a << endl; a *= 2; cout << a << endl; trình C++. Nhƣ ví dụ trên, Comet cũng có câu lệnh cout để in giá trị biến a ra màn hình giống nhƣ trong C++. Bên cạnh đó, các toán tử thực hiện trên biến a cũng giống nhƣ cấu trúc trong C++. Mô hình hai thành phần riêng biệt nhau, do đó ngƣời lập trình dễ dàng thêm
bớt các ràng buộc mà không ảnh hƣởng đến sự vận hành của chƣơng trình, tăng tính sử dụng lại của nhiều ứng dụng. Tích hợp các giải pháp tối ƣu: Tìm kiếm địa phƣơng dựa trên ràng buộc, lập trình ràng buộc, lập trình toán học. import visual; 23 Thƣ viện đồ họa 2D Hình 3-4. Kết quả trực quan bài toán 16 – queens visualization Phù hợp với các hệ điều hành: Mac OS X (32 và 64 bit), Windows, Linux. Trong mô hình tìm kiếm, hệ thống hỗ trợ chƣơng trình tự động backtracking để tìm kiếm các lời giải đúng đắn cho bài toán. Comet[8] tích hợp các API ( C++ API, JAVA API ) mô tả các lớp khác nhau, chức năng, giao diện và thƣ viện. Comet tích hợp C++ API cho phép dữ liệu trao đổi qua lại. Chƣơng
trình sử dụng hệ thống Comet nhƣ là một thƣ viện liên quan tới hai đoạn
mã - Comet code: Giải quyết các vấn đề tối ƣu hóa - C++ code: Giao tiếp với Comet Sự giao tiếp giữa Comet và C++ chỉ liên quan tới dữ liệu đầu ra và
đầu vào của chƣơng trình Comet. Do đó, có rất ít sự thay đổi để tạo một 24 chƣơng trình Comet trong việc sử dụng nó với đoạn mã C++. Bài toán xếp Thời khóa biểu luôn là một bài toán khó, mang tính khoa học
đồng thời mang tính thực tiễn rất cao. Trên thế giới, bài toán Thời khóa biểu (Time Table Problem) đã đƣợc rất nhiều các nhà khoa học quan tâm, nghiên cứu. [6] Đã có hơm 1000 bài báo khoa học đƣợc viết về đề tài này, trong đó có khoảng 300 luận án Tiến sĩ và Thạc sĩ đƣợc bảo vệ xung quanh về bài toán Thời khóa biểu. Riêng đối với Việt Nam, đặc biệt trong các trƣờng Đại học, các trƣờng phổ thông, từ lâu việc xếp thời khóa biểu đã trở thành một vấn đề có tính thời sự, một bài toán gây đƣợc sự chú ý, quan tâm của nhiều ngƣời. Một thực tế hiện nay tại Việt Nam, việc xếp thời khóa biểu phần lớn là đều đƣợc thực hiện thủ công bằng tay. Phƣơng pháp này vừa tốn nhiều chi phí, thời
gian, công sức mà hiệu quả lại không cao. Nhu cầu thực tiễn hiện nay là tin học hóa bài toán lập Thời khóa biểu với tính năng sắp thời khóa biểu chính xác, hiệu quả, giảm bớt thời gian, chi phí công sức của con ngƣời. Tính phức tạp của bài toán lập Thời khóa biểu, các quy định, ràng buộc môn học chặt chẽ, các ràng buộc về lịch dạy của giáo viên, lớp học … hết sức phức tạp, đa dạng. Chính vì vậy, bài toán lập thời khóa biểu là một bài toán khó, có rất ít phần mềm lập thời khóa biểu đƣợc viết và sử dụng tại Việt Nam. Xuất phát từ nhu cầu thực tế, việc xây dựng một chƣơng trình sắp xếp thời khóa biểu là giải pháp cấp bách và cần thiết. Phần mềm giải quyết thỏa mãn tất cả
các quy định, yêu cầu ràng buộc của bài toán. Dựa trên mô hình đào tạo của trƣờng Đại học Công nghệ, đối mỗi kỳ học,
phòng đào tạo quy định danh sách các lớp học học, danh sách các môn học tƣơng
ứng cho từng lớp học và danh sách giảng viên tƣơng ứng với mỗi môn cho từng
lớp... Vì vậy, một Thời khóa biểu chấp nhận đƣợc phải đáp ứng đƣợc tất cả các 25 điều kiện ràng buộc sau: Ràng buộc về ngày học: Một tuần có 5 ngày đi học quy định từ thứ 2 đến
thứ 6. Thứ 7 và chủ nhật là ngày nghỉ cho nên chƣơng trình không xếp lịch học vào các ngày thứ 7 và chủ nhật. Ràng buộc về ngày học, giờ học lựa chọn trước: Trƣờng hợp này chỉ áp
dụng cho lập lịch có chọn trƣớc. Trong trƣờng hợp này, giáo vụ khoa có thể cố định một số thuộc tính nhƣ lớp K54CA luôn học môn tiếng Anh vào thứ 2 phòng 302, ... Ràng buộc về giáo viên: Lịch giảng dạy của mỗi giáo viên không bị chồng
chéo lên nhau. Tức là tại một thời điểm, giáo viên chỉ đảm nhiệm giảng dạy một lớp học. Ràng buộc về ngày nghỉ của giáo viên: Giáo viên có thể đăng ký ngày nghỉ
nào đó cố định trong tuần. Do đó, chƣơng trình không xếp lịch dạy cho giáo viên đó vào ngày mà giáo viên đã đăng ký nghỉ. Ràng buộc về giáo viên nghỉ tiết đầu: Giáo viên có thể đăng ký nghỉ tiết đầu
trong buổi dạy tƣơng ứng. Chƣơng trình không xếp lịch cho giáo viên đó dạy vào các tiết đầu mà giáo viên đó đã đăng ký nghỉ. Ràng buộc về số tiết/buổi: Số tiết học trong một buổi không quá 6 tiết/buổi. Ràng buộc về lớp học: Mỗi phòng học tại một thời điểm chỉ có một lớp học. Ràng buộc về môn học: Tại một thời điểm, một lớp chỉ có thể học một môn
học. Các học phần của cùng môn học không đƣợc dạy trong một ngày. Đối với các môn học lý thuyết phải xếp vào phòng lý thuyết, môn học thực
hành xếp vào phòng thực hành. Phòng học phải đảm bảo đầy đủ điều kiện học tập (số chỗ ngồi luôn lớn hơn hoặc bằng sĩ số của lớp). Ràng buộc về lập lịch có lựa chọn trước: Việc lập Thời khóa biểu có thể
đƣợc thực hiện với một số lựa chọn đƣợc khởi tạo trƣớc nhƣ cố định ngày 26 học hay giờ bắt đầu cho một môn nào đó của một lớp,… Một hệ thống lập Thời khóa biểu hoạt động hiệu quả nhất thì phải đáp ứng đƣợc các yêu cầu nghiệp vụ của bài toán. Do đó, chúng ta sẽ lần lƣợt giải quyết từng ràng buộc của bài toán. var var var var Khai báo các biến ràng buộc sử dụng trong chƣơng trình: n là số buổi học cần phải sắp lịch. Mảng day, hour, room chứa các biến
ràng buộc về ngày giảng dạy, giờ bắt đầu và phòng học của các buổi học. Mảng day chứa danh sách các ngày học trong tuần (từ thứ 2 đến thứ 6), có giá trị ràng buộc trong đoạn [2, 6]. Mảng hour là danh sách các thời điểm bắt đầu tiết học, có giá trị ràng buộc trong tập giá trị {1, 3, 4}. Mảng room là danh sách các phòng học phục vụ cho quá trình giảng dạy và học tập. Ngoài ra, còn có mảng session có hai giá trị là 0 (tƣơng ứng với buổi sáng) hoặc 1 (tƣơng ứng với buổi chiểu), mảng start[i]==24*day[i]+ 8*session[i] + hour[i] duration lƣu khoảng thời gian của mỗi môn học/buổi. Mảng start là lƣu thời gian bắt đầu của từng môn học trong một tuần đƣợc ánh xạ từ các ngày học, buổi học và giờ học của môn đó Ràng buộc về giáo viên: Mảng startTemp là danh sách thời điểm giảng dạy tƣơng ứng với từng giảng viên. Mảng durationTemp lƣu khoảng thời gian giảng dạy của giảng viên đó. Do tính chất ràng buộc, tại một thời điểm mỗi giáo viên chỉ có thể đảm nhận dạy
một môn học. Vì vậy, đối với những giảng viên dạy từ hai lớp trở lên hoặc hai cp.post(cumulative(startTemp,durationTemp,arr1,1)); 27 môn trở lên thì tại thời điểm giảng dạy startTemp, trong khoảng thời gian
durationTemp, một giáo viên chỉ dạy một môn. Ta có thể khái quát ràng buộc đó
nhƣ sau: Hàm cumulative muốn nói mỗi công việc giảng dạy i, bắt đầu từ thời gian
startTemp[i], diễn ra trong khoảng thời gian duration[i], ứng với một giáo viên (arr[i]=1) thì chỉ cho phép dạy một môn học. Ràng buộc về ngày nghỉ của giáo viên: Chƣơng trình quản lý danh sách những ngày nghỉ mà giáo viên đã đăng ký. if(sessionTemp[j]==sessionOff[k]) cp.post(dayTemp[j]!=dayoff[k]); Để đảm bảo chƣơng trình không xếp lịch dạy cho giáo viên vào những buổi mà
giáo viên đã đăng ký nghỉ thì ta phải khái quát ràng buộc nhƣ sau sessionTemp là buổi dạy của giáo viên, sessionOff là buổi mà giáo viên đăng ký nghỉ, dayTemp là ngày phải đi dạy và dayoff là ngày mà giáo viên đăng ký buổi nghỉ (sessionOff). cp.post(hourTemp [j]!=1) Ràng buộc về giáo viên nghỉ tiết đầu: hourTemp là tập hợp giờ bắt đầu dạy theo danh sách giáo viên đã đăng ký nghỉ tiết đầu. Do dó, để thỏa mãn điều kiện không xếp lịch dạy vào các tiết đầu mà giáo viên nào đó đã đăng ký nghỉ, thì ta phải post lên ràng buộc giờ bắt đầu hourTemp[j] luôn phải khác 1 (tiết 1). cp.post(hour[i] + duration[i] <= 6); Ràng buộc về số tiết/buổi: Theo chƣơng trình đào tạo, phòng Đào tạo quy định số tiết học trong một buổi tối đa là 5 tiết. Để đảm bảo thảo mãn điều kiện số tiết/buổi tối đa là 5, chƣơng trình post ràng buộc hour[i] + duration[i] <= 6. Ở đây duration đƣợc tính theo khoảng thời gian của một tiết. Ràng buộc về môn học: 28 Trong các danh sách các môn học của phòng Đào tạo, một số môn học có
số đơn vị học trình cao (≥4), có thể đƣợc chia thành nhiều học phần phân bổ vào
các buổi học khác nhau. Ví dụ nhƣ môn tiếng Anh 2 có 6 đvht sẽ đƣợc chia thành Solver cp.post(day[i] < day[i+1]); hai học phần,… Để đảm bảo trong một lớp, các học phần cùng môn học không dạy
cùng một ngày thì ngày học học phần thứ i phải trƣớc ngày học học phần thứ i+1. int[] arr_index = subjects[i];
var forall(i in 0..subjectNumber-1)
{
} function void SubjectConstraint(var cp.post(room[i]==room[j]=>((start[i]+duration[i]<=start[j])||(
start[j]+duration[j]<=start[i]))); Ràng buộc về lớp học: Tại một thời điểm, một phòng học chỉ có thể có một lớp học. Để đảm bảo điều kiện này, nếu room[i]==room[j] (cùng một phòng), thời điểm kết thúc
(bằng thời điểm bắt đầu start cộng với khoảng thời gian duration) của i luôn nhỏ hơn thời điểm kết thúc (bằng thời điểm bắt đầu start cộng với khoảng thời gian duration) của j hoặc ngƣợc lại. Nên cố định phòng học đối với lớp khi học cùng một môn vào những buổi khác nhau. Ràng buộc về lập lịch có lựa chọn trước: Đối với việc lập lịch có lựa chọn trƣớc, giáo vụ khóa có thể lựa chọn cố định cp.post(day[i]==dayInit[i]); forall(i in 0..dayInit.getSize()-1)
{
if(dayInit[i]!=0)
} 29 ngày học hay giờ học cho môn nào đó của lớp nào. Do đó, việc xếp lịch của
chƣơng trình phải trùng với những giá trị khởi tạo mà giáo viên đã lựa chọn. cp.post(hour[i]==hourInit[i]); forall(i in 0..hourInit.getSize()-1)
{
if(hourInit[i]!=0)
} Mô hình của chƣơng trình gồm hai thành phần: Thành phần giao diện đƣợc viết bằng ngôn ngữ C# và thành phần xử lý các ràng buộc bài toán đƣợc viết bằng
ngôn ngữ Comet. Phần giao diện cập nhật, xử lý các thao tác của ngƣời dùng nhƣ thêm, xóa…các dữ liệu của chƣơng trình và ghi ra file data.txt. Phần code comet đọc dữ liệu từ file data.txt và xử lý các ràng buộc đã đƣa ra của bài toán và ghi kết quả ra file output.txt. Kết quả trong file output.txt sẽ đƣợc đọc bởi thành phần giao
diện và hiện thị trực quan hơn cho ngƣời dùng. data.txt output.txt C# Code Comet Code Hình 4-1. Mô hình bài toán Hệ thống lập Thời khóa biểu gồm các chức năng chính: Quản lý danh sách giáo viên, danh sách môn học, danh sách phòng học, danh sách khoa. Phân công giảng dạy Lập thời khóa biểu. 30 Cho phép xem thời khóa biểu theo lớp, theo giáo viên, theo phòng học. 4.3.1. Các chức năng quản lý danh sách giảng viên, danh sách môn học, danh
sách phòng học, danh sách khoa. Chức năng quản lý giảng viên: Hình 4-2. Quản lý giảng viên Chức năng này để quản lý thông tin về giảng viên (tên giảng viên, thuộc khoa nào), đồng thời quản lý lịch nghỉ của từng giảng viên (ngày nghỉ, buổi nghỉ hay nghỉ tiết đầu) bằng cách click chuột vào checkbox tƣơng ứng. Bên cạnh đó, chức năng này cho phép ngƣời dùng có thể thêm một giảng viên, xóa một giảng 31 viên trong danh sách hay cập nhật lại thông tin giảng viên. Chức năng quản lý phòng học Hình 4-3. Quản lý phòng học Chức năng này cho phép ngƣời sử dụng xem danh sách phòng học, thêm mới phòng học, xóa một phòng học trong danh sách, cập nhật lại thông tin một phòng học. Phong học đƣợc quản lý theo tên phòng, số chỗ ngồi vào loại phòng 32 (phòng thực hành hay phòng lý thuyết ). Chức năng quản lý môn học Hình 4-4. Quản lý môn học Quản lý theo tên môn học, số tiết/ tuần, loại môn (phân loại theo: môn lý thuyết, môn thực hành). Căn cứ vào “loại môn” chƣơng trình sẽ phân lịch học từng môn theo phòng học tƣơng ứng (phòng thực hành và phòng lý thuyết). Chức năng này cho phép ngƣời sử dụng xem danh sách môn học, thêm mới môn học, xóa, cập 33 nhật môn học. Quản lý lớp học Hình 4-5. Quản lý lớp học Tƣơng tự nhƣ các chức năng quản lý môn học, quản lý phòng học, chức năng quản lý lớp học cũng cho phép hiển thị thông tin về lớp học (tên lớp, sĩ số), cho phép ngƣời sử dụng thêm mới một lớp, xóa hay cập nhật lại thông tin của một 34 lớp. Chức năng quản lý Khoa Hình 4-6. Quản lý khoa Chức năng này cho phép ngƣời dùng thêm, bớt hay cập nhật lại một Khoa. Bên cạnh đó, chức năng quản lý Khoa hiển thị danh sách các Khoa trong hệ đào 35 tạo của trƣờng. 4.3.2. Chức năng phân công giảng dạy Hình 4-7. Chức năng phân công giảng dạy Chức năng này đƣợc thực hiện thủ công bằng tay bởi giáo vụ khoa, ngƣời phân công giảng viên giảng dạy từng môn, từng lớp. Chức năng này chủ yếu là hỗ trợ cho chức năng lập lịch. Giáo vụ khoa phải sắp xếp từng môn học cho từng lớp 36 theo quy định của phòng đào tạo và phân công giáo viên giảng dạy môn học đó. 4.3.3. Chức năng xếp thời khóa biểu Hình 4-8. Chức năng xếp Thời khóa biểu Chức năng xếp thời khóa biểu đƣợc phân thành hai lựa chọn: Lập lịch mới hoàn toàn và Lập lịch chọn trƣớc (ngƣời sử dụng có thể lựa chọn, cố định môn học nào đó học vào buổi nào, tiết mấy). Sau khi chƣơng trình thực hiện lập lịch xong, 37 xuất hiện một thông báo “Lập lịch đã hoàn thành”. 4.3.4. Chức năng xem thời khóa biểu theo tên lớp, tên giảng viên, phòng học Để ngƣời dùng có thể tiện theo dõi thời biểu theo lớp, giảng viên hay phòng
học thì hệ thống đã cung cấp chức năng hiển thị thời khóa biểu theo tên lớp, giảng viên, phòng học. Nhƣ vậy, không chỉ có các lớp học, giảng viên và các phòng học cũng có thời khóa biểu riêng rõ ràng và khoa học. Xem thời khóa biểu theo tên lớp 38 Hình 4-9. Xem Thời khóa biểu theo lớp Xem thời khóa biểu theo tên giảng viên Hình 4-10. Xem Thời khóa biểu theo giảng viên Xem thời khóa biểu theo tên phòng học 39 Hình 4-11. Xem Thời khóa biểu theo phòng học Khóa luận trình bày tổng quát ngôn ngữ lập trình ràng buộc với các ví dụ minh họa để thấy đƣợc điểm khác biệt giữa lập lịch ràng buộc và lập trình truyền thống. Lập trình ràng buộc đang là một công nghệ tạo ra một hƣớng giải quyết mới cho các bài toán tổ hợp. Bên cạnh đó, khóa luận tìm hiểu chi tiết ngôn ngữ lập trình Comet, một ngôn ngữ lập trình ràng buộc tiên tiến nhất hiện nay và đang đƣợc ứng dụng rộng rãi. Bằng các kiến thức đã thu nhận thông qua việc tìm hiểu ngôn ngữ lập trình
ràng buộc Comet, khóa luận đã áp dụng vào giải quyết bài toán “lập Thời khóa biểu” cho các trƣờng đại học. Chƣơng trình thực hiện lập thời khóa biểu một cách tự động, chính xác, khắc phục đƣợc những khó khăn trong công việc lập thời khóa biểu bằng tay trên giấy. Tuy nhiên chƣơng trình vẫn tồn tại một số hạn chế: - Chƣơng trình mới thực hiện phân xếp lịch theo lớp, chƣa đề cập tới việc phân lịch cho từng nhóm trong lớp. - Chƣơng trình chƣa đề cập và giải quyết ràng buộc với cùng một môn
học, cùng một lớp học thì nên sắp lịch cho lớp học học môn đó cố định tại một phòng học. Một số hƣớng phát triển của bài toán: - Giải quyết các vấn đề còn tồn tại để hoàn thiện chƣơng trình - Phát triển hệ thống lập Thời khóa biểu cho cả các THPT, THCS … 40 - Phát triển hệ thống lập Thời khóa biểu cho hệ đào tạo tín chỉ. [1]. Alexander Shrijver, Combinatorial Optimization, September 1, 2002. [2]. Luca Bortolussi, Alessandro Dal Palù, and Agotino Dovier, Two constraint–based tools for protein folding. [3]. Pascal Van Hentenryck Laurent Michel, Comet in context, 2003. [4]. Pascal Van Hentenryck Laurent Michel, Constraint-Based Combinators for Local Search , 2005. [5]. Roman Barták, Constraint propagation and backtracking–based search, Charles University, Faculty of Mathematics and Plysics, Department of Theoretical Computer Science, February, 1995. [6]. Bài toán thời khóa biểu và phần mềm xếp thời khóa biểu,
http://www.vnschool.net//modules.php?name=News&file=article&sid=35 [7]. Comet, http://www.comet-online.org/Welcome.html. [8]. Comet Tutorial, Dynamic decision technologies inc, august 28, 2009. [9]. Constraint Programming,
http://en.wikipedia.org/wiki/Constraint_programming 41 [10]. http://en.wikipedia.org/wiki/Verbal_arithmetic3.2.2. Ví dụ
3.3. Ƣu điểm của Comet
CHƢƠNG 4
ỨNG DỤNG COMET VÀO BÀI TOÁN
LẬP THỜI KHÓA BIỂU
4.1. Đặt vấn đề xây dựng bài toán
4.2. Giải quyết bài toán
4.3. Thực nghiệm
CHƢƠNG 5:
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
TÀI LIỆU THAM KHẢO
