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

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

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:

Trong đó:

 : đượ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;

 : 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 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:

Để 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

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

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

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

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 ANH¹, KHƯU MINH CẢNH²

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

    ²Trung 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