Ứng dụng giải thuật di truyền giải bài toán điều độ sản xuất Flowshop

Luận văn trình bày giải pháp ứng dụng giải thuật di truyền giải bài toán điều độ sản xuất flowshop, giúp tối ưu nguồn lực và giảm thời gian hoàn thành.

• Tác giả: Nguyễn Xuân Huy
• Người hướng dẫn: Pgs. Đỗ Ngọc Hiền
• Trường học: Trường Đại học Bách khoa, Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Kỹ thuật Công nghiệp
• Đề tài: Nghiên cứu ứng dụng giải thuật di truyền giải quyết bài toán điều độ sản xuất tại nhà máy sản xuất thiết bị cơ khí
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2024
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH ẢNH
• DANH MỤC BẢNG BIỂU
• DANH MỤC TỪ VIẾT TẮT
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. LÝ DO HÌNH THÀNH ĐỀ TÀI
• 1.2. MỤC TIÊU NGHIÊN CỨU
• 1.3. MỤC TIÊU LUẬN VĂN
• 1.4. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU
• 1.5. Ý NGHĨA NGHIÊN CỨU
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN
• 2.1. Điều độ trong sản xuất và dịch vụ
• 2.2. Giải thuật di truyền
• 2.3. Các nghiên cứu liên quan
• 2.4. PHƯƠNG PHÁP LUẬN
• 3. CHƯƠNG 3: PHÂN TÍCH ĐỐI TƯỢNG NGHIÊN CỨU
• 3.1. TỔNG QUAN ĐỐI TƯỢNG NGHIÊN CỨU
• 3.1.1. Giới thiệu về công ty
• 3.1.2. Sơ đồ tổ chức công ty
• 3.1.3. Quy trình sản xuất chung
• 3.2. PHÂN TÍCH HIỆN TRẠNG
• 3.2.1. Đặc thù sản xuất của công ty
• 3.2.2. Phương pháp điều độ hiện tại
• 3.2.3. Tiếp cận vấn đề
• 4. CHƯƠNG 4: MÔ HÌNH BÀI TOÁN
• 4.1. CÁC CHỈ SỐ, THAM SỐ
• 4.2. HÀM MỤC TIÊU, BIẾN QUYẾT ĐỊNH, RÀNG BUỘC
• 4.3. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN
• 4.3.1. Mã hóa nhiễm sắc thể
• 4.3.2. Khởi tạo quần thể
• 4.3.3. Chọn lọc cha mẹ
• 4.3.4. Điều kiện dừng
• 5. CHƯƠNG 5: ÁP DỤNG MÔ HÌNH VÀO BÀI TOÁN THỰC TẾ
• 5.1. DỮ LIỆU ĐẦU VÀO
• 5.2. CHƯƠNG TRÌNH ĐIỀU ĐỘ BẰNG NGÔN NGỮ PYTHON
• 5.3. KẾT QUẢ ĐIỀU ĐỘ
• 6. CHƯƠNG 6: KẾT LUẬN VÀ KIẾN NGHỊ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giải Thuật Di Truyền trong Điều Độ Sản Xuất

Giải thuật di truyền là một phương pháp tối ưu hóa mô phỏng quá trình tiến hóa tự nhiên, được ứng dụng rộng rãi trong các bài toán tối ưu phức tạp. Trong lĩnh vực điều độ sản xuất nhà máy, giải thuật di truyền giúp tìm kiếm lời giải tối ưu để cực tiểu hóa tổng thời gian hoàn thành các đơn hàng. Phương pháp này vượt trội so với các giải pháp truyền thống do khả năng xử lý các bài toán quy mô lớn với số lượng ràng buộc phức tạp. Ứng dụng giải thuật di truyền trong sản xuất cho phép doanh nghiệp tối ưu hóa nguồn lực hiện có, đáp ứng nhanh chóng yêu cầu khách hàng và nâng cao hiệu quả hoạt động. Nghiên cứu từ Trường Đại học Bách Khoa TP.HCM đã chứng minh tính khả thi và hiệu quả của phương pháp này trong môi trường sản xuất thực tế.

1.1. Nguyên Lý Hoạt Động của Giải Thuật Di Truyền

Giải thuật di truyền hoạt động dựa trên ba toán tử chính: chọn lọc, lai ghép và đột biến. Quá trình bắt đầu với một quần thể ban đầu gồm các cá thể đại diện cho các giải pháp tiềm năng. Mỗi thế hệ mới được tạo ra bằng cách chọn lọc các cá thể tốt nhất, lai ghép chúng để tạo ra con em, và áp dụng đột biến để duy trì tính đa dạng. Phương pháp này lặp lại cho đến khi đạt được điều kiện dừng, thường là số thế hệ tối đa hoặc sự hội tụ của giải pháp.

1.2. Ứng Dụng trong Bài Toán Điều Độ Flowshop

Mô hình flowshop linh hoạt là một trong những bài toán điều độ sản xuất phức tạp nhất. Giải thuật di truyền được sử dụng để tìm thứ tự gia công tối ưu cho các công việc trên các máy, nhằm giảm thiểu thời gian hoàn thành. Ứng dụng ngôn ngữ lập trình Python, các nhà nghiên cứu đã phát triển một giải pháp hiệu quả có khả năng xử lý dữ liệu thực tế từ nhà máy sản xuất thiết bị cơ khí.

II. Xây Dựng Mô Hình Bài Toán Điều Độ Sản Xuất

Việc xây dựng mô hình bài toán điều độ sản xuất là bước quan trọng nhất trong quá trình áp dụng giải thuật di truyền. Mô hình cần phản ánh chính xác các đặc thù của quy trình sản xuất thực tế tại nhà máy, bao gồm số lượng công việc, số lượng máy, thời gian gia công, các ràng buộc về công nghệ và tài nguyên. Mô hình flowshop linh hoạt được xây dựng dựa trên các tham số thực tế từ các doanh nghiệp sản xuất thiết bị xây dựng và cơ khí. Các ràng buộc được xác định bao gồm: không được xếp chồng công việc trên cùng một máy, công việc phải được thực hiện đúng thứ tự công nghệ, và các máy không thể xử lý nhiều công việc cùng lúc. Hàm mục tiêu là cực tiểu hóa tổng thời gian hoàn thành tất cả các đơn hàng, giúp tăng năng suất và giảm chi phí sản xuất.

2.1. Các Tham Số và Ràng Buộc Của Mô Hình

Mô hình điều độ flowshop bao gồm các tham số: số lượng công việc (n), số lượng máy (m), thời gian gia công trên từng máy (p_ij), và thứ tự công nghệ bắt buộc. Các ràng buộc chính gồm: mỗi công việc phải thực hiện tuần tự trên các máy, không được xếp chồng trên cùng máy, và thời gian bắt đầu công việc trên máy k phải lớn hơn hoặc bằng thời gian kết thúc trên máy k-1.

2.2. Hàm Mục Tiêu và Tiêu Chí Tối Ưu

Hàm mục tiêu chính của bài toán điều độ sản xuất là cực tiểu hóa makespan (C_max) – tổng thời gian hoàn thành tất cả công việc. Tiêu chí này được chọn vì nó trực tiếp ảnh hưởng đến năng suất nhà máy. Các tiêu chí phụ có thể bao gồm giảm thời gian chờ đợi, giảm chi phí năng lượng, và tối ưu hóa sử dụng máy móc.

III. Phát Triển Giải Thuật Di Truyền cho Điều Độ Sản Xuất

Phát triển giải thuật di truyền cho bài toán điều độ sản xuất đòi hỏi thiết kế cẩn thận các thành phần cốt lõi. Biểu diễn cá thể sử dụng hoán vị các công việc, đảm bảo tính khả thi của lời giải. Hàm fitness được xây dựng dựa trên makespan, với các cá thể có makespan nhỏ nhất sẽ có khả năng sinh sản cao hơn. Toán tử chọn lọc sử dụng phương pháp vòng quay (tournament selection) để cân bằng giữa khai thác lời giải tốt và khám phá không gian tìm kiếm. Lai ghép áp dụng kỹ thuật order crossover (OX) để tạo ra lời giải mới từ hai cha mẹ, bảo toàn cấu trúc hoán vị. Đột biến sử dụng phương pháp hoán vị ngẫu nhiên hai vị trí để duy trì tính đa dạng quần thể. Việc tinh chỉnh các tham số như kích thước quần thể, xác suất lai ghép, xác suất đột biến, và số thế hệ tối đa là rất quan trọng để đạt hiệu quả tối ưu.

3.1. Biểu Diễn Cá Thể và Hàm Fitness

Biểu diễn cá thể trong giải thuật di truyền sử dụng dãy hoán vị biểu diễn thứ tự công việc. Hàm fitness tính toán makespan bằng cách mô phỏng quy trình sản xuất theo thứ tự công việc được biểu diễn. Cá thể có makespan nhỏ nhất nhận giá trị fitness cao nhất, được ưu tiên chọn lọc trong các thế hệ tiếp theo.

3.2. Các Toán Tử Di Truyền Lai Ghép và Đột Biến

Toán tử lai ghép sử dụng kỹ thuật Order Crossover (OX) từ hai cá thể cha mẹ để tạo con em. Toán tử đột biến áp dụng hoán vị ngẫu nhiên hai vị trí để duy trì đa dạng. Cân bằng giữa hai toán tử này quyết định khả năng hội tụ và tránh cực tiểu địa phương của giải thuật.

IV. Ứng Dụng Thực Tế và Kết Quả Đạt Được

Ứng dụng giải thuật di truyền trong điều độ sản xuất tại các nhà máy sản xuất thiết bị cơ khí và xây dựng đã mang lại kết quả rất khả quan. Nghiên cứu từ Trường Đại học Bách Khoa TP.HCM đã triển khai giải thuật này tại một nhà máy thực tế và so sánh với phương pháp điều độ truyền thống. Kết quả cho thấy giải thuật di truyền giảm được makespan khoảng 15-25% so với phương pháp thủ công, đồng thời giảm thời gian tính toán so với các phương pháp tối ưu toàn cục. Việc triển khai mô hình flowshop linh hoạt kết hợp với giải thuật di truyền lập trình bằng Python cho phép doanh nghiệp nhanh chóng điều chỉnh kế hoạch sản xuất theo yêu cầu đơn hàng. Các lợi ích đạt được bao gồm: tăng hiệu suất máy móc, giảm thời gian chờ đợi, cải thiện khả năng đáp ứng khách hàng, và tối ưu hóa sử dụng nguồn lực sẵn có.

4.1. Kết Quả Thực Nghiệm và So Sánh

Kết quả thực nghiệm cho thấy giải thuật di truyền vượt trội so với các phương pháp truyền thống. Với 50 công việc và 5 máy, giải thuật đạt makespan 850 giờ so với 1020 giờ của phương pháp thủ công. Thời gian tính toán chỉ mất 2-3 phút, cho phép điều độ nhanh chóng theo nhu cầu thực tế.

4.2. Lợi Ích và Hướng Phát Triển Tương Lai

Những lợi ích chính bao gồm: cải thiện năng suất 15-25%, giảm chi phí sản xuất, tăng độ linh hoạt điều độ, và nâng cao sự hài lòng khách hàng. Hướng phát triển tương lai bao gồm tích hợp thêm ràng buộc về tài nguyên nhân sự, bảo dưỡng máy móc, và kết hợp với các giải thuật hybrid khác.

Nội dung chính

Tổng quan nghiên cứu

Thực trạng khảo sát tại nhà máy sản xuất thiết bị xây dựng và hầm mỏ vào tháng 8 năm 2022 ghi nhận tỷ lệ giao hàng trễ hạn lên đến 63,16%, tương ứng với 12 trên tổng số 19 sản phẩm chế tạo theo đơn hàng bị trễ với tổng thời gian chậm tiến độ lên tới 35 ngày. Là một doanh nghiệp hoạt động theo mô hình sản xuất thiết bị gốc (Original Equipment Manufacturer - OEM) và sản xuất theo đơn đặt hàng (Make To Order - MTO), công ty phải đối mặt với đặc thù sản phẩm có giá trị cao, đơn chiếc, tính lặp lại thấp và quy trình công nghệ thay đổi linh hoạt theo từng hợp đồng.

Vấn đề nghiên cứu cốt lõi xuất phát từ việc công tác lập kế hoạch và phân bổ máy móc hiện nay hoàn toàn phụ thuộc vào kinh nghiệm chủ quan của người điều độ và xử lý thủ công qua bảng tính Excel. Sự thiếu vắng một công cụ định lượng khoa học dẫn đến việc ước tính thời gian gia công thiếu chính xác, tạo ra tình trạng tắc nghẽn bán thành phẩm (WIP) tại các trạm gia công trước khâu lắp ráp, làm phát sinh chi phí tăng ca nhân công và kéo dài chu kỳ sản xuất.

Mục tiêu cụ thể của luận văn là xây dựng mô hình toán học cho bài toán điều độ flowshop linh hoạt (Flexible Flowshop Scheduling Problem - FFSP) và phát triển chương trình ứng dụng giải thuật di truyền (Genetic Algorithm - GA) trên ngôn ngữ Python, nhằm tìm kiếm phương án sắp xếp thứ tự gia công tối ưu với hàm mục tiêu cực tiểu hóa tổng thời gian hoàn thành toàn bộ các công việc ($C_{max}$ - Makespan). Nghiên cứu được thực hiện trên hệ thống gồm 8 công đoạn gia công cơ khí trong khung thời gian từ tháng 1 năm 2023 đến tháng 5 năm 2024. Kết quả mang lại ý nghĩa thiết thực khi giúp doanh nghiệp cắt giảm hơn 20% tổng thời gian gia công, loại bỏ 100% thời gian trễ hạn và nâng cao năng lực cạnh tranh trong chuỗi cung ứng cơ khí chế tạo.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng lý thuyết điều độ sản xuất trong môi trường Flowshop linh hoạt (FFSP) và lý thuyết tính toán tiến hóa dựa trên Giải thuật Di truyền (GA) được phát triển bởi John Holland. Môi trường FFSP là sự tổng quát hóa của mô hình dòng chuyền cổ điển kết hợp các máy gia công song song tại từng công đoạn, trong đó tập hợp $n$ công việc phải trải qua $l$ giai đoạn sản xuất theo cùng một tiến trình công nghệ xác định.

Hệ thống khái niệm và công cụ giải thuật trọng tâm bao gồm:

• Thời gian hoàn tất lớn nhất ($C_{max}$ - Makespan): Chỉ số hiệu suất thể hiện thời điểm hoàn thành công đoạn cuối cùng của chi tiết cuối cùng trong toàn bộ kế hoạch sản xuất.
• Biểu diễn nhiễm sắc thể dạng số nguyên (Integer Permutation Encoding): Cấu trúc chuỗi gen hoán vị đại diện trực tiếp cho thứ tự ưu tiên gia công của 12 đến 19 công việc trên hệ thống máy móc.
• Toán tử chọn lọc giải đấu (K-Tournament Selection): Cơ chế chọn lọc cá thể bố mẹ thông qua việc so tài giữa $K$ cá thể ngẫu nhiên, giúp kiểm soát áp lực chọn lọc và tránh thiên vị các cá thể vượt trội cục bộ.
• Toán tử lai chéo hai điểm (Two-point Crossover) và Đột biến hoán đổi (Swap Mutation): Các toán tử di truyền kết hợp thông tin cấu trúc và hoán đổi vị trí gen nhằm duy trì tính đa dạng quần thể, ngăn ngừa hiện tượng hội tụ sớm vào cực trị địa phương.

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

Nghiên cứu sử dụng nguồn dữ liệu thực nghiệm gồm 19 đơn hàng thực tế của tháng 8 năm 2022 tại nhà máy, bao gồm các dòng máy bơm bê tông tĩnh S30, S45 và thiết bị phun vảy Maxijet MX3. Cỡ mẫu nghiên cứu bao trùm toàn bộ chuỗi sản xuất qua 8 công đoạn chính: Cắt phôi, Chấn uốn, Gia công cơ khí (phay, tiện, khoan), Hàn, Sơn, Lắp ráp, Kiểm tra chất lượng (QC) và Nhập kho.

Phương pháp chọn mẫu có chủ đích (purposive sampling) được áp dụng để trích xuất dữ liệu từ các đơn hàng điển hình gặp sự cố trễ tiến độ lớn nhất, bảng định mức giờ công chuẩn và lịch trình vận hành của 15 máy gia công song song. Lý do lựa chọn giải thuật di truyền thay vì các phương pháp tối ưu hóa chính xác (như quy hoạch nguyên tuyến tính) là bởi bài toán FFSP thuộc nhóm bài toán NP-khó (NP-hard). Khi số lượng chi tiết vượt quá 10 công việc trên hệ thống nhiều máy song song, không gian nghiệm bùng nổ theo cấp số nhân khiến các thuật toán giải tích truyền thống không thể tìm ra lời giải trong thời gian đa thức khả thi. Giải thuật di truyền được lập trình hoàn toàn bằng ngôn ngữ Python 3.10 trên nền tảng máy tính cá nhân cấu hình tiêu chuẩn, trải qua quy trình nghiên cứu 8 bước kéo dài trong 16 tháng từ khảo sát hiện trạng, lập mô hình toán, kiểm chứng tính khả thi bằng giải tay trên quy mô nhỏ 5 công việc, đến thử nghiệm mô phỏng toàn diện trên dữ liệu thực tế.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình chạy nghiệm thực nghiệm với bộ tham số tối ưu (kích thước quần thể $N = 50$, xác suất lai chéo $P_c = 0,80$, xác suất đột biến $P_m = 0,05$ qua 100 thế hệ tiến hóa) đã mang lại những phát hiện đột phá:

Thứ nhất, giải thuật di truyền giúp rút ngắn tổng thời gian hoàn thành ($C_{max}$) từ 214 giờ sản xuất theo cách lập lịch kinh nghiệm xuống còn 168 giờ, tương đương mức tiết kiệm 46 giờ làm việc và cải thiện hiệu suất tiến độ đạt 21,50%.

Thứ hai, việc tối ưu hóa thứ tự đưa phôi vào chuyền đã triệt tiêu hoàn toàn 35 ngày trễ hạn của 12 đơn hàng trong tháng, nâng tỷ lệ giao hàng đúng hẹn từ 36,84% lên mức tuyệt đối 100,00% mà không cần yêu cầu các xưởng phải tổ chức làm thêm giờ (tăng ca).

Thứ ba, hệ số cân bằng tải và hiệu suất sử dụng của 15 máy móc tại các công đoạn nút thắt (như trạm hàn và trạm gia công cắt gọt) tăng từ 58,20% lên mức 82,40%, đồng thời thời gian chờ đợi tích lũy bán thành phẩm (WIP) giảm 34,60%.

Thứ tư, khi so sánh với các quy tắc điều độ kinh nghiệm cổ điển, giải thuật GA cho kết quả vượt trội: phương án của GA rút ngắn $C_{max}$ tốt hơn 12,40% so với quy tắc thời gian gia công ngắn nhất (SPT), tốt hơn 18,70% so với quy tắc thời gian gia công dài nhất (LPT) và tốt hơn 23,10% so với nguyên tắc đến trước phục vụ trước (FCFS).

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự chậm trễ nghiêm trọng trước đây là do doanh nghiệp bố trí đơn hàng theo từng cụm máy cố định dựa trên thói quen, dẫn đến tình trạng máy quá tải trong khi máy lân cận nhàn rỗi. Hơn nữa, việc một sản phẩm hoàn thiện cần nhiều chi tiết cấu thành nhưng các chi tiết này không được đồng bộ thời điểm hoàn tất khiến khâu lắp ráp liên tục rơi vào trạng thái chờ đợi linh kiện.

Dữ liệu mô phỏng được thể hiện trực quan qua Biểu đồ Gantt (Gantt Chart), mô tả chi tiết từng khoảng thời gian chiếm dụng máy của 19 mã sản phẩm trên trục thời gian thực tế, cho thấy các khoảng thời gian trống giữa các công đoạn được thu hẹp tối đa. Đồng thời, đồ thị hội tụ của hàm mục tiêu theo số thế hệ thể hiện rõ tốc độ hội tụ nhanh của thuật toán: giá trị Makespan giảm mạnh trong 30 thế hệ đầu tiên và đạt trạng thái tối ưu ổn định sau thế hệ thứ 70. Kết quả này hoàn toàn tương thích với các công bố học thuật quốc tế của Demir và İşleyen khi ứng dụng metaheuristic cho bài toán xưởng phức tạp, khẳng định tính đúng đắn và hiệu quả vượt bậc của GA trong thực tiễn sản xuất công nghiệp.

Đề xuất và khuyến nghị

Nhằm chuyển giao thành công kết quả nghiên cứu vào thực tế sản xuất tại các nhà máy cơ khí chế tạo, bốn nhóm giải pháp hành động cụ thể được khuyến nghị triển khai:

1. Chuẩn hóa hệ thống định mức giờ công và cơ sở dữ liệu sản xuất: Phòng Kỹ thuật sản xuất cần chủ trì thực hiện đo lường thời gian chuẩn (Standard Time) cho toàn bộ 8 công đoạn chế tạo của các dòng máy chủ lực (S30, S45, MX3), hoàn thành việc cập nhật thư viện định mức trong thời hạn 3 tháng với mục tiêu giảm sai số ước tính thời gian xuống dưới 5,00%.
2. Số hóa và tích hợp chương trình điều độ Python vào hệ thống quản trị: Bộ phận Công nghệ thông tin phối hợp cùng Ban Quản lý sản xuất đóng gói mã nguồn giải thuật GA thành ứng dụng nội bộ có giao diện trực quan, kết nối trực tiếp với cơ sở dữ liệu ERP/Excel hiện hữu trong lộ trình 4 tháng, hướng tới mục tiêu tự động hóa 90,00% thao tác lập kế hoạch hàng tuần.
3. Tái thiết lập quy trình quản lý bán thành phẩm tại khu vực tiền lắp ráp: Trưởng xưởng sản xuất và các tổ trưởng thực hiện đánh dấu khu vực đệm (buffer), áp dụng cơ chế kiểm soát trực quan (Visual Management) nhằm đảm bảo các chi tiết của cùng một bộ thiết bị được hoàn thành đồng bộ, cam kết giảm 30,00% diện tích chiếm dụng mặt bằng xưởng trong 6 tháng.
4. Tổ chức đào tạo kỹ năng vận hành và phân tích tham số thuật toán: Phòng Hành chính - Nhân sự phối hợp các chuyên gia tổ chức 02 khóa đào tạo chuyên môn cho 100% kỹ sư kế hoạch và điều độ sản xuất trong thời gian 2 tháng, đảm bảo nhân sự làm chủ việc tùy chỉnh các tham số xác suất lai ghép và đột biến khi quy mô đơn hàng biến động.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị tham khảo ứng dụng và học thuật chuyên sâu cho 4 nhóm đối tượng:

• Giám đốc điều hành và Quản lý sản xuất tại các nhà máy cơ khí, OEM: Nắm bắt phương pháp khoa học để tái cấu trúc quy trình lập lịch, giải phóng các nút thắt cổ chai, loại bỏ chi phí làm thêm giờ và tối ưu hóa năng lực phục vụ đơn hàng Make-To-Order.
• Kỹ sư Kỹ thuật Công nghiệp (Industrial Engineers) và Chuyên viên tối ưu hóa: Sử dụng mô hình toán học FFSP và mã nguồn thuật toán di truyền trên Python như một khung mẫu thực hành (framework) để tùy biến cho các bài toán phân bổ nguồn lực tại xưởng may mặc, điện tử hoặc chế biến gỗ.
• Học viên cao học và Nhà nghiên cứu chuyên ngành Kỹ thuật Hệ thống Công nghiệp: Tiếp cận một tài liệu thực nghiệm điển hình về việc ứng dụng giải thuật heuristic/metaheuristic giải quyết bài toán NP-khó với đầy đủ quy trình kiểm chứng toán học, phân tích độ nhạy và đánh giá sai số giữa lý thuyết và thực tiễn.
• Lập trình viên phát triển giải pháp phần mềm sản xuất (APS/MES): Tham khảo kiến trúc giải thuật, cấu trúc mã hóa dữ liệu đầu vào và phương pháp xuất biểu đồ Gantt tự động để tích hợp vào các hệ thống điều hành sản xuất thông minh.

Câu hỏi thường gặp

Tại sao bài toán điều độ flowshop linh hoạt (FFSP) lại được xếp vào nhóm bài toán NP-khó?

Bài toán FFSP kết hợp giữa việc phân chia thứ tự công việc và lựa chọn máy gia công song song ở mỗi công đoạn. Khi số lượng công việc ($n$) và số máy ($m$) tăng lên, không gian nghiệm tìm kiếm bùng nổ theo hàm giai thừa $(n!)^m$, khiến các thuật toán giải tích chính xác không thể tìm ra phương án tối ưu toàn cục trong khoảng thời gian chấp nhận được.

Giải thuật di truyền (GA) mang lại ưu thế gì vượt trội so với các quy tắc điều độ truyền thống?

Các quy tắc kinh nghiệm như SPT hay FCFS chỉ xem xét một tiêu chí cục bộ và mang tính tĩnh. Ngược lại, GA là thuật toán tìm kiếm ngẫu nhiên có định hướng dựa trên cơ chế tiến hóa tự nhiên, có khả năng khảo sát đồng thời nhiều vùng không gian nghiệm và tìm ra phương án cận tối ưu toàn cục tốt hơn từ 12,40% đến 23,10%.

Mô hình nghiên cứu này xử lý các ràng buộc máy song song và công đoạn như thế nào?

Mô hình toán học thiết lập các hàm ràng buộc chặt chẽ: mỗi máy chỉ gia công duy nhất 1 chi tiết tại một thời điểm, mỗi công việc chỉ được thực hiện trên đúng 1 máy ở mỗi công đoạn và bắt buộc phải hoàn thành ở công đoạn trước mới được chuyển sang công đoạn kế tiếp, đảm bảo tính khả thi 100% khi áp dụng vào thực tế xưởng.

Doanh nghiệp cần chuẩn bị những dữ liệu đầu vào nào để vận hành chương trình điều độ này?

Doanh nghiệp chỉ cần chuẩn bị 3 bảng dữ liệu cơ bản: Danh mục các đơn hàng cần gia công, Bảng quy trình công nghệ và định mức thời gian gia công của từng chi tiết trên các máy song song, cùng với Danh sách các máy móc khả dụng tại từng trạm sản xuất.

Chương trình Python của đề tài có khả năng mở rộng cho các bài toán quy mô lớn hơn không?

Hoàn toàn có thể. Do sử dụng cấu trúc mã hóa chuỗi gen số nguyên linh hoạt, chương trình cho phép mở rộng quy mô lên hàng trăm công việc và hàng chục công đoạn máy móc song song. Người vận hành chỉ cần điều chỉnh kích thước quần thể và số thế hệ tiến hóa tương ứng để đạt nghiệm tối ưu.

Kết luận

• Luận văn đã mô hình hóa thành công bài toán điều độ flowshop linh hoạt (FFSP) gồm 8 công đoạn với hệ thống máy song song tại nhà máy cơ khí quy mô thực tế.
• Xây dựng hoàn chỉnh chương trình giải thuật di truyền (GA) trên ngôn ngữ Python, giúp giảm 21,50% tổng thời gian hoàn thành sản xuất ($C_{max}$) từ 214 giờ xuống 168 giờ.
• Giải quyết triệt để vấn đề 63,16% đơn hàng bị trễ tiến độ, đưa tỷ lệ giao hàng đúng hẹn đạt mức hoàn hảo 100,00% mà không phát sinh thêm chi phí nhân công.
• Tăng tỷ lệ sử dụng máy móc trung bình từ 58,20% lên 82,40% và cắt giảm 34,60% lượng bán thành phẩm tồn ứ chờ đợi giữa các công đoạn.
• Đóng góp một giải pháp khoa học có tính ứng dụng cao, kết nối khoảng cách giữa lý thuyết tối ưu hóa toán học trừu tượng và thực tiễn điều hành sản xuất tại Việt Nam.

Kế hoạch phát triển tiếp theo của nghiên cứu trong giai đoạn 2024 - 2025 là mở rộng mô hình toán học nhằm tích hợp các yếu tố bất định thực tế như thời gian gá đặt máy phụ thuộc thứ tự (Sequence-Dependent Setup Time - SDST) và sự cố hỏng hóc máy móc ngẫu nhiên. Các nhà quản lý và kỹ sư sản xuất quan tâm có thể ứng dụng ngay khung phương pháp luận và mã nguồn giải thuật này để nâng cao hiệu suất vận hành cho doanh nghiệp mình.

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

Mở đầu  Chương 4 – Mô hình bài toán: Thu thập dữ liệu tại doanh nghiệp để xây dựng mô hình bài toán điều độ, bao gồm các khía cạnh từ thành phần đến cấu trúc dữ liệu đầu vào cho mô hình, đến dữ liệu đầu ra sau khi giải quyết vấn đề, với sự hỗ trợ của phần mềm hỗ trợ.  Chương 5 – Áp dụng mô hình giải thuật di truyền: Mô hình lập kế hoạch đã được xây dựng từ chương 4 sẽ được áp dụng vào thực tế hiện tại của công ty, sử dụng dữ liệu đầu vào thực tế từ tình trạng làm việc hàng ngày của nhà máy.  Chương 6 – Kết quả thực hiện và kiến nghị: Đánh giá kết quả của dự án, chương này thảo luận về những hạn chế hiện tại. Ngoài ra, nó còn đưa ra định hướng phát triển trong tương lai của dự án.

3 Chương 2: Cơ sở lý thuyết và phương pháp luận CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN 2. Điều độ trong sản xuất và dịch vụ 2. Lý thuyết điều độ cơ bản Điều độ là một quá trình ra quyết định được sử dụng một cách thường xuyên trong nhiều ngành công nghiệp sản xuất và dịch vụ. Nó liên quan đến việc phân bổ nguồn lực cho các nhiệm vụ trong khoảng thời gian nhất định và mục tiêu của nó là tối ưu hóa một hoặc nhiều mục tiêu.

Các nguồn lực và nhiệm vụ trong một tổ chức có thể ở nhiều dạng khác nhau. Tài nguyên có thể là máy móc trong xưởng, đường băng tại sân bay, đội ngũ tại công trường xây dựng, các đơn vị xử lý trong môi trường máy tính, v. Các nhiệm vụ có thể là hoạt động trong quy trình sản xuất, cất cánh và hạ cánh tại sân bay, các giai đoạn trong một dự án xây dựng, thực hiện các chương trình máy tính, v. Mỗi nhiệm vụ có thể có một mức độ ưu tiên nhất định, thời gian bắt đầu sớm nhất có thể và ngày đến hạn.

Các mục tiêu cũng có thể có nhiều hình thức khác nhau. Một mục tiêu có thể là giảm thiểu thời gian hoàn thành của nhiệm vụ cuối cùng và một mục tiêu khác có thể là giảm thiểu số lượng nhiệm vụ được hoàn thành sau ngày đến hạn tương ứng của chúng. Điều độ, với tư cách là một quá trình ra quyết định, đóng một vai trò quan trọng trong hầu hết các hệ thống sản xuất và chế tạo cũng như trong hầu hết các môi trường xử lý thông tin. Nó cũng quan trọng trong môi trường vận tải và phân phối cũng như trong các loại hình công nghiệp dịch vụ khác.

Chức năng điều độ trong sản xuất Chức năng lập kế hoạch trong hệ thống sản xuất hoặc tổ chức dịch vụ phải tương tác với nhiều chức năng khác. Những tương tác này phụ thuộc vào hệ thống và có thể khác nhau đáng 4 Chương 2: Cơ sở lý thuyết và phương pháp luận kể từ tình huống này sang tình huống khác. Chúng thường diễn ra trong một hệ thống thông tin toàn doanh nghiệp. Các đơn đặt hàng được phát hành trong môi trường sản xuất phải được chuyển thành các công việc có ngày đến hạn liên quan.

Những công việc này thường phải được xử lý trên máy trong một trung tâm làm việc theo một thứ tự hoặc trình tự nhất định. Quá trình xử lý công việc đôi khi có thể bị trì hoãn nếu một số máy đang bận và quyền ưu tiên có thể xảy ra khi các công việc có mức độ ưu tiên cao đến với các máy đang bận. Cũng phải tính đến các sự kiện không lường trước được trong khu vực sản xuất, chẳng hạn như sự cố máy móc hoặc thời gian xử lý lâu hơn dự kiến, vì chúng có thể ảnh hưởng lớn đến lịch sản xuất. Trong một môi trường như vậy, việc phát triển một điều đọi nhiệm vụ chi tiết giúp duy trì hiệu quả và kiểm soát các hoạt động.

Khu vực sản xuất không phải là bộ phận duy nhất của tổ chức tác động đến quá trình điều độ. Nó cũng bị ảnh hưởng bởi quá trình lập kế hoạch sản xuất. Điều độ trong môi trường flowshop linh hoạt Bài toán điều độ flowshop tổng quát là một bài toán sản xuất trong đó một tập hợp n công việc phải được xử lý với thứ tự công việc giống hệt nhau trên m máy và điều độ flowshop linh hoạt là sự tổng quát hóa của điều độ flowshop đơn giản và cổ điển với môi trường máy song song. Điều độ trong môi trường flowshop linh hoạt (FFSP) là một bài toán phức tạp liên quan đến việc điều độ một tập hợp công việc trên một tập hợp máy có nhiều giai đoạn xử lý, trong đó mỗi công việc có thể được xử lý trên nhiều máy trong một giai đoạn nhất định.

Mục tiêu của FFSP là giảm thiểu thước đo hiệu suất nhất định, chẳng hạn như tổng thời gian hoàn thành hoặc thời gian thực hiện. Trong bài toán FFSP tất định, có một số công việc cần được xử lý. Mỗi công việc đều có số lượng thao tác và trình tự xử lý cụ thể. Thời gian sẵn sàng của một công việc là thời điểm thao tác đầu tiên của nó sẵn sàng được xử lý, trong khi thời gian đến hạn của công việc là thời điểm thao tác cuối cùng phải được hoàn thành.

Cả hai dữ liệu này đều được xác định trước và khác với những dữ liệu khác. Mỗi thao tác chỉ có thể được xử lý bởi một máy trong một tập hợp các máy được xác định. Ngoài ra, còn một số hạn chế nữa góp phần làm phức 5 Chương 2: Cơ sở lý thuyết và phương pháp luận tạp bài toán như thời gian có sẵn của máy, mức độ ưu tiên của công việc, thời gian setup máy, thời gian vận chuyển, sản xuất hàng loạt… Hình 2.1 Sơ đồ dòng thông tin trong hệ thống sản xuất 2. Giải thuật di truyền Giải thuật di truyền (Genetic Algorithm - GA) lần đầu tiên được phát triển bởi John Holland và các cộng sự vào những năm 1960 và 1970 trong cuốn sách "Adaptation in Natural 6 Chương 2: Cơ sở lý thuyết và phương pháp luận and Artificial Systems".

Giải thuật này ban đầu là một mô hình của quá trình tiến hóa sinh học dựa trên lý thuyết chọn lọc tự nhiên của Darwin, sử dụng các nguyên tắc của phép lai chéo và tái tổ hợp, đột biến, và chọn lọc. Ứng dụng của Holland đối với GA đã được mở rộng thành nhiều loại bài toán tối ưu hóa khác nhau, và liên tục được phát triển và áp dụng trong nhiều lĩnh vực, từ thị trường tài chính đến tối ưu hóa kỹ thuật đa mục tiêu. Giải thuật di truyền, nổi tiếng nhờ hiệu quả trong việc giải các bài toán tối ưu hóa, đặc biệt có liên quan trong bối cảnh của các nhiệm vụ điều độ và tối ưu hóa. Mặc dù đã được mở rộng vào lĩnh vực kỹ thuật, thuật ngữ sử dụng cho GA vẫn bao gồm một số thuật ngữ sinh học.

Bao gồm "quần thể," ám chỉ nhóm các cá thể; "nhiễm sắc thể," chỉ các cá thể trong một quần thể; và "gen," là thành phần của một nhiễm sắc thể. Do đó, mỗi nhiễm sắc thể đại diện cho một giải pháp tiềm năng cho bài toán tối ưu hóa hiện tại. Giải thuật di truyền gồm có bốn quy luật cơ bản là: - Lai chéo. - Chọn lọc tự nhiên.

Quy trình lai chéo (phép lai): Quá trình này diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai nhiễm sắc thể cha-mẹ để hình thành nhiễm sắc thể mới mang đặc tính của cả cha lẫn mẹ. Phép lai này có thể mô tả như sau: - Chọn ngẫu nhiên hai hay nhiều cá thể trong quần thể. Giả sử chuỗi nhiễm sắc thể của cha và mẹ đều có chiều dài là m. - Tìm điểm lai bằng cách tạo ngẫu nhiên một con số từ 1 đến m-1.

Như vậy, điểm lai này sẽ chia hai chuỗi nhiễm sắc thể cha-mẹ thành hai nhóm nhiễm sắc thể con là m1 và m2. Hai chuỗi nhiễm sắc thể con lúc này sẽ là m11+m22 và m21+m12. - Đưa hai chuỗi nhiễm sắc thể con vào quần thể để tiếp tục tham gia quá trình tiến hóa. 7 Chương 2: Cơ sở lý thuyết và phương pháp luận Quá trình đột biến (phép đột biến).

Quá trình tiến hóa được gọi là quá trình đột biến khi một hoặc một số tính trạng của con không được thừa hưởng từ hai chuỗi nhiễm sắc thể cha-mẹ. Phép đột biến xảy ra với xác suất thấp hơn rất nhiều lần so với xác suất xảy ra phép lai. Phép đột biến có thể mô tả như sau: - Chọn ngẫu nhiên một số k từ khoảng 1 ≥ k ≥ m. - Thay đổi giá trị của gen thứ k.

- Đưa nhiễm sắc thể con vào quần thể để tham gia quá trình tiến hóa tiếp theo. Quá trình sinh sản và chọn lọc (phép tái sinh và phép chọn). Phép tái sinh: là quá trình các cá thể được sao chép dựa trên độ thích nghi của nó. Độ thích nghi là một hàm được gán các giá trị thực cho các cá thể trong quần thể của nó.

Phép tái sinh có thể mô phỏng như sau: - Tính độ thích nghi của từng cá thể trong quần thể, lập bảng cộng dồn các giá trị thích nghi đó (theo thứ tự gán cho từng cá thể) ta được tổng độ thích nghi. Giả sử quần thể có n cá thể. Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i là Ft. Tổng độ thích nghi là Fm.

- Tạo số ngẫu nhiên F có giá trị trong đoạn từ 0 đến Fm. - Chọn cá thể k đầu tiên thỏa mãn F ≥ Ft đưa vào quần thể của thế hệ mới. - Phép chọn: là quá trình loại bỏ các cá thể xấu và để lại những cá thể tốt. Phép chọn được mô tả như sau:  Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần.

 Loại bỏ các cá thể cuối dãy, chỉ để lại n cá thể tốt nhất.2 là biểu đồ dựa trên khái niệm Giải thuật Di truyền (GA) do Elisaveta G. Shopova và Natasha G. Vaklieva-Bancheva đề xuất, minh họa ứng dụng của GA trong việc giải quyết các bài toán tối ưu hóa. Ban đầu, thuật toán tạo ra một quần thể các nhiễm sắc thể đáp ứng các ràng buộc của vấn đề, sau đó giá trị độ phù hợp của từng nhiễm sắc thể được tính toán để đánh giá hiệu suất của nó.

Tiếp theo, các nhiễm sắc thể có giá trị độ phù hợp cao hơn sẽ được chọn cho quá trình tiến hóa.