Ứng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền

23/03/2024

TN&MTPhân nhóm tài nguyên phục vụ để đáp ứng các nguồn lực được bố trí tối đa không bị lãng phí là vấn đề thử thách ngày càng lớn hiện nay. Bài báo viết về một kỹ thuật AI trong phân nhóm, đó là kỹ thuật CFP (cell formation problem). Kỹ thuật CFP được áp dụng nhiều trong các ứng dụng thực tế. Cụ thể hơn là trên các lĩnh vực cần tối ưu và hợp lý hóa để đảm bảo các phân hoạch khi thực hiện việc phân bổ như sử dụng nhân lực, thiết bị và tài nguyên trong y tế, môi trường; khi chăm sóc khách hàng, xử lý các tình huống khẩn cấp,... Theo đó, nghiên cứu đề cập đến phương pháp giải bài toán CFP với giải thuật di truyền trên tập dữ liệu mẫu khi quản lý tài nguyên.

Từ khóa: CFP, thuật giải di truyền, nhóm, dịch vụ

Giới thiệu

Trong thực tế điều hành và quản lý về tài nguyên nhân lực/môi trường/công việc gom thành các nhóm để xử lý tương tác là một phương pháp cần thiết giúp tối ưu và giải phóng nhiều tài nguyên như: nhân lực, máy móc,… Về ứng dụng, theo các xu hướng phát triển, TP. Hồ Chí Minh và nhiều thành phố tại Việt Nam sẽ gia tăng các hệ sinh thái dịch vụ. Đó là những chuỗi 4 hoạt động về cung cấp, điều tiết, hỗ trợ và điều chỉnh văn hóa đối với các hoạt động/qui trình xử lý. Mỗi hoạt động đều cần có sự định lượng và tiếp đó là phân nhóm để tăng cường chất lượng cũng như giảm các loại chi phí. Các vấn đề về phân nhóm sẽ được quan tâm để mức ảnh hưởng và hiệu quả của các dịch vụ là tối ưu, hạn chế lãng phí nguồn tài nguyên. Một ví dụ điển hình là phân tầng điều trị Covid19 tại TP. Hồ Chí Minh vào năm 2021: Thời điểm ban đầu, số tầng điều trị là 3 nhóm đã làm dư thừa một lượng lớn nhân viên y tế chữa trị bệnh nhân thông thường nhưng lại gây thiếu trầm trọng các nhân viên y tế ở các bệnh nhân trong nhóm bệnh nặng. Sau đó, khi số tầng điều trị được điều chỉnh thành 5 nhóm thì nguồn tài nguyên nhân lực được vận dụng tối ưu và hợp lý hơn, nguồn lực y tế được sử dụng triệt để hơn, việc điều trị cũng được triển khai tốt hơn do các nhóm bệnh nhận được phân chia cụ thể hơn và nhân lực y tế được khai thác tối đa.

Bài báo này trình bày ứng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền và kết quả thử nghiệm dựa trên dữ liệu mẫu về định hướng sử dụng vỉa hè.

Tổng quan

Về lịch sử CFP, nhà nghiên cứu Flanders (1925) đưa ra “Lớp bài toán Sản xuất tế bào - Cellular Manufacturing (CM) là ứng dụng về khái niệm kỹ thuật nhóm trong lĩnh vực công nghệ”. Sau đó, Mitrodanov (1933) đề cập tới bài toán phân nhóm sản xuất và vào thập kỷ 1970 Burbidge đưa ra công nghệ nhóm (Group Technology) để giải bài toán này. Bài toán Hình thành tế bào - Cell Formation Problem (CFP) là một trong những bài toán thuộc CM. Kỹ thuật CFP là một nền tảng của kỹ thuật phân nhóm. Theo [1], đầu vào của CFP là một ma trận kích thước với là tập số máy và là tập các bộ phận được xử lý. Các giá trị nghĩa là máy thứ không thể xử lý bộ phận thứ . Và khi có nghĩa là máy thứ có thể xử lý được việc. 

Từ đó, với yêu cầu phân thành hữu hạn các nhóm máy và các bộ phận xử lý tương ứng với ràng buộc là mỗi máy, cũng như mỗi bộ phận, chỉ thuộc 1 nhóm. Bài toán này cũng được nhiều tác giả nghiên cứu với nhiều cách tiếp cận khác nhau. Ví dụ, cũng theo bài báo [1], Boctor (1991) tiếp cận theo hướng lập trình toán học; Guerrero và cộng sự (2002) tiếp cận theo hướng mạng nơron; Rajagopalan và Batra (1975) và sau này là Alain Hertz cùng với cộng sự (1992), cũng như nhóm J Saral trong bài báo [1] tiếp cận theo hướng đồ thị, cụ thể là xem xét giải CFP như đồ thị hai phía (bi-partite graphs). Kỹ thuật CFP ngày nay vẫn được nhiều nhà nghiên cứu, khoa học quan tâm, như Tunnukij & Hicks (2009); Elbenani & Ferland (2012); J. Saral (2019); Mikhail V. Batsyna (2021). Bên cạnh đó, phương pháp tiếp cận bằng giải thuật di truyền cũng đã được đưa ra [2]. Về bản chất, CFP là bài toán có độ phức tạp NP với ý nghĩa tìm các hoán vị của dòng và của cột để tổ chức nhóm được tối ưu hơn.

Cụ thể hơn, CFP là bài toán nhóm các máy móc (Machines) và các bộ phận (Parts) trong các ô được sản xuất để tránh hoặc cực tiểu các phần tử ngoại lệ, trong CFP mỗi nhóm máy-bộ phận được gọi là một tế bào (Cell). Về mặt lý luận, đây là bài toán khó và chưa có phương pháp giải tuyệt đối. Về mặt thực tiễn, CFP có thể được áp dụng trong các hệ thống tự động quản lý sản xuất, chẳng hạn như trong thiết kế kiến trúc các chip máy tính hay trong tự động hóa cho các hệ thống tính toán song song. Với các bài toán như thế, CFP được cho là hoàn toàn thích hợp để hoàn thành việc phân rã các bộ xử lý và các đơn vị dữ liệu vào một số tế bào xác định trước.

Theo đó, Hình 1(a) bên dưới là khả năng xử lý của máy (Machines) cho công việc (Parts) và hình 1(b) là kết quả phân nhóm các công việc được thực hiện theo máy.

Hình 1: (a) Bảng dữ liệu; (b) Một kết quả phân nhóm thành 2 nhóm
Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền

Về hướng nghiên cứu giải bằng các thuật toán di truyền (genetics algorithms), kỹ thuật CFP được nhiều nhà khoa học quan tâm như bảng mô tả các nghiên cứu như sau:

Bảng 1: Các phương pháp di truyền cho kỹ thuật CFP

Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền

Trong nghiên cứu của Araj Mahdavi và cộng sự (2009) đưa ra, hiệu quả trong việc nhóm khối được định lượng bằng công thức mà các bài nghiên cứu trước đó đã sử dụng:

Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền

Trong đó:

 Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền: được xác định là tổng các giá trị trong ma trận kề, nghĩa là tổng các giá trị 1;

 Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền: tương ứng với số lượng các phần tử không được bố trí, nghĩa là số tế bào nằm ngoài;

 Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền: ứng với số lượng các phần tử bằng 0 trong các khối, nghĩa là số các số 0 được bố trí nằm trong khối.

Phương pháp nghiên cứu

Trong các tài liệu về thuật toán di truyền, khái niệm Thuật toán di truyền (Genetic Algorithm - GA) được hiểu là “một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp, vận dụng các nguyên lý như di truyền, đột biến, chọn lọc tự nhiên và trao đổi chéo.” Ngày nay, thuật toán di truyền được sử dụng phổ biến trong một số ngành như: tin sinh học, khoa học máy tính, trí tuệ nhân tạo, tài chính và một số ngành khác. 

Về lựa chọn biểu diễn nghiệm: Ma trận kết quả được hình thành từ giá trị chuỗi nhiễm sắc thể. Nhiễm sẵc thể có độ dài M + P và có M + P giá trị (từ 1 đến K, với K là số lượng các nhóm). Trong đó, P giá trị đầu tiên biểu thị các bộ phận và M giá trị (từ P+1 đến P+M) biểu thị nhóm máy xử lý. Vì vậy, nếu giá trị của bộ phận có cùng giá trị của máy xử lý thì có nghĩa là chúng thuộc về một nhóm xử lý. 

Ví dụ: Giả sử M = 3, N = 2, K = 2, khi kết quả chuỗi nhiễm sắc thể là “12221” thì nghĩa là bộ phận thứ 1 được máy 3 xử lý, bộ phận thứ 2 sẽ được máy 1 và 2 xử lý. Từ đó, ma trận tương ứng với chuỗi nhiễm sắc thể trên sẽ như sau:

Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền

Để thực hiện giải thuật, lược đồ (1a) gồm các công tác xử lý được thể hiện như sau: Bước 1: Khởi tạo quần thể; Bước 2: Đánh giá mỗi cá thể trong quần thể; Bước 3: Kiểm tra tiêu chí dừng và chọn nghiệm, hoặc sang bước 4;Bước 4: Tạo quần thể mới bằng các phép toán di truyền (lai chéo, đột biến) và quay lại Bước 2

Lược đồ 1a, 1b: Các bước thực thi của thuật toán di truyền cho kỹ thuật CFP

Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền

Cụ thể hơn, về cài đặt, các chi tiết được mô tả như lược đồ 1b như sau: Bước 1: Đọc dữ liệu, các tham số và mã hóa (Problem Encoding); Bước 2: Tạo quần thể ban đầu (Create Initial Population); Bước 3: Tính toán giá trị (Best Finess Evaluation); Bước 4: Kiểm tra giá trị, chuyển sang bước 5, 6; Bước 5: Nếu giá trị đạt thì dừng thuật toán, thực hiện việc giải mã quần thể xây dựng được. Ngược lại thì sang bước 6; Bước 6: Bắt đầu thực hiện việc lai tạo (Crossover) và/hoặc đột biến (Mutation) cho thế hệ sau; Bước 7: Tính toán và thay thế nghiệm mới nếu nghiệm mới tốt hơn và tiếp tục thực hiện lặp lại Bước 4.

Điều kiện để dừng thuật toán là khi giá trị phù hợp (best finess value) hội tụ (tức là không đổi) trên một số vòng lặp. Tuy nhiên, chương trình sẽ giới hạn số lần lặp khi tìm nghiệm tối ưu (trong nghiên cứu giới hạn số lần lặp là 100).Việc điều khiển (giới hạn) số lần ổn định của nghiệm sẽ tùy thuộc vào kết quả nghiệm thực tế, nghĩa là ta sẽ sử dụng nghiệm để đánh giá việc nên dừng.

Về tính hội tụ, hình bên dưới thể hiện nghiệm sẽ hội tụ trong những bước lặp về sau. Điều này có nghĩa là ở những bước lặp ban đầu, nghiệm sẽ thay đổi nhiều và việc chọn nghiệm theo giải thuật di truyền càng về sau sẽ càng chậm lại do tính sàn lọc cao.

Hình 2: Hình thể hiện độ hội tụ của nghiệm

Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền

Nội dung nghiên cứu

Ứng dụng phân nhóm sử dụng kỹ thuật CFP có thể được ứng dụng trên nhiều lĩnh vực khi có nhu cầu tổ chức hoặc tái tổ chức nhằm mô hình các kịch bản thay đổi. Một ví dụ minh họa: Bài toán quản lý vỉa hè với yêu cầu phân nhóm có thể: Đề xuất các hướng kinh doanh cho người dân; đề xuất các hướng quản lý và các yêu cầu tối thiếu đối với các loại hình kinh doanh sử dụng vỉa hè; đề xuất các hướng quy hoạch trong tương lai.

Dưới đây là bảng minh họa mô tả một số đặc tính công năng được đề xuất cho vỉa hè:

Bảng 1: Bảng dữ liệu minh họa các tính năng của vỉa hè có thể triển khai

Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền

Kết quả thực thi của thuật toán cho thấy việc phân nhóm khá rõ ràng:

Với số nhóm k =2, sau 26 lần lặp, giá trị tối ưu tìm được µ = 0.45238 và nghiệm thể hiện the chuỗi DNA

Hình 3: Minh họa về ma trận đầu vào và ma trận nghiệm

Úng dụng kỹ thuật CFP trong phân nhóm tài nguyên phục vụ với cách tiếp cận bằng giải thuật di truyền

là [[2. 2. 1. 1. 1. 1. 2. 1. 2. 1. 2. 2. 2. 1. 1. 1. 2. 2.]].

Với số nhóm k =3, sau 16 lần lặp, giá trị tối ưu tìm được µ = 0.47058 và nghiệm là [[1. 3. 2. 2. 2. 2. 1. 2. 3. 1. 1. 1. 3. 2. 2. 2. 3. 1.]].

Kết luận

Kết quả nghiên cứu cho thấy phương pháp CFP phù hợp với việc tìm kiếm bố trí nguồn lực, tài nguyên và định hướng phân loại các nhóm trong các dịch vụ. Phương pháp giải quyết bằng thuật giải di truyền cho thấy hệ thống đáp ứng được việc tìm kiếm nghiệm gần đúng.

Tài liệu tham khảo

1. J. SARAL, S. ARUMUGAM, Ibrahim VENKAT và A. SOMASUNDARAM, Cellular manufacturing problem - A graph theoretic approach, 2019; 

2. Iraj Mahdavi và cộng sự, Genetic algorithm approach for solving a cell formation problem in cellular manufacturing, 2009;

3. Mikhail V. Batsyna, Ekaterina K. Batsynab, Ilya S. Bychkova, On NP-completeness of the cell formation problem, International Journal of Production Research, 2021;

4. J. Saral, S. Arumugam#, Ibrahim Venkat và A. Somasundaram, Cellular manufacturing problem - A graph theoretic approach, 2019.

APPLICATION OF APPLY CFP’TECHNIQUE FOR SOLVING GROUPING ISSUES IN RESOURCES WITH GENETIC ALGORITHM APPROACH

Abstract: Grouping resources to meet the maximum allocation of resources without being wasted is an increasingly challenging issue today. The article is about an AI technique in clustering, which is the CFP (cell formation problem) technique. CFP technique is widely applied in practical applications. More specifically, on the areas that need to be optimized and rationalized to ensure planning when making allocations such as using human resources, equipment and resources in health care and the environment; when taking care of customers, handling emergency situations... Accordingly, the study addresses the method of solving the CFP problem with genetic algorithms on sample data sets of resources.

Keyword: CFP, genetics algorithm, grouping, service.

HOÀNG THỊ KIỀU ANH1, KHƯU MINH CẢNH2

    1Trường Đại học Tài nguyên và Môi trường TP. Hồ Chí Minh

    2Trung tâm HCMGIS, Sở Khoa học và Công nghệ TP.Hồ Chí Minh

Nguồn: Tạp chí Tài nguyên và Môi trường số 23 (Kỳ 1 tháng 12) năm 2023
 

Where you can buy Louis Vuitton Replica :

hermes pas cher louis vuitton neverfull replica louis vuitton scarf replica gucci backpack replica louis vuitton outlet nederland dior tasche replica replica chanel wallet louis vuitton duffle bag replica Replica chanel replica chanel wallet louis vuitton messenger bag replica dior tasche replica fake Louis Vuitton shoes replica gucci shoes van cleef replica chanel imitazioni replica celine Louis Vuitton Taschen replica hermes pas cher louis vuitton messenger bag replica LOUIS VUITTON sunglasses replica replica cartier love bracelet replica louis vuitton m40780 louis vuitton imitate kaufen fake louis vuitton tas kopen fake louis vuitton wallet louis vuitton scarf replica chanel imitazioni perfette replica louboutin replica celine replica Louis Vuitton shoes goyard replica cartier love imitazione fake Louis Vuitton shoes gucci scarf replica borse louis vuitton replica replica Louis Vuitton supreme Backpack Louis Vuitton replica replique Sac Louis Vuitton chanel replica louis vuitton keepall replica zaino louis vuitton falso replica Jordan 1 cartier love ring replica dior replica chanel replica fake louis vuitton shoes louis vuitton shoes replica replica louis vuitton wallet imitazioni louis vuitton

Tin tức

Tập đoàn Nhật Bản khởi công dự án nửa tỷ USD từ thông điệp của Thủ tướng

Thủ tướng Phạm Minh Chính: 'Ai có gì góp nấy' để xóa nhà tạm, nhà dột nát cho người nghèo

Thủ tướng Phạm Minh Chính: Cả nước chung tay để xóa nhà tạm, nhà dột nát trên cả nước trong năm 2025

Ủy ban Chỉ đạo quốc gia về thực hiện Chiến lược phát triển bền vững kinh tế biển Việt Nam tổ chức kỳ họp lần thứ I

Tài nguyên

Nguyên nhân khiến hầm Bãi Gió sạt lở, đường sắt Bắc-Nam tê liệt

Phát hiện thêm 22 hang động lung linh huyền ảo tại Quảng Bình

Khẩn trương khắc phục sự cố sạt lở hầm đường sắt khu vực qua đèo Cả

Những ý kiến được quan tâm tại Hội nghị hướng dẫn thi hành Luật Đất đai năm 2024

Môi trường

Net Zero - cơ hội và thách thức

'Xanh hóa' du lịch, khách muốn có chuyến đi giảm ‘dấu ấn’ môi trường

Khởi động chiến dịch “Nói không với rác nhựa, lưu lại dấu tay xanh" tại Côn Đảo

Ô nhiễm không khí vượt ngưỡng, Hà Nội sẽ phun nước rửa đường trở lại

Video

Kỷ niệm 20 năm Tạp chí Tài nguyên và Môi trường và ra mắt kỷ ra mắt chuyên trang tiếng Anh

Tình yêu Môi trường

Thế giới lo sợ vì biến đổi khí hậu đã “Ngoài tầm kiểm soát” và kêu gọi hành động toàn cầu

Dự án Luật địa chất và khoáng sản sửa đổi khắc phục hạn chế để phát huy nguồn lực khoáng sản

Khoa học

Về khả năng tồn tại các nguồn nước dưới đất ở vùng thềm lục địa nước ta 

Giải pháp xanh bảo vệ, chống sạt lở mái taluy khu đô thị khu vực Đà Lạt

Một số vấn đề xây dựng đội ngũ cán bộ khoa học lĩnh vực tài nguyên nước 

Đề xuất các giải pháp bảo vệ môi trường các hồ cấp nước sinh hoạt trên địa bàn tỉnh Bà Rịa - Vũng Tàu 

Chính sách

Bổ nhiệm Tân Thứ trưởng Bộ Ngoại giao

Phát triển mạng lưới trạm khí tượng thủy văn hiện đại, đồng bộ

Vì sao Công ty TNHH Nông nghiệp Đông Giang bị phạt 80 triệu đồng?

Hà Nội: Đăng ký biến động, mua bán chuyển nhượng bất động sản không gia tăng đột biến

Phát triển

Khó chi trả kinh phí từ bán tín chỉ carbon rừng

Bổ nhiệm Tổng Biên tập Tạp chí Thông tin và Truyền thông

Liên đoàn Quy hoạch và Điều tra tài nguyên nước miền Bắc: 50 năm xây dựng và phát triển 

Bình Dương: Sắp diễn ra Diễn đàn hợp tác kinh tế Horasis Trung Quốc 2024

Diễn dàn

Thời tiết ngày 14/4: Nhiều khu vực có nắng nóng diện rộng và gay gắt

Thời tiết ngày 13/4: Nhiều khu vực trên cả nước nắng nóng, có nơi nắng nóng gay gắt

Thời tiết ngày 12/4: Miền Bắc nắng nóng trở lại, Nam Bộ có nơi gần 40 độ

Duy trì ổn định hoạt động mạng lưới trạm, cảnh báo, dự báo kịp thời các hiện tượng thời tiết nguy hiểm