I HC QUC GIA THÀNH PH H CHÍ MINH
I HC KHOA HC T NHIÊN


C SEN


NGHIÊN CU BÀI TOÁN XP LCH TRC
CHO Y TÁ

LU
NGÀNH H THNG THÔNG TIN





Thành ph H Chí Minh - 2013
I HC QUC GIA THÀNH PH H CHÍ MINH
I HC KHOA HC T NHIÊN


C SEN


NGHIÊN CU BÀI TOÁN XP LCH TRC
CHO Y TÁ

NgH THNG THÔNG TIN
60 48 05

LU
NG DN KHOA HC: TS N



Thành ph H Chí Minh  2013
i

Li c
Tôi xin chân thành cảm ơn Thầy Đinh Bá Tiến và Cô Viviane Gascon đã nhiệt tình
tận tâm hướng dẫn, động viên khuyến khích tạo động lực lớn cho tôi trong suốt quá
trình thực hiện luận văn.
Tôi xin chân thành cảm ơn Quý Thầy Cô trường Đại học Khoa học Tự nhiên đã tận
tình giảng dạy trong suốt quá trình học tập.
Tôi xin bày tỏ lòng biết ơn sâu sắc đến Gia Đình và cảm ơn các Bạn Bè đã góp ý,
ủng hộ, giúp đỡ tôi trong suốt quá trình làm luận văn.

Học viên thực hiện
Vũ Ngọc Sen

ii

Mc lc
Lời cảm ơn i
Mục lục ii
Danh mục các bảng iv
Danh mục các hình v
Phần mở đầu 1
Lý do thực hiện và mục tiêu của đề tài 1
Bố cục luận văn 2

Chương 1. Tổng quan về bài toán Xếp lịch y tá 3
1.1 Giới thiệu bài toán Xếp lịch y tá 3
1.2 Các hướng tiếp cận cho bài toán Xếp lịch y tá 5
Chương 2. Phát biểu bài toán Xếp lịch y tá và Các thuật giải liên quan 12
2.1 Các khái niệm của bài toán 12
2.2 Mô hình toán học của bài toán và các ràng buộc 14
2.3 Thành phần lời giải 20
2.4 Các thuật giải liên quan 20
Chương 3. Thuật giải đề nghị 28
3.1 Các bước chuyển trong thuật giải 29
3.2 Thuật giải đề nghị 31
3.3 Giai đoạn 1: Xếp lịch làm việc cho y tá 34
3.4 Giai đoạn 2: Xếp lịch trực cho y tá 41
Chương 4. Thực nghiệm và thảo luận 43
Chương 5. Kết luận và hướng phát triển 48
5.1 Kết luận 48
iii

5.2 Hướng phát triển 49
Tài liệu tham khảo 50
Phụ lục 56
A. Kết quả xếp tay trên Access của Bộ dữ liệu 01 57
B. Kết quả xếp tay trên Access của Bộ dữ liệu 04 61


iv

Danh mc các bng
Bảng 2.1. Nhu cầu y tá cho các ca làm việc theo từng ngày trong tuần 13
Bảng 2.2. Nhu cầu y tá cho các ca trực theo từng ngày trong tuần 13

Bảng 2.3. Số ngày làm việc và số lượng y tá theo loại và nhóm 14
Bảng 2.4. Các hàm mục tiêu thành phần của các ràng buộc mềm 19
Bảng 4.1. Thông tin nhu cầu y tá của 5 bộ dữ liệu theo tuần 43
Bảng 4.2. Kết quả thực nghiệm 45
Bảng 4.3. Mục tiêu trải đều ca trễ cho các y tá chính thức 46
Bảng 4.4. Mục tiêu tối thiểu số lượng y tá chính thức làm ca trễ vào thứ Sáu 46
Bảng 4.5. Mục tiêu tối thiểu việc thiếu y tá 46
Bảng 4.6. Mục tiêu tối đa số lượng y tá làm vào thứ Hai và thứ Sáu 47
Bảng 4.7. Mục tiêu tối thiểu số lượng y tá làm việc nhiều hơn số ngày làm việc được
quy định trong hợp đồng 47


v

Danh mc các hình
Hình 1.1. Các hướng tiếp cận cho bài toán NRP 7
Hình 2.1. Minh hoạ thuật giải VNS
[56]
24
Hình 2.2. Mã giả của thuật giải VNS
[37]
25
Hình 2.3. Minh hoạ thuật giải ILS
[37]
: 26
Hình 2.4. Mã giả của thuật giải ILS
[37]
27
Hình 3.1. Bước chuyển đơn: 29
Hình 3.2. Bước hoán chuyển đồng loạt trong một ngày 29

Hình 3.3. Bước hoán chuyển đồng loạt trong hai ngày 30
Hình 3.4. Bước hoán chuyển đồng loạt trong ba ngày 30
Hình 3.5. Bước chuyển ca trực 30
Hình 3.6. Thuật giải cho bài toán xếp lịch y tá 31
Hình 3.7. Mã giả của thuật giải Lặp tìm kiếm cục bộ 36
Hình 3.8. Mã giả của thuật giải Tabu Search với Bước chuyển đơn 38
Hình 3.9. Mã giả của thuật giải Steepest Descent với Bước chuyển ca trực 42
1

Phn m u
Lý do thc hin và mc tiêu c tài
Ngày nay, theo đà phát triển của thế giới về mọi mặt kinh tế-văn hoá-xã hội, nhu
cầu chăm sóc sức khoẻ con người ngày càng nhiều kèm theo yêu cầu chất lượng
càng cao. Cùng với sự phát triển về qui mô cũng như chất lượng của bệnh viện, việc
sắp xếp số lượng lớn y tá vào làm các ca trực sao cho phù hợp và thoả đáng những
nhu cầu của y tá cũng như nhu cầu của bệnh viện nói chung hay của từng khoa,
từng loại ca trực nói riêng, đảm bảo các y tá luôn cảm nhận thoải mái, công bằng
trong công việc và bệnh viện giảm thiểu được chi phí đã trở nên phức tạp hơn
nhiều. Do đó, bài toán Xếp lịch trực cho Y tá (Nurse Rostering Problem-NRP) đang
rất được quan tâm và ứng dụng thực tế rộng rãi. Đề tài này tập trung nghiên cứu và
giải quyết bài toán NRP thực tế của một Bệnh viện đa khoa ở Canada – Centre
hospitalier régional de Trois-Rivières. Bệnh viện này chuyên cung cấp các dịch vụ
về phẫu thuật với 11 phòng phẫu thuật và 1 phòng chuyên khoa mắt. Hiện nay số
lượng y tá của bệnh viện không đủ để đáp ứng nhu cầu khám và phẫu thuật trong
khi việc xếp lịch trực bằng MS Access chiếm nhiều thời gian của y tá trưởng mà
vẫn chưa hợp lý do chưa đáp ứng được nhu cầu sở thích cá nhân của các y tá, một
số y tá phải làm quá nhiều ca trễ… khiến các y tá tự chuyển đổi ca làm việc nhiều.
Dẫn đến thực trạng có nhiều ngày bệnh viện không đủ y tá để đáp ứng nhu cầu
khám và phẫu thuật. Hiện nay tình trạng thiếu y tá khá nhiều và thường xuyên. Vì
vậy, việc xếp lịch y tá sao cho cân bằng ca trễ giữa các y tá chính thức, tối thiểu số

lượng y tá chính thức làm ca trễ vào thứ Sáu, giảm thiểu tình trạng thiếu y tá, tối đa
số lượng y tá làm việc vào thứ Hai và thứ Sáu đang là nhu cầu rất cần thiết của bệnh
viện. Trong đó ca trễ là ca làm việc bắt đầu từ 10h00 sáng đến 6h15 chiều. Mục tiêu
của luận văn là đưa ra được thuật giải giúp giải quyết bài toán này. Luận văn đã đề
nghị một thuật giải Metaheuristic để giải quyết. Kết quả thực nghiệm của thuật giải
được so sánh với kết quả xếp bằng MS Access được lấy từ thực tế.
2

B cc lu
Luận văn gồm có 5 chương như sau:
- Chương 1. Tổng quan về bài toán Xếp lịch Y tá: gồm giới thiệu tổng quan
bài toán và các hướng tiếp cận hiện nay để giải quyết bài toán.
- Chương 2. Phát biểu bài toán Xếp lịch Y tá và Các thuật giải liên quan: trình
bày chi tiết bài toán thực tế của một bệnh viện đa khoa tại Canada mà luận
văn tập trung giải quyết gồm những khái niệm của bài toán, các ràng buộc,
mục tiêu và mô hình toán học của bài toán; trình bày các thuật toán liên quan
đến thuật giải đề nghị ở chương 3.
- Chương 3. Thuật giải đề nghị: trình bày chi tiết về thuật giải được đề nghị để
giải quyết bài toán.
- Chương 4. Thực nghiệm và thảo luận: trình bày về các kết quả đạt được của
thuật giải đề nghị.
- Chương 5. Kết luận và hướng phát triển: rút ra kết luận đồng thời đưa ra
hướng phát triển trong thời gian tới.

3

 Tng quan v bài toán Xp lch y tá
1.1 Gii thiu bài toán Xp lch y tá
Bài toán Xếp lịch Y tá (Nurse Rostering Problem - gọi tắt là NRP) đại diện cho
công việc rất quan trọng tại các bệnh viện hiện đại trên thế giới, đó là hoạt động

quản lý y tá và các ca làm việc. Yêu cầu của bài toán là phân công các y tá vào
những ca làm việc có đặc điểm khác nhau với số lượng y tá rất giới hạn và họ có
kỹ năng cũng như hợp đồng làm việc khác nhau, trong khi phải thỏa mãn rất nhiều
quy tắc của bệnh viện, tập quán làm việc, các luật và những sở thích cá nhân. Việc
giải quyết tốt bài toán xếp lịch y tá sẽ giúp khai thác hiệu quả nguồn nhân lực, cân
bằng công việc cho mọi y tá, đáp ứng được sở thích cá nhân, ảnh hưởng tốt đến
điều kiện và tinh thần làm việc của các y tá, điều này giúp nâng cao chất lượng
chăm sóc sức khỏe của bệnh viện[52].
Bên cạnh tầm quan trọng về mặt thực tế thì việc giải quyết các bài toán NRP phức
tạp cũng là thách thức khoa học cho các nhà nghiên cứu vì NRP thuộc lớp các bài
toán NP khó [55]. NRP chính là một loại đặc biệt của bài toán xếp lịch (Scheduling
Problem) với rất nhiều những ràng buộc cụ thể và không đồng nhất, nên rất khó để
giải quyết bài toán này một cách hiệu quả. Dù vậy, đây là một trong những bài toán
có ứng dụng thực tế rất rộng lớn và được nghiên cứu rộng rãi trên thế giới trong
suốt 40 năm qua [21] và cho đến ngày nay, điển hình là các nghiên cứu trong một
số năm gần đây như:
- Năm 2013, Ilina Stoilkovska ứng dụng Thuật giải Lặp tìm kiếm cục bộ
(Iterated Local Search) để giải quyết bài toán xếp lịch cho y tá tại một số
bệnh viện ở Na Uy [45], với lời giải khởi tạo được xây dựng bằng thuật giải
Lập trình ràng buộc.
- Năm 2010, với bài toán xếp lịch y tá phức tạp được đưa ra trong cuộc thi
quốc tế lần thứ nhất INRC-2010 (the First International Nurse Rostering
Competition), hai tác giả Zhipeng Lü và Jin-Kao Hao [63] dùng phương
4

pháp tìm kiếm lân cận thích ứng (Adaptive Neighborhood search) trong đó
có sử dụng thuật toán tìm kiếm Tabu (Tabu search), với kết quả thu được tốt
hơn ở 12 bộ dữ liệu, và đạt bằng ở 39 bộ dữ liệu trong tổng số 60 bộ dữ liệu.
Trong khi nhóm đoạt giải nhất của cuộc thi, C. Valouxis, C. Gogos, G.
Goulas, P. Alefragis và E. Housos [27] dựa trên hướng tiếp cập lai hai giai

đoạn (Two-phase Hybrid) chia bài toán thành nhiều bài toán con và áp dụng
phương pháp quy hoạch tính toán (Mathematical Programming). Một hướng
tiếp cận lai khác cũng đạt được kết quả tốt do K. Burke, Tim Curtois [35] đề
xuất với phương pháp tìm kiếm Variable Depth Search được cải tiến với các
phương thức leo đồi (Hill Climbing) sử dụng nhiều vùng lân cận tìm kiếm
khác nhau, và dùng thuật toán quy hoạch động (Dynamic Programming) để
xây dựng lịch trực cho từng y tá.
- Vào những năm 2000, với dữ liệu của bệnh viện lớn ở Anh, nhiều tác giả
như K.Burke, Aickelin, Dowsland, Thompson, White, J. Li đã dành nhiều
thời gian nghiên cứu với các giải thuật khác nhau để đưa ra những lời giải
ngày càng tối ưu cho bài toán xếp lịch y tá này [4, 5, 6, 31, 49, 61]. Aickelin
và Dowsland 2000, 2003; Aickelin và White 2004 đề xuất những hướng tiếp
cận khác nhau dựa trên thuật giải di truyền (Genetic Algorithms), trong đó
thuật giải Hill-climbing GA và Indirect GA cho kết quả tốt nhất [7]. Trong
khi một hướng tiếp cận khác dựa trên hệ thống Learning Classifier system
được Li và Aickelin 2004 áp dụng. Burke et al. 2003, Li và Aickelin 2003
cũng thu được các kết quả rất khả thi với thuật giải tìm kiếm Tabu search
hyperheuristic và Bayesian Optimization Algorithm.
Một số thuật ngữ chính của bài toán gồm [23]:
- Chu kỳ xếp lịch (Planning Period): đây là khoảng thời gian mà các nhân viên
được xếp lịch. Thường thì chu kỳ này là một tháng hoặc bốn tuần trong bài
toán xếp lịch y tá.
5

- Nhóm kỹ năng (Skill Category): nhóm này phân loại các nhân viên theo trình
độ chuyên môn, kỹ năng hoặc trách nhiệm.
- Loại ca (Shift type): chính là những ca làm việc ở bệnh viện, những ca trực
này có thời gian bắt đầu và kết thúc rất rõ ràng. Chẳng hạn như các bài toán
xếp lịch y tá thường có ba ca làm việc là ca sớm (07:00-15:00), ca trễ (15:00-
22:00), và ca khuya (22:00-07:00) hoặc các biến thể nhỏ của chúng.

- Các ràng buộc bao phủ (Coverage Constraints): cho biết số lượng nhân viên
cần thiết cho từng nhóm kỹ năng, cho mỗi ca làm việc hoặc cho từng khoảng
thời gian trong suốt chu kỳ xếp lịch. Các ràng buộc này thể hiện cho nhu cầu
nhân lực. Thường thì trong các bệnh viện, các ràng buộc bao phủ này được
xác định từ hệ thống đo lường công việc (như là hệ thống phân loại bệnh
nhân), các tỷ lệ y tá-bệnh nhân, hoặc do dự đoán.
- Các ràng buộc liên quan đến thời gian (Time Related Constraints): những
ràng buộc này diễn đạt tất cả hạn chế về lịch cá nhân. Nghĩa là những yêu
cầu cá nhân, sở thích cá nhân, và những ràng buộc nhằm cân bằng khối
lượng công việc giữa các nhân viên cùng nhóm.
- Ràng buộc cứng (Hard Constraints): là toàn bộ những yêu cầu phải được
thỏa mãn với tất cả các chi phí.
- Ràng buộc mềm (Soft Constraints): rất cần thiết nhưng có thể vi phạm để
đưa ra được lời giải khả thi.
- Quy chế làm việc (Work Regulations): là hợp đồng giữa các nhân viên và
bệnh viện, thường được gọi là hợp đồng lao động. Hợp đồng này đặt ra các
ràng buộc về thời gian cho các y tá.
1.2 ng tip cn cho bài toán Xp lch y tá
Bài toán Xếp lịch y tá NRP có hai cách xếp lịch cơ bản được dùng rộng rãi là xếp
lịch theo chu kỳ (Cyclic Scheduling) và xếp lịch không theo chu kỳ (Non-cyclic
6

Scheduling) [12]. Trong cách xếp lịch theo chu kỳ, mỗi y tá sẽ làm việc với cùng
một lịch trực duy nhất tại các giai đoạn xếp lịch liên tiếp, giúp cho các y tá biết
được lịch làm việc cố định của họ trong thời gian dài đủ ổn định để họ sắp xếp công
việc, tuy nhiên cách này thiếu linh hoạt trong việc đáp ứng những yêu cầu cá nhân
đột xuất. Còn với cách xếp lịch không theo chu kỳ thì trong từng giai đoạn xếp lịch
sẽ có một lịch trực mới cho từng y tá, giúp thoả mãn được những yêu cầu cá nhân,
giải quyết được những yêu cầu thay đổi theo ngày nhưng phải tạo lịch mới tại mỗi
giai đoạn xếp lịch và các mô hình thuật toán sẽ phức tạp hơn [32].

Trong những thập kỷ qua, có rất nhiều hướng tiếp cận được đề xuất để giải quyết
bài toán NRP tuỳ thuộc vào đặc điểm của bài toán và những nhu cầu của các bệnh
viện với mục tiêu là đưa ra các lịch trực khả thi hoặc tốt nhất có thể. Ba loại phương
pháp tổng quát được sử dụng thường xuyên là quy hoạch tính toán (Mathematical
Programming), các thuật giải heuristic và các phương pháp AI. Hầu hết các thuật
giải heuristic tập trung giải quyết những bài toán xếp lịch theo chu kỳ trong khi quy
hoạch tính toán và AI thì được dùng cho cả những bài toán xếp lịch theo chu kỳ và
không theo chu kỳ.
Các hướng tiếp cận của bài toán NRP có thể được chia thành hai nhóm chính sau
gồm hướng tiếp cận tối ưu hoá (Optimization Approach) và hướng tiếp cận quyết
định (Decision Approach). Nhóm tối ưu hoá thường dựa trên các phương pháp quy
hoạch tính toán, còn nhóm quyết định lại sử dụng các thuật giải heuristic và các
phương pháp AI. Có thể tổng quát các hướng tiếp cận cho bài toán NRP theo hình
1.1
1.2.1 ch tính toán (Mathematical Programming)
Quy hoạch tính toán (Mathematical Programming – gọi tắt là MP) được dùng trong
hướng tiếp cận tối ưu hoá với một số mục tiêu như: tối thiểu hoá lượng y tá, tối đa
mức độ thoả mãn về sở thích hay yêu cầu đặc biệt của các y tá Các thuật toán dựa
trên MP thường đạt được những lời giải tối ưu với chi phí thấp nhất. Tuy nhiên
phương pháp này lại ít được áp dụng phổ biến do những công thức MP khó để diễn
7


Hình 1.1. Các hướng tiếp cận cho bài toán NRP
8

đạt số lượng lớn những mục tiêu và ràng buộc phức tạp, cũng như hạn chế về thời gian
tìm kiếm nên hướng này thường chỉ được dùng cho những bài toán xếp lịch đơn giản
với kích thước dữ liệu nhỏ [2], hoặc dùng kết hợp với các thuật giải heuristic. Hướng
tiếp cận này được áp dụng lần đầu trong bài toán NRP vào những năm 1970 và 1980

nhằm đưa ra các công thức và kỹ thuật giải quyết bài toán, điển hình là quy hoạch tính
toán (Mathematical Programming) [29, 30], các kỹ thuật Brand-and-bound [62], quy
hoạch mục tiêu (Goal Programming) [44, 47], các thuật toán iterative [1, 52]. Trong
những năm 1990, các kỹ thuật tiến bộ hơn nữa được biết đến là quy hoạch tuyến tính
(Linear Programming) lai quy hoạch số nguyên (Integer Programming) và tối ưu hoá
mạng (Network Optimisation) [14, 42, 50]…
1.2.2 Nhóm các thut gii heuristic
Trong khi các phương pháp quy hoạch tính toán gặp khó khăn với những bài toán xếp
lịch phức tạp hoặc có kích thước lớn vì mất quá nhiều thời gian tính toán để đưa ra lời
giải tối ưu thì các thuật giải heuristic lại đưa ra được các lời giải khả thi với thời gian
ngắn hợp lý mặc dù các lời giải này có thể không phải là lời giải tốt nhất. Nhóm thuật
giải này được chia thành hai loại: các thuật giải cổ điển (Classical Heuristic) và các
Metaheuristic.
1.2.2.1 Các thuật giải heuristic cổ điển (Classical Heuristic)
Các thuật giải cổ điển được phát triển rất sớm từ khoảng những năm 1960 gồm có
những thuật giải khởi tạo lời giải và tìm kiếm cục bộ (Local Search) [46]. Thuật giải
heuristic khởi tạo lời giải (Constructive Heuristic) là phương pháp xây dựng lời giải
một cách từ từ trong khi cố gắng giữ chi phí thấp nhất có thể, điển hình là Greedy (tạm
dịch là thuật toán Tham lam): bắt đầu với một lời giải thành phần chưa có yếu tố nào,
sau đó tiến hành lựa chọn rồi thêm các yếu tố vào lời giải, việc này được lặp lại đến
khi xây dựng được lời giải khả thi [46]. Trong khi đó, thuật giải heuristic tìm kiếm cục
bộ (local search heuristic) lại bắt đầu từ một lời giải khởi tạo ban đầu S, thuật giải sẽ
tìm lời giải tốt hơn trong vùng lân cận N(S) của lời giải S. Tiến trình này được lặp lại
cho đến khi không tìm được lời giải nào tốt hơn. Và lời giải tốt nhất được tìm thấy này
9

còn được gọi là lời giải tối ưu cục bộ [46]. Một số heuristic cơ bản như Shuffling và
Greedy Shuffling (tạm dịch là Xáo trộn và Xáo trộn tham lam). Ý tưởng của Shuffling
là xây dựng một lời giải tệ nhất cho bài toán, sau đó lời giải được cải tiến dần bằng
cách đổi một phần lịch trực của y tá này với một phần lịch trực của các y tá khác, mỗi

bước đổi này được gọi là một ‘shuffle’. Các thuật giải theo kiểu Greedy Shuffling
cũng tương tự Shuffling, tính toán chi phí của tất cả shuffles cho mọi y tá, sau đó liệt
kê chúng theo mức độ chi phí và chọn thực hiện shuffle mà lời giải được cải tiến tốt
nhất. Việc này được lặp đi lặp lại nhiều lần nhất có thể [12]. Thuật giải này cùng
những biến thể của nó được sử dụng rộng rãi trong nhiều bài báo [11, 24, 34, 36…]
1.2.2.2 Metaheuristic
Metaheuristic định hình một lớp các phương pháp quan trọng để giải quyết các bài
toán tối ưu rời rạc hay tổ hợp khó. Thường thì những phương pháp này được dùng để
giải quyết những bài toán mà các thuật giải heuristic cổ điển không làm được, nó cho
phép tìm kiếm trên một không gian lời giải rộng lớn và giúp chương trình thoát khỏi
các tối ưu cục bộ. Metaheuristic thường là dạng lai của các thuật toán heuristic. Trong
những năm gần đây Metaheuristic được phát triển rất phổ biến vì nếu không thể đưa ra
được lời giải tốt nhất cho bài toán thì vẫn đưa ra được lời giải khả thi tốt trong thời
gian hợp lý, trong khi nhóm phương pháp quy hoạch tính toán MP có khả năng không
đưa ra được lời giải và mất rất nhiều thời gian tìm kiếm. Hơn nữa, hầu hết các
Metaheuristic tương đối đơn giản để cài đặt và dễ dàng để áp dụng cho những mục tiêu
phức tạp. Tuy nhiên, Metaheuristic thường không đạt hiệu quả cao với những bài toán
xếp lịch có nhiều ràng buộc quá phức tạp và khó đưa vào các heuristic. Những bài toán
này sẽ được giải quyết tốt hơn với hướng tiếp cận Lập trình ràng buộc (CP- Constraint
Programming)- một nhánh của nhóm phương pháp trí tuệ nhân tạo (AI- Artificial
Intelligence). Ngoài ra, điểm bất lợi nữa của các Metaheuristic là vấn đề lựa chọn giá
trị phù hợp cho các tham số, cách làm thông dụng nhất hiện nay là dựa vào kinh
nghiệm. Các Metaheuristic được phân loại thành:

10

Metaheuristic khi to li gii (Constructive Metaheuristic)
Một số Metaheuristic tiêu biểu của nhóm này là các thuật giải Greedy random adaptive
search procedures (GRASP) [41], Greedy Random Adaptive Memory Programming
search (GRAMPS), Ant Colony Optimization [59], Adaptive Memory Programming.

Metaheuristic tìm kim lân cn (Neighbourhood Search Metaheuristic)
Gồm có Tôi luyện thép (Simulated Annealing) [55], Tabu search [24], Iterated Local
search [36], Neural Networks, Threshold Accepting, và Variable Neighbourhood
search [34]. Từ lời giải ban đầu, các thuật giải sẽ thực hiện lặp đi lặp lại việc tìm kiếm
trong miền không gian tìm kiếm của bài toán nhằm mục đích tìm ra lời giải tối ưu. Tại
mỗi bước lặp, thuật giải sẽ tìm kiếm và chỉ chọn ra một lời giải duy nhất để làm lời
giải cho bước lặp tiếp theo. Thuật giải sẽ duyệt trong miền không gian láng giềng của
lời giải hiện tại để chọn ra lời giải thay thế cho lời giải hiện tại ở bước lặp kế sau. Mỗi
lời giải trong không gian láng giềng của lời giải hiện tại được gọi là một láng giềng
của lời giải hiện tại. Sự tác động lên lời giải hiện tại để biến nó thành một lời giải láng
giềng của nó gọi là một bước chuyển (move). Trong các Metaheuristic tìm kiếm lân
cận, hai vấn đề quan trọng nhất cần quan tâm là tính tăng cường (intensification) và
tính đa dạng (diversification) của quá trình tìm kiếm, tính tăng cường là khả năng tập
trung tìm kiếm sâu ở những vùng không gian mà ta dự đoán là sẽ chứa lời giải tối ưu,
tính đa dạng là khả năng tìm đến những vùng không gian lời giải mới nhằm thoát ra
khỏi các vùng chứa điểm tối ưu cục bộ.
Metaheuristic qun th (Population Metaheuristic)
Tương tự như thuật giải Metaheuristic tìm kiếm lân cận, với điểm khác biệt chính là
với mỗi bước lặp thuật giải sẽ chọn ra một tập các lời giải, trong khi nhóm
Metaheuristic tìm kiếm lân cận chỉ chọn một lời giải duy nhất. Các thuật giải điển hình
của nhóm này là Evolutionary algorithms [15], các thuật giải di truyền (GA-Genetic
algorithms [6, 61]), Scatter search, Path re-linking [41] …
Ngoài ra trong những năm gần đây các thut gii lai Hybrid Metaheuristic được
phát triển và sử dụng rộng rãi vì khả năng tìm được lời giải tốt hơn nhiều [46], thường
11

là kết hợp giữa các thành phần khác nhau hoặc giữa các Metaheuristic có hiệu quả cao,
điển hình là:
- Thuật giải Memetic Algorithm _ một thuật giải Tìm kiếm Quần thể được kết
hợp từ thuật giải Heuristic Tìm kiếm Cục bộ và thuật giải Di truyền (Genetic

algorithms) [43].
- Burke et al. (2001) lai Memetic Algorithm và Tabu Search cho bài toán xếp lịch
y tá đã cho thấy rằng cách lai này cho lời giải tốt hơn so với lời giải chỉ từ thuật
giải Tabu Search [33].
- Một thuật giải lai khác giữa Quy hoạch số nguyên (Integer Programming) và
Variable Neighbourhood Search (VNS) áp dụng cho bài toán xếp lịch y tá với
tính ràng buộc cao cho kết quả tốt hơn so với thuật giải Di truyền (Genetic
algorithms) [26].
- Burke (1999) lai giữa Tabu Search và Greedy Shuffling để giải quyết bài toán
xếp lịch y tá của một bệnh viện ở Bỉ.
1.2.3  tu nhân to (Artificial Intelligence - AI)
Từ những năm 1980 đến nay, các phương pháp trí tuệ nhân tạo cũng được áp dụng cho
bài toán xếp lịch [49] như Hệ thống chuyên gia (Expert systems) [51], Hệ thống tri
thức (Knowledge based systems) [28], và đặc biệt là phương pháp Lập trình ràng buộc
(Constraint Programming - CP) [13, 39]. Lập trình ràng buộc đã thu hút được nhiều sự
quan tâm và được thương mại hoá vì rất hữu dụng và có hiệu quả tốt khi sử dụng cho
những bài toán với nhiều ràng buộc quá phức tạp mà Metaheuristic khó giải quyết
được. CP có thể dễ dàng diễn đạt các ràng buộc của bài toán, tuy nhiên, điểm bất lợi
của CP là với những bài toán yêu cầu tìm một lời giải tối ưu hoặc gần tối ưu trong rất
nhiều các lời giải khả thi thì phương pháp này hiếm khi đưa ra được lời giải tốt nhất
[2].
12

 Phát biu bài toán Xp lch y tá và Các thut
gii liên quan
Bài toán cần giải quyết là bài toán xếp lịch cho y tá của bệnh viện đa khoa Centre
hospitalier régional de Trois-Rivières tại Canada. Hiện nay lịch làm việc của các y tá
trong bệnh viện do y tá trưởng sắp xếp bằng MS Access với tổng số lượng hơn 50 y tá.
Việc xếp lịch này chiếm nhiều thời gian của y tá trưởng nhưng chưa được hợp lý với
nhiều y tá dẫn đến tình trạng y tá tự chuyển đổi ca làm việc nhiều, xảy ra thực trạng có

nhiều ngày không đủ y tá để đáp ứng nhu cầu khám và phẫu thuật tại bệnh viện. Do
đó, xếp lịch một cách hợp lý, cân bằng ca trễ giữa các y tá chính thức, tối thiểu số
lượng y tá chính thức làm ca trễ vào thứ Sáu, giảm thiểu tình trạng thiếu y tá, tối đa số
lượng y tá làm việc vào thứ Hai và thứ Sáu đang là nhu cầu lớn của bệnh viện. Trong
đó ca trễ là ca làm việc bắt đầu từ 10h00 sáng đến 6h15 chiều.
2.1 Các khái nim ca bài toán
Ca làm việc (Shifts):
Ca làm việc của các y tá được xếp theo bốn loại gồm ca sớm, ca sáng, ca trễ, và ca
cuối tuần. Từ thứ Hai đến thứ Sáu với 11 phòng phẫu thuật và 1 phòng chuyên khoa
mắt thì bệnh viện gồm 3 ca làm việc:
- Ca sớm (Early) từ 7h30 sáng đến 3h45 chiều: cần 25 y tá
- Ca sáng (Morning) từ 8h00 sáng đến 4h15 chiều: cần 8 y tá
- Ca trễ (Late) từ 10h00 sáng đến 6h15 chiều: cần 3 y tá
Những ngày cuối tuần gồm Chủ Nhật và thứ Bảy có một ca làm việc duy nhất là:
- Ca cuối tuần (Weekend) từ 7h30 sáng đến 3h45 chiều: cần 3 y tá làm việc.
- Ngoài ra cần lưu ý thứ tự các ngày trong tuần theo yêu cầu của bài toán được
sắp xếp như sau: Chủ Nhật – thứ Hai – thứ Ba – – thứ Bảy.
Nhu cầu y tá cho các ca làm việc của bệnh viện được thể hiện trong bảng 2.1.

13

Bảng 2.1. Nhu cầu y tá cho các ca làm việc theo từng ngày trong tuần
Ca làm vic
S ng y tá cn thit

T2
T3
T4
T5
T6

T7
CN
Ngày l
Ca sớm
25
25
25
25
25
0
0
0
Ca sáng
8
8
8
8
8
0
0
0
Ca trễ
3
3
3
3
3
0
0
0

Ca cuối tuần
0
0
0
0
0
3
3
3
Ca trực (Duties):
Những y tá được phân công vào các ca làm việc cũng sẽ được phân công trực vào cuối
tuần hoặc trực đêm trong tuần. Khi được phân công trực cuối tuần, y tá được ở nhà
nhưng phải luôn sẵn sàng để đến bệnh viện làm việc khi bệnh viện cần trong những
trường hợp khẩn cấp.
- Trực đêm bắt đầu từ 6h00 tối hôm trước đến 7h30 sáng hôm sau cho các đêm
trong tuần từ thứ Hai đến thứ Năm: cần 3 y tá.
- Trực cuối tuần từ 6h00 tối thứ Sáu đến 7h30 sáng thứ Hai: cần 4 y tá.
Nhu cầu y tá cho các ca trực của bệnh viện được thể hiện trong bảng 2.2.
Bảng 2.2. Nhu cầu y tá cho các ca trực theo từng ngày trong tuần
Ca trc
S ng y tá cn thit

T2
T3
T4
T5
T6
T7
CN
Ngày l

Trực đêm
3
3
3
3
0
0
0
0
Trực cuối tuần
0
0
0
0
4
4
4
4

Y tá:
Hiện tại bệnh viện có ba nhóm y tá cụ thể như sau:
- Nhóm y tá chính thức, còn gọi là nhóm Regular. Nhóm này gồm các y tá làm
việc chính thức tại bệnh viện. Họ luôn được phân công làm việc trừ trường hợp
họ xin nghỉ và được y tá trưởng chấp thuận.
- Nhóm Flying Squad: những y tá trong nhóm này sẽ làm thay cho các y tá nghỉ
bệnh hoặc khi thiếu y tá.
- Nhóm y tá đã nghỉ hưu, còn gọi là nhóm Retired. Trong trường hợp dù đã cho
các y tá thuộc hai nhóm trên làm thêm giờ nhưng vẫn thiếu y tá để xếp lịch, thì
nhóm y tá đã nghỉ hưu sẽ được phân công làm việc.
14


Mỗi nhóm gồm có hai loại y tá như sau:
o Y tá làm toàn thời gian, hay còn gọi là y tá Full time. Những y tá này
làm 5 ngày trong một tuần.
o Y tá làm bán thời gian, còn gọi là y tá Part time. Số ngày làm việc của
từng y tá tuỳ theo hợp đồng mà họ đã ký kết với bệnh viện.
Số ngày làm việc trong một tuần và lượng y tá trong từng nhóm được thể hiện trong
bảng 2.3:
Bảng 2.3. Số ngày làm việc và số lượng y tá theo loại và nhóm
Nhóm
Loi y tá
S ngày làm vic
S ng y tá
Nhóm Chính thức
Full time
5 ngày /tuần
36
Part time
4 ngày /tuần
2
3 ngày /tuần
1
Nhóm Flying Squad
Full time
5 ngày /tuần
5
Part time
4 ngày /tuần thứ nhất và
3 ngày /tuần thứ hai
3

3 ngày /tuần thứ nhất và
4 ngày /tuần thứ hai
2
Nhóm nghỉ hưu

2 ngày /tuần
1
1 ngày /tuần
1

2.2 Mô hình toán hc ca bài toán và các ràng buc
Bài toán có hai loại ràng buộc gồm ràng buộc cứng (Hard Constraints) là những điều
kiện mà lời giải bắt buộc phải thoả mãn, và ràng buộc mềm (Soft Constraints) là
những điều kiện không cần thiết phải đáp ứng nhưng cần tối thiểu những vi phạm ràng
buộc mềm. Một lịch (hay có thể gọi là lời giải) đáp ứng được tất cả ràng buộc cứng thì
được gọi là lời giải khả thi. Yêu cầu về chu kỳ xếp lịch của bài toán là bốn tuần.
Mô hình toán học của bài toán với các tham số như sau:
- N
F
là danh sách các y tá làm toàn thời gian (Full time).
- N
P
là danh sách các y tá làm bán thời gian (Part time).
- d
dsw
là số lượng y tá mà bệnh viện cần cho loại ca s trong ngày d của tuần w, với
d = 1,2, ,7; s = 1 (ca sớm), 2 (ca sáng), 3 (ca trễ), 4 (ca cuối tuần); w=1, 2, 3,
4.
- sh
nw

là tổng số ngày (hoặc ca làm việc) mà y tá n phải làm việc trong tuần w.
15

- nu
3dw
là số lượng y tá cần để phân công làm các ca trễ trong bốn tuần.
- maxdutyWE thể hiện tổng số lần trực cuối tuần tối đa của một y tá trong khoảng
thời gian bốn tuần.
- maxdutyEN cho biết tổng số lần trực đêm tối đa của y tá trong thời gian bốn
tuần.
Và các biến:






với n= N
F

N
P
; s=1,2,3,4; d=1,2, ,7; w=1,2,3,4;






với n= N

F

N
P
; d=1,2, ,7; w=1,2,3,4;






Các ràng buộc cứng gồm:
- H1: Mỗi y tá n phải làm đủ số ngày làm việc sh
nw
trong tuần w mà họ đã ký kết
với bệnh viện trong hợp đồng lao động.






- H2: Mỗi y tá n chỉ làm việc tối đa một ca s trong ngày d.




- H3: Từ thứ Hai đến thứ Sáu, nếu y tá n làm ca sớm (s=1) trong ngày d của tuần
w, thì y tá này có thể làm ca sớm, ca sáng, ca trễ, hoặc là không làm việc vào
ngày kế tiếp.











- H4: Từ thứ Hai đến thứ Sáu, nếu y tá n làm ca sáng (s=2) trong ngày d của tuần
w, thì y tá này có thể làm ca sáng, ca trễ, hoặc là không làm việc vào ngày kế
16

tiếp.


 





 





 







- H5: Từ thứ Hai đến thứ Sáu, nếu y tá n làm ca trễ (s=3) trong ngày d của tuần
w, thì y tá này chỉ có thể làm ca trễ hoặc là không làm việc vào ngày kế tiếp.


 





  







- H6: Nếu y tá n làm ca cuối tuần (s=4) vào thứ Bảy của tuần w, thì y tá này cũng
phải làm việc vào Chủ nhật của tuần tiếp theo.


 






- H7: Những y tá làm việc cuối tuần sẽ không được trực vào cuối tuần đó. Và
ngược lại, những y tá đã làm trực vào cuối tuần w sẽ không được làm việc cuối
tuần đó.


 


- H8: Nếu y tá n trực cuối tuần vào thứ Bảy của tuần w, thì y tá này cũng phải
trực cuối tuần vào Chủ nhật của tuần tiếp theo.








- H9: Nếu y tá n xin nghỉ làm vào ngày d của tuần w, thì y tá này sẽ không được
phân công làm việc trong ngày đó.


 


Các ràng buộc mềm:

- S1: Trong mỗi tuần w, y tá n không nên làm việc nhiều hơn số ngày làm việc
sh
nw
được quy định trong hợp đồng lao động, với s S



 





với 


là số ngày y tá n làm nhiều hơn số ngày làm việc sh
nw
.
- S2: Y tá n nên được phân công làm việc vào ca s mà y tá yêu cầu (sở thích)
trong ngày d của tuần w.
17



 








với 


là số lần y tá n được phân công làm việc vào ca s không đúng với yêu
cầu của y tá đó.
- S3: Tổng số lần trực cuối tuần của y tá n không nên nhiều hơn số lần trực cuối
tuần tối đa trong bốn tuần maxdutyWE theo hợp đồng làm việc của y tá.



 



với 


là số lần trực cuối tuần vượt quá maxdutyWE của y tá n trong bốn tuần.
- S4: Tổng số lần trực đêm của y tá n không nên nhiều hơn số lần trực đêm tối đa
trong bốn tuần maxdutyEN theo hợp đồng làm việc của y tá





 




với 


là số lần trực đêm vượt quá maxdutyEN của y tá n trong bốn tuần.
- S5: Y tá n nên được phân công trực vào ngày d của tuần w mà y tá yêu cầu.


 






với 


là số lần y tá n được phân công trực không đúng với yêu cầu của y tá.
Các mục tiêu của bài toán và các hàm mục tiêu thành phần:
- O1: Trải đều ca trễ cho các y tá chính thức. Nghĩa là mỗi y tá n nên làm vừa đủ
số lượng ca trễ trung bình cho từng y tá trong bốn tuần.








 













 



với 

là số lượng y tá cần để phân công làm các ca trễ trong bốn tuần. N
F

là danh sách các y tá làm toàn thời gian (Full time). N
P
là danh sách các y tá
làm bán thời gian (Part time).
18

Ví dụ:

o Số lượng y tá cần để phân công làm ca trễ trong từng ngày là 3.
o Tổng số ngày có ca trễ trong mỗi tuần là 5.
o Chu kỳ xếp lịch là bốn tuần.
o 

= 3 x 5 x 4 = 60
o N
F
= 32, N
P
= 3.
Vậy


= 1.71 ca trễ / y tá. Nghĩa là mỗi y tá chỉ nên làm từ 1 đến 2 ca trễ
trong bốn tuần.
Hàm mục tiêu của O1 như sau:


 






 






Trong đó, 


là số y tá làm chưa đủ và 


là số y tá làm vượt quá số lượng ca
trễ trung bình cho từng y tá trong bốn tuần. 

là điểm phạt cho mỗi vi phạm.
- O2: Tối thiểu số lượng y tá chính thức làm ca trễ vào thứ Sáu. Với 

là điểm
phạt cho mỗi y tá chính thức được phân công làm ca trễ vào thứ Sáu.


 







- O3: Tối thiểu việc thiếu y tá.




 





với 


là số y tá thiếu để phân công làm ca s trong ngày d của tuần w.
Hàm mục tiêu của O3 như sau với 

là điểm phạt cho từng y tá bị thiếu.


 








- O4: Tối đa số lượng y tá làm vào thứ Hai và thứ Sáu.


  




 



tương đương với hàm sau:


 



 



 



