Ứ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

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.

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.