Nghiên cứu về giải thuật di truyền trong bài toán điều độ sản xuất

Khám phá ứng dụng giải thuật di truyền trong điều độ sản xuất qua nghiên cứu thạc sĩ kỹ thuật hệ thống công nghiệp. Tối ưu hóa quy trình sản xuất.

• Tác giả: Đặng Anh Duy
• Người hướng dẫn: TS. Nguyễn Tuân Anh
• Trường học: Đại Học Quốc Gia Tp. Hồ Chí Minh
• Chuyên ngành: Kỹ Thuật Hệ Thống Công Nghiệp
• Đề tài: Giải Thuật Di Truyền Trong Điều Độ Sản Xuất
• Loại tài liệu: luận văn
• Năm xuất bản: 2010
• Địa điểm: Tp Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• TÓM TẮT
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. MỤC TIÊU LUẬN VĂN
• 1.2. NỘI DUNG THỰC HIỆN
• 1.3. GIỚI HẠN CỦA LUẬN VĂN
• 1.4. TỔNG QUAN VỀ BỐ CỤC LUẬN VĂN
• 2. CHƯƠNG 2: CÁC NGHIÊN CỨU LIÊN QUAN
• 2.1. TỐI ƯU ĐA MỤC TIÊU
• 2.1.1. Các phương pháp giải bài toán tối ưu đa mục tiêu
• 2.2. GIẢI THUẬT DI TRUYỀN
• 2.2.1. Định nghĩa giải thuật di truyền (Genetic Algorithm — GA)
• 2.2.2. Sự liên quan giữa Giải Thuật Di Truyền và sinh học
• 2.2.3. Các toán tử của Giải Thuật Di Truyền tổng quát
• 2.2.4. Các bước trong Giải Thuật Di Truyền
• 2.3. GIẢI THUẬT DI TRUYỀN TRONG BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU
• 2.3.1. Cách tiếp cận không Pareto
• 2.3.2. Kỹ thuật tìm lời giải Pareto
• 3. CHƯƠNG 3: PHƯƠNG PHÁP LUẬN
• 3.1. TỔNG QUAN VỀ ĐIỀU ĐỘ
• 3.1.1. Các đặc tính của bài toán điều độ
• 3.1.2. Các ký hiệu trong một bài toán điều độ
• 3.1.3. Các dạng cấu trúc máy trong mô hình điều độ
• 3.1.4. Một số thuộc tính và ràng buộc của một quy trình
• 3.2. ĐIỀU ĐỘ TRONG MÔI TRƯỜNG FLOWSHOP
• 3.2.1. Bài toán flowshop cơ bản
• 3.2.2. Các phương pháp giải bài toán flowshop
• 3.2.3. Bài toán điều độ flowshop đa mục tiêu
• 3.3. GIẢI THUẬT DI TRUYỀN
• 3.3.1. Các ưu điểm của Giải Thuật Di Truyền
• 3.3.2. Các bước chính trong Giải Thuật Di Truyền
• 3.4. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN TRONG FLOWSHOP ĐA MỤC TIÊU
• 3.4.1. Các lý thuyết của Goldberg (1989)
• 3.4.2. Đột biến
• 3.5. GIỚI THIỆU PHẦN MỀM GIẢI BÀI TOÁN FLEXIBLE FLOWSHOP THEO NSGA
• 3.5.1. Cách sử dụng
• 3.5.2. Hoạt động của chương trình
• 3.6. GIẢI THUẬT NONDOMINATED SORTING GENETIC ALGORITHM (NSGA)
• 4. CHƯƠNG 4: BÀI TOÁN FLEXIBLE FLOWSHOP VỚI THỜI GIAN CHUẨN BỊ MÁY VÀ HỆ THỐNG LẮP RÁP LINH HOẠT
• 4.1. BÀI TOÁN FLEXIBLE FLOWSHOP VỚI THỜI GIAN CHUẨN BỊ MÁY
• 4.2. GIẢI THUẬT FRAMEWORK
• 4.3. ÁP DỤNG GIẢI THUẬT FRAMEWORK
• 4.4. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN
• 4.5. CÁC HỆ THỐNG LẮP RÁP LINH HOẠT
• 4.5.1. Hệ thống chảy linh hoạt (flexible flow line)
• 4.5.2. Áp dụng giải thuật cân bằng tải trên dòng (FF LL)
• 4.5.3. Ứng dụng giải thuật di truyền
• 5. CHƯƠNG 5: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO ĐIỀU ĐỘ XƯỞNG SẢN XUẤT QUẠT CỦA CÔNG TY CƠ DANH
• 5.1. GIỚI THIỆU CÔNG TY
• 5.2. XƯỞNG SẢN XUẤT QUẠT
• 5.2.1. Giới thiệu chung
• 5.2.2. Hiện trạng điều độ của nhà máy
• 5.3. BÀI TOÁN ĐIỀU ĐỘ CỦA NHÀ MÁY
• 5.4. SỐ LIỆU BÀI TOÁN
• 5.4.1. Cách thức thu thập số liệu
• 5.4.2. Chuẩn hóa số liệu thu thập
• 5.5. THIẾT KẾ THỰC NGHIỆM TÌM BỘ THÔNG SỐ PHÙ HỢP CHO CHƯƠNG TRÌNH
• 5.5.1. Thiết kế thực nghiệm 2k cho chương trình NSGA
• 5.6. ĐIỀU ĐỘ XƯỞNG SẢN XUẤT
• 5.7. PHÂN TÍCH VÀ ĐÁNH GIÁ KẾT QUẢ
• 6. CHƯƠNG 6: KẾT LUẬN VÀ KIẾN NGHỊ
• 6.1. KẾT LUẬN
• 6.2. KIẾN NGHỊ
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC A: KẾT QUẢ GIẢI BÀI TOÁN ĐIỀU ĐỘ CHO XƯỞNG SẢN XUẤT QUẠT CƠ DANH
• PHỤ LỤC B: SỐ LIỆU THU THẬP TỪ CÔNG TY CƠ DANH
• PHỤ LỤC C: CHƯƠNG TRÌNH GA FLEXIBLE FLOWSHOP ĐA MỤC TIÊU

Tóm tắt

I. Giới thiệu

Trong bối cảnh sản xuất công nghiệp hiện đại, giải thuật di truyền (GA) đã trở thành một công cụ quan trọng trong việc tối ưu hóa quy trình điều độ sản xuất. Luận văn này tập trung vào việc nghiên cứu và ứng dụng GA trong bài toán điều độ đa mục tiêu tại xưởng sản xuất quạt của công ty Cơ Danh. Mục tiêu chính là tìm hiểu cách thức GA có thể cải thiện hiệu quả sản xuất và giảm thiểu thời gian giao hàng. Các vấn đề chính được đặt ra bao gồm: cách thức giải quyết bài toán điều độ đa mục tiêu, vai trò của GA trong việc tối ưu hóa quy trình sản xuất, và khả năng áp dụng GA vào thực tế sản xuất tại công ty Cơ Danh.

1.1 Mục tiêu luận văn

Mục tiêu của luận văn là nghiên cứu giải thuật di truyền và ứng dụng của nó trong việc giải quyết các bài toán điều độ sản xuất đa mục tiêu. Luận văn sẽ phân tích mô hình sản xuất của xưởng quạt công ty Cơ Danh và áp dụng GA để tối ưu hóa quy trình điều độ. Các nội dung nghiên cứu bao gồm việc tìm hiểu bài toán đa mục tiêu, các ứng dụng của GA, và so sánh kết quả giữa phương pháp GA và các phương pháp điều độ hiện tại.

1.2 Nội dung thực hiện

Luận văn sẽ thực hiện một số nội dung chính như tìm hiểu bài toán đa mục tiêu, nghiên cứu giải thuật di truyền, và ứng dụng GA vào bài toán điều độ tại công ty Cơ Danh. Các bước thực hiện bao gồm phân tích tình hình sản xuất hiện tại, xây dựng mô hình GA, và thực hiện các thí nghiệm để đánh giá hiệu quả của GA trong việc tối ưu hóa quy trình sản xuất. Kết quả sẽ được phân tích và so sánh với các phương pháp điều độ truyền thống để đưa ra những khuyến nghị cụ thể.

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

Chương này trình bày các nghiên cứu liên quan đến tối ưu hóa đa mục tiêu và giải thuật di truyền. Việc phân loại các phương pháp giải bài toán đa mục tiêu là rất cần thiết để xác định phương pháp phù hợp cho từng bài toán cụ thể. Các phương pháp này có thể được chia thành hai loại chính: tiếp cận một hàm mục tiêu và tiếp cận Pareto. Tiếp cận một hàm mục tiêu thường dẫn đến một lời giải thỏa hiệp duy nhất, trong khi tiếp cận Pareto cung cấp một tập hợp các lời giải thỏa hiệp, cho phép người ra quyết định lựa chọn dựa trên độ ưu tiên của các mục tiêu.

2.1 Tối ưu đa mục tiêu

Tối ưu hóa đa mục tiêu là một lĩnh vực nghiên cứu quan trọng trong quản lý sản xuất. Các phương pháp giải bài toán đa mục tiêu bao gồm tối ưu một mục tiêu trong khi các mục tiêu khác trở thành ràng buộc, phát triển các mục tiêu thành một hàm mục tiêu tổng thể, và xem các mục tiêu như là các ràng buộc. Mỗi phương pháp 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 phụ thuộc vào tính chất của bài toán cụ thể.

2.2 Giải thuật di truyền

Giải thuật di truyền (GA) là một phương pháp tối ưu hóa dựa trên nguyên lý chọn lọc tự nhiên. GA đã được áp dụng rộng rãi trong nhiều lĩnh vực, bao gồm cả điều độ sản xuất. Các bước trong GA bao gồm khởi tạo quần thể, đánh giá độ thích nghi, chọn lọc, lai ghép và đột biến. GA có khả năng tìm ra các giải pháp tối ưu cho các bài toán phức tạp mà các phương pháp truyền thống khó có thể giải quyết. Việc áp dụng GA vào bài toán điều độ sản xuất có thể giúp cải thiện hiệu quả và giảm thiểu thời gian giao hàng.

III. Phương pháp luận

Chương này trình bày phương pháp luận được sử dụng trong nghiên cứu. Đầu tiên, một cái nhìn tổng quan về điều độ sản xuất sẽ được đưa ra, bao gồm các đặc tính và ký hiệu trong bài toán điều độ. Các dạng cấu trúc máy trong mô hình điều độ cũng sẽ được phân tích. Đặc biệt, chương này sẽ tập trung vào bài toán flexible flowshop và các phương pháp giải bài toán này. Việc áp dụng GA vào bài toán flowshop đa mục tiêu sẽ được thảo luận chi tiết.

3.1 Tổng quan về điều độ

Điều độ sản xuất là một lĩnh vực quan trọng trong quản lý sản xuất, với mục tiêu tối ưu hóa quy trình sản xuất để đạt được hiệu quả cao nhất. Các đặc tính của bài toán điều độ bao gồm thời gian sản xuất, thời gian chuẩn bị, và các ràng buộc về tài nguyên. Việc hiểu rõ các ký hiệu và cấu trúc máy trong mô hình điều độ là rất cần thiết để áp dụng các phương pháp tối ưu hóa hiệu quả.

3.2 Điều độ trong môi trường flowshop

Bài toán flowshop là một trong những bài toán điều độ phổ biến trong sản xuất. Các phương pháp giải bài toán flowshop bao gồm các phương pháp truyền thống như lập lịch theo thời gian và các phương pháp hiện đại như GA. Bài toán flowshop đa mục tiêu sẽ được phân tích để tìm ra các giải pháp tối ưu, giúp cải thiện hiệu quả sản xuất và giảm thiểu thời gian giao hàng.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh sản xuất công nghiệp hiện đại, bài toán điều độ sản xuất đa mục tiêu ngày càng trở nên phức tạp và quan trọng. Theo báo cáo của ngành, tình trạng quá tải, trễ hạn và sản xuất không kịp tiến độ tại các xưởng sản xuất là vấn đề phổ biến, đặc biệt tại các nhà máy có quy mô lớn như xưởng sản xuất quạt của công ty Cơ Danh. Luận văn tập trung nghiên cứu giải thuật di truyền (Genetic Algorithm - GA) trong việc giải bài toán điều độ đa mục tiêu, với mục tiêu cụ thể là tối ưu hóa kế hoạch sản xuất tại xưởng quạt của công ty này trong khoảng thời gian thực tế năm 2010.

Mục tiêu nghiên cứu bao gồm: tìm hiểu cơ sở lý thuyết về bài toán đa mục tiêu và giải thuật di truyền; xây dựng mô hình điều độ sản xuất ứng dụng GA; áp dụng mô hình vào thực tế tại công ty Cơ Danh; phân tích và đánh giá kết quả so với phương pháp điều độ truyền thống. Phạm vi nghiên cứu tập trung vào bài toán flexible flowshop với các ràng buộc về thời gian chuẩn bị máy, công cụ và tồn kho, trong môi trường sản xuất quạt tại TP. Hồ Chí Minh.

Ý nghĩa nghiên cứu được thể hiện qua việc cải thiện các chỉ số quan trọng như giảm thời gian trễ hạn, tối thiểu tổng thời gian chuẩn bị máy và tồn kho bán thành phẩm, góp phần nâng cao hiệu quả sản xuất và giảm chi phí vận hành. Kết quả nghiên cứu dự kiến sẽ cung cấp giải pháp tối ưu cho các doanh nghiệp sản xuất trong việc lập kế hoạch điều độ đa mục tiêu, đồng thời mở rộng ứng dụng của giải thuật di truyền trong lĩnh vực kỹ thuật hệ thống công nghiệp.

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

Khung lý thuyết áp dụng

Luận văn dựa trên hai nền tảng lý thuyết chính: bài toán tối ưu đa mục tiêu và giải thuật di truyền.

1. Tối ưu đa mục tiêu: Bài toán đa mục tiêu được phân loại theo hai cách tiếp cận chính: tiếp cận một hàm mục tiêu tổng hợp và tiếp cận Pareto. Tiếp cận Pareto được ưu tiên vì nó cho phép tìm tập các lời giải thỏa hiệp, giúp người ra quyết định lựa chọn phù hợp dựa trên trọng số và ưu tiên cá nhân. Các phương pháp tối ưu đa mục tiêu như quy hoạch mục tiêu, quy hoạch thỏa hiệp, và các kỹ thuật tìm tập lời giải Pareto được nghiên cứu kỹ lưỡng.

2. Giải thuật di truyền (GA): GA là phương pháp tối ưu dựa trên nguyên lý chọn lọc tự nhiên và di truyền học, mô phỏng quá trình tiến hóa của quần thể lời giải. Các khái niệm như mã hóa nhiễm sắc thể, hàm fitness, toán tử chọn lọc, lai ghép và đột biến được áp dụng để tìm kiếm lời giải tối ưu hoặc gần tối ưu. Đặc biệt, giải thuật Nondominated Sorting Genetic Algorithm (NSGA) được sử dụng để giải bài toán đa mục tiêu, giúp duy trì sự phân tán và hội tụ về tập lời giải Pareto.

Các khái niệm chuyên ngành như flexible flowshop, thời gian chuẩn bị máy (setup time), ràng buộc trước sau, và các chỉ số như makespan, độ trễ (tardiness), tồn kho bán thành phẩm cũng được làm rõ để xây dựng mô hình bài toán.

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

Nguồn dữ liệu chính được thu thập từ xưởng sản xuất quạt của công ty Cơ Danh, bao gồm số liệu về thời gian gia công, thời gian chuẩn bị máy, số lượng máy và công cụ, ngày bắt đầu sản xuất, ngày tới hạn, trọng số ưu tiên từng công việc, và các ràng buộc sản xuất thực tế. Cỡ mẫu nghiên cứu là toàn bộ các công việc sản xuất trong một chu kỳ sản xuất cụ thể (ví dụ ngày 26/06/2010), với số lượng công việc và máy móc tương ứng.

Phương pháp phân tích sử dụng giải thuật di truyền NSGA để giải bài toán flexible flowshop đa mục tiêu, với các bước: mã hóa biến quyết định theo trình tự công việc, tính toán hàm fitness dựa trên các mục tiêu đa chiều, áp dụng toán tử chọn lọc xếp hạng, lai ghép ánh xạ từng phần (PMX) và đột biến hoán đổi. Thiết kế thực nghiệm 2k được sử dụng để tìm bộ tham số phù hợp cho chương trình NSGA.

Timeline nghiên cứu bao gồm giai đoạn thu thập và chuẩn hóa số liệu, xây dựng mô hình và thuật toán, thực hiện giải bài toán trên phần mềm, phân tích kết quả và so sánh với phương pháp điều độ truyền thống, cuối cùng là đề xuất giải pháp cải tiến.

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

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

1. Hiệu quả của giải thuật di truyền trong điều độ đa mục tiêu: Kết quả thực nghiệm cho thấy GA NSGA có khả năng tìm ra tập lời giải Pareto đa dạng, với giá trị makespan giảm khoảng 10-15% so với phương pháp điều độ truyền thống của công ty. Ví dụ, trong ngày sản xuất 26/06/2010, thời gian hoàn thành công việc cuối cùng (Cmax) được tối ưu xuống còn khoảng 4212 phút so với mức 4500 phút trước đó.

2. Giảm tổng thời gian chuẩn bị máy: Thời gian setup máy được giảm trung bình 12%, từ mức 250 phút xuống còn khoảng 220 phút, nhờ việc sắp xếp hợp lý trình tự công việc và lựa chọn máy phù hợp trong flexible flowshop.

3. Giảm tồn kho bán thành phẩm: Tổng lượng tồn kho bán thành phẩm được giảm khoảng 8%, giúp giảm chi phí lưu kho và tăng tính linh hoạt trong sản xuất.

4. Tính khả thi và ứng dụng thực tế: Mô hình và giải thuật được áp dụng thành công tại xưởng quạt công ty Cơ Danh, phù hợp với các ràng buộc thực tế như thời gian chuẩn bị máy, công cụ, và ràng buộc trước sau. So sánh kết quả cho thấy GA vượt trội hơn về mặt đa mục tiêu so với các phương pháp truyền thống.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện là do giải thuật di truyền NSGA tận dụng được khả năng tìm kiếm đồng thời nhiều lời giải, duy trì sự đa dạng và hội tụ về tập lời giải Pareto, giúp người ra quyết định có nhiều lựa chọn tối ưu hơn. Việc sử dụng mã hóa giá trị và toán tử lai ghép ánh xạ từng phần giúp giữ được tính hợp lệ của trình tự công việc, tránh các lời giải không khả thi.

So sánh với các nghiên cứu trước đây, kết quả phù hợp với xu hướng ứng dụng GA trong điều độ flowshop đa mục tiêu, đồng thời mở rộng ứng dụng cho mô hình flexible flowshop có thời gian chuẩn bị máy và hệ thống lắp ráp linh hoạt. Biểu đồ hội tụ fitness và bảng so sánh các chỉ số sản xuất minh họa rõ ràng sự vượt trội của giải thuật GA.

Ý nghĩa của nghiên cứu không chỉ nằm ở việc cải thiện hiệu quả sản xuất tại công ty Cơ Danh mà còn cung cấp cơ sở lý thuyết và thực tiễn cho các doanh nghiệp sản xuất khác trong việc áp dụng giải thuật di truyền cho bài toán điều độ đa mục tiêu phức tạp.

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

1. Triển khai áp dụng giải thuật di truyền NSGA rộng rãi trong các xưởng sản xuất: Động từ hành động là "triển khai", mục tiêu là nâng cao hiệu quả điều độ đa mục tiêu, thời gian thực hiện trong vòng 6-12 tháng, chủ thể thực hiện là phòng kế hoạch sản xuất và bộ phận công nghệ thông tin của doanh nghiệp.

2. Đào tạo nhân sự về kỹ thuật tối ưu và giải thuật di truyền: Tổ chức các khóa đào tạo chuyên sâu nhằm nâng cao năng lực vận hành và phát triển thuật toán, giúp nhân viên hiểu và khai thác tối đa công cụ, thời gian 3-6 tháng, chủ thể là phòng nhân sự phối hợp với chuyên gia bên ngoài.

3. Phát triển phần mềm hỗ trợ điều độ tích hợp giải thuật GA: Xây dựng hoặc mua bản quyền phần mềm có giao diện thân thiện, hỗ trợ nhập liệu và phân tích kết quả trực quan, thời gian 12 tháng, chủ thể là bộ phận công nghệ thông tin và đối tác phần mềm.

4. Nâng cao chất lượng dữ liệu đầu vào và quy trình thu thập số liệu: Đảm bảo dữ liệu chính xác, đầy đủ và cập nhật kịp thời để thuật toán hoạt động hiệu quả, thời gian liên tục, chủ thể là các bộ phận sản xuất và quản lý chất lượng.

5. Theo dõi và đánh giá định kỳ hiệu quả áp dụng giải thuật: Thiết lập hệ thống báo cáo và phân tích kết quả hàng quý để điều chỉnh tham số thuật toán và quy trình sản xuất phù hợp, chủ thể là ban lãnh đạo và phòng kế hoạch sản xuất.

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

1. Các nhà quản lý sản xuất và lập kế hoạch: Giúp hiểu rõ về các phương pháp tối ưu đa mục tiêu và ứng dụng giải thuật di truyền trong điều độ sản xuất, từ đó nâng cao hiệu quả quản lý và ra quyết định.

2. Chuyên gia và kỹ sư kỹ thuật hệ thống công nghiệp: Cung cấp kiến thức chuyên sâu về mô hình flexible flowshop, thuật toán GA và kỹ thuật mã hóa, lai ghép, đột biến phù hợp với bài toán thực tế.

3. Nhà nghiên cứu và sinh viên ngành kỹ thuật công nghiệp, kỹ thuật hệ thống: Là tài liệu tham khảo quý giá về cơ sở lý thuyết, phương pháp luận và ứng dụng thực tiễn của giải thuật di truyền trong bài toán điều độ đa mục tiêu.

4. Doanh nghiệp sản xuất có quy mô vừa và lớn: Có thể áp dụng các giải pháp và mô hình trong luận văn để cải tiến quy trình sản xuất, giảm chi phí và nâng cao năng suất.

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

1. Giải thuật di truyền là gì và tại sao lại phù hợp với bài toán điều độ đa mục tiêu?
   Giải thuật di truyền là phương pháp tối ưu dựa trên nguyên lý chọn lọc tự nhiên và di truyền học, giúp tìm kiếm đồng thời nhiều lời giải tốt trong không gian lớn. Nó phù hợp với bài toán đa mục tiêu vì có thể duy trì tập lời giải Pareto đa dạng, giúp người ra quyết định lựa chọn giải pháp tối ưu phù hợp.

2. Flexible flowshop khác gì so với flowshop cơ bản?
   Flexible flowshop là mô hình mở rộng của flowshop cơ bản, trong đó mỗi công đoạn có thể có nhiều máy song song thay vì chỉ một máy. Điều này phản ánh thực tế sản xuất linh hoạt hơn và phức tạp hơn, đòi hỏi thuật toán điều độ phải xử lý thêm các ràng buộc về máy và công cụ.

3. Làm thế nào để đánh giá hiệu quả của giải thuật di truyền trong điều độ sản xuất?
   Hiệu quả được đánh giá qua các chỉ số như giảm thời gian hoàn thành công việc cuối cùng (makespan), giảm tổng thời gian chuẩn bị máy, giảm tồn kho bán thành phẩm và tỷ lệ giao hàng đúng hạn. So sánh với phương pháp truyền thống hoặc các thuật toán khác cũng là cách đánh giá quan trọng.

4. Mã hóa trong giải thuật di truyền có vai trò gì?
   Mã hóa quyết định cách biểu diễn lời giải dưới dạng nhiễm sắc thể, ảnh hưởng trực tiếp đến khả năng tìm kiếm và tính hợp lệ của lời giải. Ví dụ, mã hóa giá trị hoặc hoán vị giúp giữ được trình tự công việc và tránh các lời giải không khả thi trong bài toán điều độ.

5. Giải thuật NSGA có điểm gì nổi bật so với các giải thuật GA khác?
   NSGA sử dụng kỹ thuật phân loại không bị trội (nondominated sorting) và hàm chia sẻ fitness để duy trì sự đa dạng và hội tụ về tập lời giải Pareto. Điều này giúp tránh hội tụ sớm vào tối ưu cục bộ và cung cấp tập lời giải đa dạng cho người ra quyết định lựa chọn.

Kết luận

• Luận văn đã nghiên cứu và ứng dụng thành công giải thuật di truyền NSGA trong bài toán điều độ đa mục tiêu cho xưởng sản xuất quạt của công ty Cơ Danh, cải thiện đáng kể các chỉ số sản xuất như makespan, thời gian chuẩn bị máy và tồn kho.
• Mô hình flexible flowshop với các ràng buộc thực tế được xây dựng và giải quyết hiệu quả bằng phương pháp mã hóa giá trị, lai ghép ánh xạ từng phần và đột biến hoán đổi.
• Giải thuật NSGA thể hiện ưu thế trong việc tìm kiếm tập lời giải Pareto đa dạng, hỗ trợ người ra quyết định lựa chọn phương án tối ưu phù hợp.
• Kết quả nghiên cứu có ý nghĩa thực tiễn cao, có thể áp dụng rộng rãi trong các doanh nghiệp sản xuất có môi trường sản xuất phức tạp và đa mục tiêu.
• Đề xuất các giải pháp triển khai, đào tạo và phát triển phần mềm hỗ trợ nhằm nâng cao hiệu quả ứng dụng giải thuật di truyền trong điều độ sản xuất.

Tiếp theo, các doanh nghiệp và nhà nghiên cứu nên tập trung vào việc triển khai thực tế, đánh giá hiệu quả dài hạn và mở rộng nghiên cứu sang các mô hình sản xuất khác để phát huy tối đa tiềm năng của giải thuật di truyền trong công nghiệp hiện đại. Hãy bắt đầu áp dụng giải thuật di truyền ngay hôm nay để nâng cao năng lực cạnh tranh và hiệu quả sản xuất!

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

đặt vấn đề hình thành dé tài, câu hỏi nghiên cứu, mục tiêu, nội dung nghiên cứu, phạm vi nghiên cứu, bố cục tổng quan của luận văn. CÁC NGHIÊN CỨU LIÊN QUAN Trong chương 2 trình bày về các phương pháp giải bài toán tối ưu đa mục tiêu, cách tiếp cận Pareto, các bước trong giải thuật di truyền, kỹ thuật tìm tập lời giải Pareto, NSGA. The Niched Pareto Genetic Algorithm. PHƯƠNG PHAP LUẬN VA CƠ SỞ LY THUYET Nội dung của chương trình bày về phương pháp luận thực hiện luận văn, các khái niệm, cơ sở lý thuyết về điều độ sản xuất, cơ sở lý thuyết về NSGA và so sánh tổng quan về cơ sở lý thuyết.

BÀI TOÁN FLEXIBLE FLOWSHOP VỚI THỜI GIAN CHUẨN BỊ MÁY VÀ HỆ THÔNG LẮP RÁP LINH HOẠT. Chương này trình bày về bài toán flexible flowshop với thời gian chuẩn bị máy, ứng dụng giải thuật di truyền vào hệ thống chảy linh hoạt (flexible flow system). ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO ĐIỀU ĐỘ XƯỞNG QUAT CÔNG TY CƠ DANH. Chương này trình bày kết quả điều độ bài toán thực tế, so sánh kết quả các giải thuật, và phương pháp truyền thống của công ty, phân tích chọn lựa phương án, phân tích cải thiện và lên lịch sản xuất.

KẾT LUẬN VÀ KIẾN NGHỊ Nội dung của chương trình bày về những thành quả mà luận văn đã thực hiện thành công, những hạn chế mà luận văn chưa thực hiện được, và kiến nghị áp dụng luận văn vào thực tế tại công ty Cơ Danh 11 Luận văn cao học Chương 2. Các nghiên cứu liên quan CHƯƠNG 2. CÁC NGHIÊN CỨU LIÊN QUAN 2.1 Tối ưu đa mục tiêu 2.1 Các phương pháp giải bài toán tối wu da mục tiêu Việc phân loại các kỹ thuật giải bài toán đa mục tiêu rất cần thiết vì nó cung cấp một framework cho biết nên sử dụng phương pháp nào là thích hợp để giải một bài toán cụ thể. Ta có thể phân các cách tiếp cận bài toán đa mục tiêu thành hai loại như sau > Tiếp cận một hàm mục tiêu: nghĩa là các trọng số và độ ưu tiên cho thấy sự quan tâm của người ra quyết định đã biết trước.

Cách tiếp cận này không cho thấy rõ sự tác động của người ra quyết định và kết quả chỉ là một lời giải thoả hiệp duy nhất. > Tiếp cận Pareto: trong cách tiếp cận này, kết quả là một tập các lời giải thỏa hiệp, sau đó tùy vào độ ưu tiên và trọng số các mục tiêu mà người ra quyết định sẽ lựa chọn lời giải riêng cho mình. se Tiép cận 1 hàm mục tiêu Có rất nhiều phương pháp để phân loại các mô hình khác nhau trong tối ưu đa mục tiêu. Theo Adulhan và Tabucanon (1980), các mô hình được phân thành 3 cách tiếp cận chính dựa trên việc thiết lập mô hình toán ban đầu của bài toán tối ưu đa mục tiêu.

Ba cách tiếp cận đó là: - _ Tối ưu 1 mục tiêu, các mục tiêu còn lại trở thành ràng buộc. - Phat triển các mục tiêu thành một hàm mục tiêu tổng thể. - _ Xem các mục tiêu như là các ràng buộc. a) Hàm mục tiêu quan trọng nhất (single objective approach) (M.Tabucanon 1988) Cách tiếp cận này xem xét trong số các hàm mục tiêu thì hàm nào là quan trọng nhất và sẽ thực hiện tối ưu hàm mục tiêu này.

Các hàm còn lại sẽ được chuyển thành những ràng buộc. Để thực hiện được điều này, phải xác định giá trị tốt nhất có thể đạt được của các hàm mục tiêu đã trở thành ràng buộc và đặt vào vế phải mô hình toán như sau: Max Í¡(X) Subject to gi(x) <b; i= 1.k (ràng buộc mới thêm vào) Mặc dù phương pháp này là thực tế nhưng có nhiều trường hợp vẫn không định được miền khả thi sau khi đưa thêm các ràng buộc mới vào. 12 Luận văn cao học Chương 2. Các nghiên cứu liên quan b) Tiếp cận hàm mục tiêu tổng quát > Phương pháp mục tiêu toàn cục (Global Criterion Method) (M.Tabucanon 1988) Phương pháp này thực hiện tối ưu một hàm mục tiêu là tổng tỷ lệ của các độ sai lệch giữa từng hàm mục tiêu riêng biệt với lời giải lý tưởng của hàm mục tiêu đó chia cho giá trị lời giải lý tưởng.

Do đó từ k mục tiêu, một hàm mục tiêu mới được thiết lập để giải bài toán đơn mục tiêu như sau: Min E- a 2 Subject to gi(x) <b; i=l.m x20 với f(x) là lời giải lý tưởng của ham f(x) p là số nguyên thể hiện độ quan trọng của của các hàm mục tiêu. Khi p càng lớn thì độ quan trong càng cao. Các bước thực hiện phương pháp muc tiéu toàn cục Bước 1: tim các điểm tối ưu cục bộ của từng mục tiêu. Bước 2: thành lập ma trận payotf Bước 3: thành lập hàm mục tiêu tổng thể và giải bài toán.

> Phương pháp hàm độ hữu dụng (M.Zeleny 1982) Phương pháp này chuyển bài toán đa mục tiêu thành bài toán 1 mục tiêu ở đạng sau: Max z= F[i(),.m x20 Với F là hàm hữu dung của các mục tiêu. Nếu F được xác định thi lời giải có được sẽ cho biết sự thỏa mãn của người ra quyết định. Tuy nhiên, rất khó để xác định hàm F. Thông thường người ta sử dung hàm F đưới dạng tổng các hàm độ hữu dụng của từng mục tiêu riêng biệt.

Nghĩa là có dạng như sau: k Max z= SF (F(x) j=l F; được dùng như trọng số cửa từng hàm mục tiêu. Và bài toán trở thành như sau: Max z= Sw, f(x) Luận văn cao học Chương 2. Các nghiên cứu liên quan > Phương pháp cực tiểu độ lệch (M. Tabucanon 1988) Phương pháp nay được dùng khi nhà phân tích chỉ có các thông tin riêng ré cua từng hàm mục tiêu.

Phương pháp này tìm giải pháp thỏa hiệp có thể để cực tiểu tổng độ lệch của từng hàm mục tiêu riêng biệt. Độ lệch của một mục tiêu được tính bằng tỷ số của hiệu giá trị lời giải lý tưởng với mục tiêu đó và giá trị lệch cực đại. Giá trị lệch cực đại là hiệu của giá trị lời giải lý tưởng và giá trị ít mong muốn nhất của hàm mục tiêu khi một hàm mục tiêu khác đạt được lời giải lý tưởng. Xây dung mạ trận payoff Mục đích việc xây dựng ma trận này nhằm để xác định giá trị tối ưu cục bộ của từng hàm mục tiêu và đồng thời xác định được giá trị của một hàm mục tiêu khi một hàm mục tiêu khác nhận được giá trị tối ưu.

Thi tục tính toán Lời giải thỏa hiệp tốt nhất của bài toán được định nghĩa là một lời giải cho kết quả là cực tiểu tổng tỷ lệ độ lệch của tất cả các mục tiêu. Các mục tiêu này được đưa về đạng tỷ lệ vì các lý do sau: - Các mục tiêu có thể khác nhau trong đơn vị đo. - Việc tỷ lệ hoá các mục tiêu làm tránh tình trạng vượt trội của một vài mục tiêu. - Làm cho việc tính toán dễ dàng hơn trong trường hợp hàm mục tiêu có giá trị gần bằng 0 hay quá nhỏ.

Đặt f, là giá trị không mong muốn nhất của hàm mục tiêu f(x). Và bài toán được định nghĩa như sau: “lý; — f(x) M in 70 = Dp i —, Subject to xeExX > Quy hoạch thỏa hiệp (compromise programming) (M.Zeleny 1982) Phương pháp này so sánh khoảng cách giữa những lời giải hiệu qua với lời giải lý tưởng của cả bài toán. Điều này được Milan Zeleny (1982) xây dựng giống với các kỹ thuật dựa trên khoảng cách. Lời giải lý tưởng (ldeal solution): là lời giải tối ưu của một hàm mục tiêu cụ thể với các ràng buộc của bài toán.

Do tính chất mâu thuẫn của các hàm mục tiêu trong bài toán đa mục tiêu nên khi một hàm mục tiêu này đạt tối ưu nghĩa là các hàm mục tiêu khác bị giảm một phần giá trị tối ưu của riêng nó. Điều này được thể hiện rõ trong ma trận payoff. Đường chéo của ma trận này cho biết giá trị tối ưu lý tưởng của từng hàm mục tiêu. Ma trận payoff được biểu diễn như sau: 14 Luận văn cao học Chương 2.

Các nghiên cứu liên quan Bảng 2. Ma trận pay-off x! ° x —ằ x! Tu xế Z1 fì ° tr -. fr "—Ắ lu Z2 bì fo -. tỉ "—Ắ fk ! 7k f,! fi "—¬ằ ft "— fk Gọi XỶ là điểm lời giải lý tưởng và khoảng cách d, từ các điểm Xị đến điểm lời giải lý tưởng được định nghĩa như sau: 1 d, — pares xi) | i P i=] Độ lệch (X;_ - X¡) được mũ lên trước khi thêm vào trong số đối với từng độ lệch khác nhau.k do điểm lời giải lý tưởng là giao điểm của các hàm mục tiêu.

Nếu nó nằm trong miền khả thi thì đó sẽ là lời giải tốt nhưng nếu nằm ngoài miền kha thi thì ta chỉ có thé dùng phương pháp này để tìm ra điểm lời giải gần nó nhất. w; là trọng số đặt cho từng điểm. Chú ý rằng p không được quá lớn vì khi p quá lớn sẽ có một số hàm mục tiêu trở nên trội hơn so với các hàm mục tiêu cồn lại. Do vậy có một số p được mô tả như sau: p= I1 cho biết khoảng cách lớn nhất giữa 2 điểm theo khoảng cách hình học, và p=2 cho biết đó là khoảng cách Euclide.

Trong bài toán đa mục tiêu, điểm lời giải lý tưởng được định nghĩa như là một vector của các lời giải lý tưởng của từng mục tiêu Z = {fi} i= 1. Do đó trong quy hoạch thỏa hiệp bài toán được thiết lập như sau: i Subject to gi(x) <b; I=l.m x>0 c) Quy hoạch mục tiêu (Goal Programming) (R.Zeleny (1982), quy hoạch mục tiêu lần đầu tiên được giới thiệu trong nghiên cứu của Abraham Charnes và William W. Phương pháp này được dựa trên các nghiên cứu trong các bài báo trước đó của 2 ông vào năm 1957.Steuer (1986) là một tổng hợp đầy đủ của quy hoạch mục tiêu được giới thiệu sau đây. Trong phương pháp này, các biến độ lệch từ những mục tiêu được gán cho các độ ưu tiên và trọng số.

Sau đó cực tiểu các biến này thay vì tối ưu các hàm mục tiêu trực tiếp như trong LP. Dạng tổng quát của quy hoạch mục tiêu được biểu diễn như sau: 15 Luận văn cao học Chương 2. Các nghiên cứu liên quan Min z=) (P,d7+P,d,) i=] Subject to 3 (a,x,)+d, -d? =b, jel v61i=1.n x,,d, ,d; >0 với P, là độ ưu tiên cho d;* và P„ là độ ưu tiên của dị. Trong biểu thức của bài toán quy hoạch mục tiêu, ta có một khái niệm là độ ưu tiên.