Luận văn thạc sĩ: Ứng dụng công nghệ thông tin vào xếp lịch trực y tá bằng tu chỉnh lặp có trọng số

Luận văn thạc sĩ nghiên cứu công nghệ thông tin ứng dụng tu chỉnh lặp có trọng số vào giải quyết bài toán xếp lịch trực y tá, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện

• Tác giả: Nguyễn Thị Tuyết Nga
• Người hướng dẫn: TS. Đỗ Tuấn Anh
• Trường học: Đại Học Bách Khoa
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Ứng Dụng Phương Pháp Tu Chỉnh Lặp Có Trọng Số Vào Bài Toán Xếp Lịch Trực Y Tế
• Loại tài liệu: luận văn thực số
• Năm xuất bản: 2004
• Địa điểm: Thành phố Hồ Chí Minh

Tóm tắt

I. Giới thiệu

Công việc xếp lịch trực cho y tá thường rất phức tạp và tốn nhiều thời gian. Hiện nay, ở nước ta, công việc này vẫn được thực hiện bằng tay. Do đó, nhu cầu nghiên cứu và tìm giải pháp cho bài toán này là rất cần thiết. Trong khi đó, trên thế giới, bài toán xếp lịch trực cho y tá đã được quan tâm nghiên cứu phát triển từ những năm 1980. Trải qua nhiều giai đoạn phát triển, đã có những thành công nhất định. Một số sản phẩm đã được áp dụng cho các bệnh viện khác nhau trên thế giới. Tuy nhiên, đến nay vẫn chưa thật sự có một giải pháp nào giải quyết triệt để cho tất cả các trường hợp. Đặc điểm của bài toán xếp lịch trực cho y tá là rất đặc thù cho một trường hợp cụ thể vì thế bài toán luôn là một hướng mở cho nhiều nhà nghiên cứu.

1.1. Bài toán xếp lịch trực y tá

Công việc xếp lịch trực y tá toán khá nhiều thời gian và công sức, ngoài ra kết quả thường không được tối ưu. Vì thế hiện nay ở các nước tiên tiến trên thế giới, công việc này thường được mô hình hóa và giải quyết bằng máy tính. Một cách tổng quát, bài toán thường chia ra làm hai loại ràng buộc: ràng buộc cứng và ràng buộc mềm. Ràng buộc cứng là những quy định và luật bắt buộc phải thỏa mãn. Ràng buộc mềm thường là những yêu cầu hay ước muốn từ phía các y tá, không bắt buộc phải thỏa mãn tất cả, và được dùng để tham khảo tối ưu bài toán.

II. Các nghiên cứu liên quan

Trong chương này, các phương pháp giải quyết bài toán xếp lịch trực y tá sẽ được giới thiệu. Song song đó tác giả cũng sẽ trình bày những công trình liên quan đến kỹ thuật tu chỉnh lặp có trọng số. Những nghiên cứu này sẽ là nền tảng cho việc xây dựng giải thuật sau này. Kỹ thuật tìm kiếm cục bộ (Local Search) đã tạo được nhiều tiếng vang và sự chú ý trong việc giải quyết các bài toán khó và phức tạp. Một trong những ứng dụng quan trọng và tiêu biểu của phương pháp này là bài toán xếp lịch, trong số đó, bài toán phân công trực y tá là một điển hình.

2.1. Các nghiên cứu liên quan đến bài toán xếp lịch trực y tá

Nghiên cứu về bài toán xếp lịch trực y tá đã được thực hiện từ lâu và có nhiều phương pháp khác nhau được áp dụng. Các phương pháp này bao gồm quy hoạch toán học (Mathematical Programming), lập trình ràng buộc (Constraint Programming) và nhận xét các phương pháp xếp lịch trực y tá. Mỗi phương pháp đều có những ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp là rất quan trọng để đạt được kết quả tối ưu.

III. Phương hướng giải quyết bài toán

Kỹ thuật tu chỉnh lặp có trọng số (Weighted Iterative Repair) là một trong những phương pháp được áp dụng để giải quyết bài toán xếp lịch trực y tá. Mối quan hệ giữa lượng thông tin, chi phí và số lần lặp là rất quan trọng trong quá trình tìm kiếm giải pháp. Duy trì sự phân biệt giữa ràng buộc cứng và ràng buộc mềm là một yếu tố quyết định trong việc tối ưu hóa bài toán. Việc xác định trọng số ban đầu cho ràng buộc cứng cũng cần được thực hiện một cách cẩn thận.

3.1. Ứng dụng tu chỉnh lặp có trọng số vào bài toán xếp lịch trực y tá

Mô hình hóa bài toán là bước đầu tiên trong việc áp dụng kỹ thuật tu chỉnh lặp có trọng số. Lựa chọn độ sâu cho giải thuật và tiêu chuẩn đánh giá là những yếu tố quan trọng trong quá trình này. Giải thuật tu chỉnh lặp có trọng số (Weighted Iterative Repair – WIR) sẽ được áp dụng để tìm kiếm giải pháp tối ưu cho bài toán xếp lịch trực y tá. Ràng buộc đã biến đổi và bổ sung một số heuristic để cải thiện giải thuật là những bước tiếp theo cần thực hiện.

IV. Thiết kế ứng dụng xếp lịch trực y tá

Việc thiết kế ứng dụng xếp lịch trực y tá cần phải đảm bảo tính hiệu quả và khả năng sử dụng. Xây dựng thư viện phần mềm cho giải thuật tu chỉnh lặp có trọng số là một trong những nhiệm vụ quan trọng. Ứng dụng này không chỉ giúp giải quyết bài toán xếp lịch mà còn có thể mở rộng cho các bài toán khác trong lĩnh vực y tế. Các chức năng của hệ thống xếp lịch trực y tá cần được thiết kế một cách hợp lý để đáp ứng nhu cầu của người dùng.

4.1. Hiện thực giải thuật

Xây dựng thư viện phần mềm cho giải thuật tu chỉnh lặp có trọng số là một trong những nhiệm vụ quan trọng. Ứng dụng này không chỉ giúp giải quyết bài toán xếp lịch mà còn có thể mở rộng cho các bài toán khác trong lĩnh vực y tế. Các chức năng của hệ thống xếp lịch trực y tá cần được thiết kế một cách hợp lý để đáp ứng nhu cầu của người dùng.

V. Chạy thử nghiệm chương trình

Phương án chạy thử nghiệm chương trình là bước quan trọng để đánh giá hiệu quả của giải thuật. Các kết quả thử nghiệm sẽ được phân tích và đánh giá để rút ra những nhận xét về hiệu quả của giải thuật. Việc phân tích kết quả thử nghiệm sẽ giúp cải thiện và tối ưu hóa giải thuật trong tương lai.

5.1. Phương án chạy thử nghiệm

Phương án chạy thử nghiệm sẽ được thực hiện trên nhiều kịch bản khác nhau để đánh giá tính hiệu quả của giải thuật. Kết quả thử nghiệm sẽ được so sánh với các phương pháp khác để đưa ra những nhận xét chính xác về hiệu quả của giải thuật tu chỉnh lặp có trọng số.

VI. Kết luận

Đóng góp của đề tài là rất quan trọng trong việc phát triển các giải pháp cho bài toán xếp lịch trực y tá. Hướng mở rộng của đề tài sẽ là nghiên cứu sâu hơn về các phương pháp tối ưu hóa khác và áp dụng vào các lĩnh vực khác trong y tế. Việc phát triển ứng dụng xếp lịch trực y tá sẽ góp phần nâng cao hiệu quả công việc và giảm thiểu thời gian cho các y tá.

6.1. Đóng góp của đề tài

Đề tài đã đóng góp một phần quan trọng trong việc phát triển các giải pháp cho bài toán xếp lịch trực y tá. Hướng mở rộng của đề tài sẽ là nghiên cứu sâu hơn về các phương pháp tối ưu hóa khác và áp dụng vào các lĩnh vực khác trong y tế.

Trích đoạn nội dung tài liệu

Ñaïi Hoïc Quoác Gia Tp. Hoà Chí Minh TRÖÔØNG ÑAÏI HOÏC BAÙCH KHOA ------------------- NGUYEÃN THÒ TUYEÁT NGA ÖÙNG DUÏNG TU CHÆNH LAËP COÙ TROÏNG SOÁ VAØO GIAÛI QUYEÁT BAØI TOAÙN XEÁP LÒCH TRÖÏC Y TAÙ Chuyeân ngaønh: Coâng Ngheä Thoâng Tin Maõ soá ngaønh: 01.10 LUAÄN VAÊN THAÏC SÓ TP. HOÀ CHÍ MINH, THAÙNG 12 NAÊM 2004 Ñaïi hoïc Quoác Gia Tp. Hoà Chí Minh COÄNG HOØA XAÕ HOÄI CHUÛ NGHÓA VIEÄT NAM TRÖÔØNG ÑAÏI HOÏC BAÙCH KHOA Ñoäc laäp - Töï do - Haïnh phuùc --------- --------- NHIEÄM VUÏ LUAÄN VAÊN THAÏC SÓ Hoï vaø teân hoïc vieân: NGUYEÃN THÒ TUYEÁT NGA Phaùi: Nöõ Ngaøy thaùng naêm sinh: 10 - 03 - 1977 Nôi sinh: Quaûng Ngaõi Chuyeân ngaønh: Coâng Ngheä Thoâng Tin Maõ soá: CNTT12-018 I.

TEÂN ÑEÀ TAØI: ÖÙng duïng phöông phaùp Tu chænh laëp coù troïng soá vaøo baøi toaùn xeáp lòch tröïc y taù. NHIEÄM VUÏ VAØ NOÄI DUNG: Nhieäm vuï cuûa ñeà taøi laø nghieân cöùu öùng duïng phöông phaùp Tu chænh laëp coù troïng soá vaøo baøi toaùn xeáp lòch tröïc y taù ôû caùc beänh vieän. NGAØY GIAO NHIEÄM VUÏ: 26/02/2004 IV. NGAØY HOAØN THAØNH NHIEÄM VUÏ: 25/11/2004 V.

HOÏ VAØ TEÂN CAÙN BOÄ HÖÔÙNG DAÃN: TS- DÖÔNG TUAÁN ANH CAÙN BOÄ HÖÔÙNG DAÃN CHUÛ NHIEÄM NGAØNH BOÄ MOÂN QUAÛN LYÙ NGAØNH TS-DÖÔNG TUAÁN ANH Noäi dung vaø ñeà cöông luaän vaên thaïc só ñaõ ñöôïc Hoäi Ñoàng Chuyeân Ngaønh thoâng qua. Ngaøy thaùng naêm PHOØNG ÑAØO TAÏO SAU ÑAÏI HOÏC KHOA QUAÛN LYÙ NGAØNH TOÙM TAÉT Giaûi thuaät Tu chænh laëp coù troïng soá xuaát phaùt töø yù töôûng khaù ñôn giaûn. Khi rôi vaøo traïng thaùi toái thieåu cuïc boä, giaûi thuaät seõ taêng troïng soá cuûa caùc raøng buoäc vi phaïm. Vieäc naøy laøm thay ñoåi giaù trò chi phí cuûa lôøi giaûi hieän taïi cho ñeán khi moät lôøi giaûi laân caän trôû neân coù theå chaáp nhaän ñöôïc.

Nhieàu baøi toaùn giaûi heä raøng buoäc trong thöïc teá thuoäc daïng raøng buoäc quaù möùc (coù soá raøng buoäc quaù nhieàu) vì theá khoâng theå tìm thaáy lôøi giaûi khaû thi naøo thoaû taát caû caùc raøng buoäc. Baøi toaùn naøy thöôøng chia raøng buoäc ra laøm hai loaïi: raøng buoäc cöùng (hard constraint) vaø raøng buoäc meàm (soft constraint). Trong ñoù, raøng buoäc cöùng laø raøng buoäc phaûi thoaû maõn, raøng buoäc meàm laø raøng buoäc khoâng baét buoäc phaûi thoaû maõn. Muïc tieâu cuûa baøi toaùn laø thoaû maõn taát caû raøng buoäc cöùng vaø toái thieåu soá raøng buoäc meàm vi phaïm.

Ñaëc ñieåm naøy cuûa baøi toaùn raøng buoäc quaù möùc ñaõ gaây khoù khaên cho kyõ thuaät Tu chænh laëp coù troïng soá. Bôûi vì, giaûi thuaät naøy duøng troïng soá ñeå phaân bieät raøng buoäc cöùng vaø raøng buoäc meàm. Tuy nhieân, trong suoát quaù trình tìm kieám, vieäc taêng troïng soá cuûa raøng buoäc vi phaïm seõ laøm “meùo moù” troïng soá ban ñaàu chæ ñoä quan troïng töông ñoái giöõa caùc raøng buoäc. Keát quaû laø troïng soá cuûa raøng buoäc meàm coù theå ngang baèng hay lôùn hôn raøng buoäc cöùng.

Vì theá, giaûi thuaät seõ khoâng theå tìm thaáy lôøi giaûi khaû thi. Ñeå coù theå öùng duïng giaûi thuaät Tu chænh laëp coù troïng soá vaøo baøi toaùn xeáp lòch tröïc y taù, taùc giaû seõ döïa vaøo khaùi nieäm “laëp laïi” raøng buoäc cuûa Cha et al. vaø choïn xaây döïng giaûi thuaät theo höôùng “hoïc hoûi” cuûa Thornton vaø Sattar. Maëc khaùc, khoâng gioáng nhö caùc phöông phaùp giaûi quyeát cho baøi toaùn xeáp lòch tröïc y taù tröôùc, taùc giaû choïn höôùng tieáp caän ñeå giaûi thuaät Tu chænh laëp coù troïng soá vöøa coù chöùc naêng xaây döïng lôøi giaûi khaû thi vöøa coù chöùc naêng toái öu lôøi giaûi.

Ñoàng thôøi qua ñoù taùc giaû cuõng muoán chöùng minh raèng caùc giaûi thuaät tìm kieám cuïc boä hoaøn toaøn khoâng bò leä thuoäc vaøo lôøi giaûi ban ñaàu. Trang i Giôùi thieäu ABSTRACT Weighted iterative repair technique originates from a simple idea. When stucking on a local optimum solution, the algorithm will increase weights of all violated constraints. This changes the cost of the current solution until a lower cost solution becomes accessible.

Many real-world constraint satisfaction problems can be over-constrained. For this reason, it is impossible to find a feasible solution that satisfies all contraints. These problems contain a set of hard constraints that have to be satisfied and a set of soft constraints whose satisfaction is desirable but not mandatory. The objective of the problem is to satisfy all hard constraints and to minimize the violations of soft constraints.

This feature of over-constrained problems causes difficulties in using weighted iterative repair techniques, because the techniques use weight to distinguish hard and soft constraints. However, during the search, increasing the weights of the violated constraints can override the relative importance of constraints. This can make weights of soft constraints equal or greater than those of hard constraints. So the algorithm can not find feasible solutions.

In order to apply the weighted iterative repair techniques into the nurse scheduling, author based on concept of repeating hard constraints proposed by Cha et al. and choose to build the algorithm following concept of learning of Thornton and Sattar. In addition, different from previous approachs for nurse rostering problem, the author chooses the approach that weight iterative repair algorithm can produce both feasible solutions and optimized solutions. On the other hand, the author also demonstrates that local search algorithm is independent of initial solutions.

Trang ii LÔØI CAÛM ÔN Lôøi ñaàu tieân toâi xin baøy toû loøng bieát ôn chaân thaønh ñeán Thaày TS. Döông Tuaán Anh, ngöôøi ñaõ taän tình giuùp ñôõ toâi trong suoát thôøi gian hoïc taäp cuõng nhö trong thôøi gian laøm luaän aùn thaïc só. Xin baøy toû loøng bieát ôn ñoái vôùi caùc Thaày Coâ trong khoa Coâng Ngheä Thoâng Tin tröôøng Ñaïi hoïc Baùch Khoa TP.Hoà Chí Minh ñaõ taän tình giaûng daïy truyeàn ñaït kieán thöùc cuõng nhö nhöõng hoã trôï khaùc veà tinh thaàn vaø tö lieäu cho toâi trong suoát thôøi gian hoïc taäp vaø laøm vieäc. Xin chaân thaønh caùm ôn Thaày TS.

Nguyeãn Thaønh Long, ngöôøi ñaõ luoân ñoäng vieân, khuyeán khích vaø goùp yù cho toâi trong suoát quaù trình laøm luaän vaên. Xin chaân thaønh caùm ôn hai ngöôøi raát thaân cuûa toâi laø Nguyeãn Thò Tuyeát Hoàng vaø Phaïm Vaên Vuõ ñaõ luoân ôû beân caïnh, ñoäng vieân, khuyeán khích, giuùp toâi in taøi lieäu, ñoïc vaø chænh söûa caùc loãi chính taû trong luaän vaên. Xin chaân thaønh caùm ôn baïn Buøi Vaên Quang ñaõ ñoùng goùp moät soá yù kieán vaø taïo moïi ñieàu kieän thuaän lôïi cho toâi trong vieäc söû duïng chöông trình xeáp lòch tröïc y taù duøng giaûi thuaät Tìm kieám Tabu. Xin chaân thaønh caùm ôn chò Nguyeãn Thò Kieàu Thu, ñieàu döôõng tröôûng cuûa khoa Tim Maïch beänh vieän Nhi Ñoàng I vaø chò Phan Thò Phöông Anh, ñieàu döôõng tröôûng cuûa khoa Caáp Cöùu beänh vieän Chôï Raãy ñaõ giuùp toâi raát nhieàu trong vieäc tìm hieåu nghieäp vuï cuûa baøi toaùn xeáp lòch tröïc y taù.

Sau cuøng, xin baøy toû loøng bieát ôn saâu saéc ñoái vôùi gia ñình, baïn beø, ñoàng nghieäp vaø caùc baïn cuøng lôùp cao hoïc khoa Coâng Ngheä Thoâng Tin khoaù 12 ñaõ luoân ñoäng vieân vaø quan taâm giuùp ñôõ toâi trong suoát thôøi gian hoïc taäp vaø laøm luaän vaên. Thaønh phoá Hoà Chí Minh, 25/11/2004 Taùc giaû Trang iii Giôùi thieäu MUÏC LUÏC Toùm taét .ii Lôøi caûm ôn. iii Muïc luïc .iv Danh muïc caùc hình vaø giaûi thuaät .vii Danh muïc caùc baûng .vii CHÖÔNG 1 : GIÔÙI THIEÄU .1 Giôùi thieäu ñeà taøi .2 Baøi toaùn xeáp lòch tröïc y taù .1 Moâ taû baøi toaùn.2 Caùc raøng buoäc cuûa baøi toaùn .3 Ñaùnh giaù baøi toaùn .4 CHÖÔNG 2 : CAÙC NGHIEÂN CÖÙU LIEÂN QUAN.1 Caùc nghieân cöùu lieân quan ñeán baøi toaùn xeáp lòch tröïc y taù .1 Qui hoaïch toaùn hoïc (Mathematical Programming).2 Laäp trình raøng buoäc (Constraint Programming) .3 Nhaän xeùt caùc phöông phaùp xeáp lòch tröïc y taù.2 Caùc nghieân cöùu lieân quan ñeán kyõ thuaät tu chænh laëp .1 Tu chænh laëp coù troïng soá cho baøi toaùn thoaû maõn raøng buoäc.2 Kyõ thuaät Tu chænh laëp coù troïng soá cho baøi toaùn raøng buoäc quaù möùc.3 Höôùng nghieân cöùu cuûa luaän vaên.25 CHÖÔNG 3 : PHÖÔNG HÖÔÙNG GIAÛI QUYEÁT BAØI TOAÙN.1 Kyõ thuaät tu chænh laëp coù troïng soá (weighted iterative repair) .1 Moái quan heä giöõa löôïng thoâng tin, chi phí vaø soá laàn laëp .2 Duy trì söï phaân bieät giöõa raøng buoäc cöùng vaø raøng buoäc meàm .3 Xaùc ñònh troïng soá ban ñaàu cho raøng buoäc cöùng .2 ÖÙng duïng tu chænh laëp coù troïng soá vaøo baøi toaùn xeáp lòch tröïc y taù.1 Moâ hình hoaù baøi toaùn.2 Löïa choïn ñoä saâu cho giaûi thuaät .3 Löïa choïn tieâu chuaån ñaùnh giaù .4 Giaûi thuaät Tu chænh laëp coù troïng soá (Weighted Iterative Repair – WIR).5 Raøng buoäc ña bieán .6 Boå sung moät soá heuristic ñeå caûi thieän giaûi thuaät .42 CHÖÔNG 4 : THIEÁT KEÁ ÖÙNG DUÏNG XEÁP LÒCH TRÖÏC Y TAÙ .1 Hieän thöïc giaûi thuaät .44 Trang iv Giôùi thieäu 4.1 Xaây döïng thö vieän phaàn meàm cho giaûi thuaät Tu chænh laëp coù troïng soá .2 ÖÙng duïng thö vieän vaøo giaûi quyeát baøi toaùn xeáp lòch tröïc y taù .2 Thieát keá öùng duïng xeáp lòch tröïc y taù .1 Moâ hình öùng duïng xeáp lòch tröïc y taù .2 Thieát keá cô sôû döõ lieäu .3 Caùc chöùc naêng cuûa heä thoáng xeáp lòch tröïc y taù .54 CHÖÔNG 5 : CHAÏY THÖÛ NGHIEÄM CHÖÔNG TRÌNH .1 Phöông aùn chaïy thöû nghieäm .2 Phöông aùn thöû nghieäm .3 Thieát keá taäp baøi toaùn thöû nghieäm .4 Keát quaû thöïc nghieäm .1 Thoáng keâ keát quaû .2 Nhaän xeùt keát quaû .3 Phaân tích keát quaû .69 CHÖÔNG 6 : KEÁT LUAÄN .1 Ñoùng goùp cuûa ñeà taøi .2 Höôùng môû roäng cuûa ñeà taøi .71 THÖ MUÏC THAM KHAÛO .72 PHUÏ LUÏC A: BAØI TOAÙN GIAÛI HEÄ RAØNG BUOÄC VAØ BAØI TOAÙN GIAÛI HEÄ RAØNG BUOÄC RIEÂNG PHAÀN .1 PHUÏ LUÏC B: TÌM KIEÁM HEÄ THOÁNG VAØ TÌM KIEÁM PHI HEÄ THOÁNG.1 PHUÏ LUÏC C: TOÁI THIEÅU CUÏC BOÄ.1 PHUÏ LUÏC D: SÖÛ DUÏNG CHÖÔNG TRÌNH XEÁP LÒCH TRÖÏC Y TAÙ .1 BAÛNG THUAÄT NGÖÕ VIEÄT-ANH ÑOÁI CHIEÁU.1 Trang v Giôùi thieäu DANH MUÏC CAÙC HÌNH VAØ GIAÛI THUAÄT Hình 2-1: Ví duï moät baûng phaân coâng tröïc cho 25 y taù.8 Hình 2-2: Ví duï moät baøi toaùn thoaû maõn raøng buoäc coù 5 bieán A, B, C, D, E.20 Hình 2-3: Baøi toaùn thoaû maõn raøng buoäc ñöôïc moâ hình hoaù theo GENET .20 Hình 2-4: Baûng troïng soá wxy giöõa hai noát coù söï xung ñoät .21 Hình 2-5: Ví duï moät traïng thaùi coù theå cuûa maïng GENET trong hình 2.22 Hình 2-6: Giaûi thuaät Breakout .23 Hình 2-7: Giaûi thuaät Soft Constraint Heuristic.25 Hình 3-1: Ví duï baøi toaùn toâ maøu ñoà thò coù soá raøng buoäc quaù möùc.28 Hình 3-2: Moái quan heä giöõa löôïng thoâng tin, chi phí vaø soá laàn laëp .29 Hình 3-3: Duy trì söï phaân bieät troïng soá giöõa raøng buoäc cöùng vaø raøng buoäc meàm .32 Hình 3-4: Giaûi thuaät taêng troïng soá raøng buoäc vi phaïm .34 Hình 3-5: Giaûi thuaät tính ñoä sai bieät giaù trò muïc tieâu so vôùi lôøi giaûi hieän taïi khi choïn giaù trò m cho bieán v .38 Hình 3-6: Giaûi thuaät Tu chænh laëp coù troïng soá (WIR) .39 Hình 3-7: Heuristic saép thöù töï bieán thuaän .42 Hình 3-8: Heuristic saép thöù töï bieán nghòch .