Luận Văn Thạc Sĩ Về Phương Pháp Tối Ưu Đàn Kiến Giải Bài Toán Lập Lịch Sản Xuất

Luận văn thạc sĩ nghiên cứu vnu uet phương pháp tối ưu đàn kiến giải bài toán lập lịch sản xuất, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vực

• Chuyên ngành: Tối Ưu Hóa, Lập Lịch Sản Xuất
• Đề tài: Phương Pháp Tối Ưu Đàn Kiến Trong Lập Lịch Sản Xuất
• Loại tài liệu: Luận Văn

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: TỐI ƯU HÓA ĐÀN KIẾN VÀ ỨNG DỤNG
• 1.1. Giới thiệu bài toán lập lịch sản xuất (Job shop scheduling - JSS)
• 1.2. Các cách tiếp cận truyền thống
• 1.3. Bài toán JSS trong trường hợp hai máy
• 1.4. Bài toán JSS với số máy lớn hơn 2
• 2. CHƯƠNG 2: BÀI TOÁN LẬP LỊCH SẢN XUẤT VÀ CÁC PHƯƠNG PHÁP GIẢI CHÍNH
• 3. CHƯƠNG 3: SẢN XUẤT T CHUNG ĐỂ LẬP LỊCH SẢN XUẤT
• 3.1. ACO giải bài toán lập lịch sản xuất
• 3.2. Độ phức tạp các thuật toán MMAS, SMMAS, MLAS
• 3.3. Kết quả thực nghiệm của MMAS
• 3.4. Kết quả thực nghiệm của MMAS, SMMAS và MLAS
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phương Pháp Tối Ưu Đàn Kiến Trong Lập Lịch Sản Xuất

Phương pháp tối ưu đàn kiến (ACO) là một trong những kỹ thuật tiên tiến trong việc lập lịch sản xuất. ACO mô phỏng hành vi của đàn kiến trong việc tìm kiếm thức ăn, từ đó áp dụng vào các bài toán tối ưu hóa. Phương pháp này giúp cải thiện hiệu suất sản xuất và giảm thiểu thời gian lập lịch. Việc áp dụng ACO trong lập lịch sản xuất không chỉ mang lại hiệu quả cao mà còn giúp giải quyết các bài toán phức tạp mà các phương pháp truyền thống không thể xử lý.

1.1. Định Nghĩa và Nguyên Tắc Hoạt Động Của ACO

ACO là một thuật toán meta-heuristic dựa trên hành vi của đàn kiến. Các con kiến để lại vết mùi (pheromone) để hướng dẫn nhau đến nguồn thức ăn. Trong lập lịch sản xuất, ACO sử dụng vết mùi này để tìm ra lịch trình tối ưu, giúp giảm thiểu thời gian và chi phí sản xuất.

1.2. Lợi Ích Của Việc Áp Dụng ACO Trong Lập Lịch Sản Xuất

Việc áp dụng ACO trong lập lịch sản xuất mang lại nhiều lợi ích như: tối ưu hóa quy trình sản xuất, giảm thiểu thời gian chờ đợi, và nâng cao hiệu suất làm việc. ACO cũng giúp giải quyết các bài toán phức tạp mà các phương pháp truyền thống không thể xử lý hiệu quả.

II. Các Thách Thức Trong Lập Lịch Sản Xuất Hiện Nay

Lập lịch sản xuất hiện nay đối mặt với nhiều thách thức lớn. Sự gia tăng quy mô sản xuất và yêu cầu về chất lượng sản phẩm ngày càng cao đã tạo ra áp lực lớn cho các nhà quản lý. Các thách thức này bao gồm việc tối ưu hóa quy trình sản xuất, quản lý nguồn lực hiệu quả và đáp ứng kịp thời nhu cầu của thị trường.

2.1. Vấn Đề Quản Lý Nguồn Lực Trong Sản Xuất

Quản lý nguồn lực là một trong những thách thức lớn nhất trong lập lịch sản xuất. Việc phân bổ nguồn lực không hợp lý có thể dẫn đến tình trạng thiếu hụt hoặc lãng phí, ảnh hưởng đến hiệu suất sản xuất.

2.2. Tính Phức Tạp Của Các Bài Toán Lập Lịch

Các bài toán lập lịch sản xuất thường có tính phức tạp cao, đặc biệt là trong các hệ thống sản xuất lớn. Việc tìm ra lịch trình tối ưu trong thời gian ngắn là một thách thức lớn mà các nhà quản lý phải đối mặt.

III. Phương Pháp Tối Ưu Đàn Kiến Trong Giải Quyết Bài Toán Lập Lịch

Phương pháp tối ưu đàn kiến đã được chứng minh là hiệu quả trong việc giải quyết các bài toán lập lịch sản xuất. ACO sử dụng các thuật toán thông minh để tìm ra lịch trình tối ưu, giúp giảm thiểu thời gian và chi phí sản xuất. Các thuật toán như MMAS, SMMAS và MLAS đã được áp dụng thành công trong nhiều nghiên cứu.

3.1. Thuật Toán MMAS Trong Lập Lịch Sản Xuất

Thuật toán Max-Min Ant System (MMAS) là một trong những phương pháp ACO hiệu quả nhất. MMAS giúp cải thiện độ hội tụ của thuật toán và tìm ra giải pháp tối ưu nhanh chóng hơn so với các phương pháp khác.

3.2. Ứng Dụng Của ACO Trong Các Bài Toán Thực Tế

ACO đã được áp dụng thành công trong nhiều bài toán thực tế, từ lập lịch sản xuất trong nhà máy đến tối ưu hóa quy trình logistics. Các nghiên cứu cho thấy ACO có thể cải thiện đáng kể hiệu suất sản xuất và giảm chi phí.

IV. Kết Quả Nghiên Cứu Về ACO Trong Lập Lịch Sản Xuất

Nhiều nghiên cứu đã chỉ ra rằng ACO có thể mang lại kết quả vượt trội trong lập lịch sản xuất. Các kết quả thực nghiệm cho thấy ACO không chỉ giúp tối ưu hóa quy trình mà còn nâng cao hiệu suất làm việc của các nhà máy. Việc áp dụng ACO đã giúp nhiều doanh nghiệp tiết kiệm chi phí và thời gian sản xuất.

4.1. Kết Quả Thực Nghiệm Của ACO

Các kết quả thực nghiệm cho thấy ACO có thể giảm thiểu thời gian lập lịch và tăng cường hiệu suất sản xuất. Nhiều doanh nghiệp đã áp dụng ACO và đạt được những thành công đáng kể.

4.2. So Sánh ACO Với Các Phương Pháp Khác

So với các phương pháp lập lịch truyền thống, ACO cho thấy hiệu quả vượt trội hơn trong việc tối ưu hóa quy trình sản xuất. Nghiên cứu đã chỉ ra rằng ACO có thể tìm ra giải pháp tốt hơn trong thời gian ngắn hơn.

V. Kết Luận Về Tương Lai Của ACO Trong Lập Lịch Sản Xuất

Tương lai của ACO trong lập lịch sản xuất rất hứa hẹn. Với sự phát triển của công nghệ và các thuật toán thông minh, ACO sẽ tiếp tục được cải tiến và áp dụng rộng rãi hơn trong các lĩnh vực sản xuất. Việc nghiên cứu và phát triển ACO sẽ giúp nâng cao hiệu suất sản xuất và đáp ứng tốt hơn nhu cầu của thị trường.

5.1. Xu Hướng Phát Triển ACO Trong Tương Lai

Trong tương lai, ACO sẽ tiếp tục được phát triển với các thuật toán mới và cải tiến. Sự kết hợp giữa ACO và các công nghệ mới như trí tuệ nhân tạo sẽ mở ra nhiều cơ hội mới cho lập lịch sản xuất.

5.2. Tác Động Của ACO Đến Ngành Sản Xuất

ACO sẽ có tác động lớn đến ngành sản xuất, giúp tối ưu hóa quy trình và nâng cao hiệu suất. Các doanh nghiệp sẽ có cơ hội tiết kiệm chi phí và thời gian, từ đó nâng cao khả năng cạnh tranh trên thị trườ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 lập lịch sản xuất đóng vai trò xương sống quyết định năng lực cạnh tranh của doanh nghiệp. Việc tối ưu hóa lịch trình vận hành có thể giúp giảm từ 15% đến 30% thời gian máy chờ và tiết kiệm hàng tỷ đồng chi phí lưu kho mỗi năm. Tuy nhiên, bài toán lập lịch sản xuất với quy mô từ 3 máy trở lên thuộc lớp bài toán NP-khó phức tạp nhất trong tối ưu hóa tổ hợp. Một minh chứng kinh điển là bài toán MT10 gồm 10 công việc thực hiện trên 10 máy do Thompson đưa ra năm 1963, đã thách thức giới khoa học suốt 22 năm và phải đến năm 1985 mới tìm ra được lời giải tối ưu thông qua phương pháp nhánh cận.

Vấn đề nghiên cứu cốt lõi mà luận văn giải quyết là sự bùng nổ tổ hợp của không gian trạng thái khi số lượng máy và công việc tăng lên, khiến các phương pháp giải chính xác hoàn toàn bất khả thi về mặt thời gian tính toán và dung lượng bộ nhớ. Mặc dù thuật toán tối ưu hóa đàn kiến xuất hiện từ năm 1991 mang lại hướng tiếp cận phỏng sinh học đầy triển vọng, nhưng các mô hình truyền thống thường gặp hiện tượng đình trệ và hội tụ sớm vào các cực trị địa phương.

Mục tiêu cụ thể của luận văn là nghiên cứu sâu cơ chế truyền thông tin qua vết mùi pheromone, phân tích toán học tính hội tụ, từ đó đề xuất hai thuật toán cải tiến vượt bậc: Hệ kiến cực đại - cực tiểu trơn và Hệ kiến đa mức. Nghiên cứu thực hiện đánh giá thực nghiệm toàn diện trên 10 bộ dữ liệu chuẩn quốc tế từ Orb1 đến Orb10 với quy mô 10 công việc trên 10 máy. Các kết quả nghiên cứu đã được công nhận và công bố chính thức tại hai hội nghị quốc tế uy tín là IEEE RIVF 2006 và PRIMA 2008, mang lại giải pháp nâng cao hiệu suất điều độ lên trên 20% và tiệm cận giới hạn lý thuyết 5/4 nghiệm tối ưu của Williamson.

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 được xây dựng dựa trên nền tảng vững chắc của hai trụ cột lý thuyết: Lý thuyết tối ưu hóa tổ hợp meta-heuristic và Lý thuyết điều độ sản xuất công nghiệp. Mô hình toán học tổng quát của bài toán lập lịch xưởng sản xuất được phát biểu với tập hợp n công việc cần gia công trên m máy công cụ, trong đó mỗi công việc gồm chuỗi m thao tác công nghệ bắt buộc tuân thủ thứ tự nghiêm ngặt và mỗi máy chỉ phục vụ duy nhất một thao tác tại một thời điểm.

Nghiên cứu triển khai mô hình hóa bài toán thành đồ thị cấu trúc có trọng số gồm tập đỉnh, tập cạnh, véc-tơ heuristic và ma trận vết mùi. Số lượng đỉnh trên đồ thị cấu trúc được xác định chính xác theo công thức bằng tích của số công việc nhân với số máy cộng thêm một đỉnh xuất phát gốc, tương ứng 101 đỉnh cho bài toán 10 công việc trên 10 máy. Hành trình di chuyển khép kín của một con kiến nhân tạo tương ứng với một hoán vị hợp lệ của các thao tác, sau đó được ánh xạ trực tiếp sang một lịch sản xuất khả thi.

Khung phân tích tập trung vào 4 khái niệm chuyên ngành cốt lõi:

• Cường độ vết mùi tích lũy: Thể hiện tri thức tập thể của đàn kiến qua các thế hệ nhằm dẫn đường cho các cá thể tiếp theo.
• Thông tin heuristic: Được xác định bằng nghịch đảo thời gian xử lý của từng thao tác, cung cấp thông tin dẫn hướng cục bộ tĩnh.
• Hiện tượng đình trệ tìm kiếm: Trạng thái đàn kiến tập trung quá mức vào một hành trình dưới tối ưu do chênh lệch vết mùi quá lớn.
• Quy tắc cập nhật mùi đa mức: Cơ chế điều chỉnh vết mùi linh hoạt theo thời gian thực kết hợp giữa cập nhật trực tuyến và cập nhật ngoại tuyến.

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

Nguồn dữ liệu thực nghiệm được trích xuất từ thư viện chuẩn quốc tế OR-Library, bao gồm 10 bộ dữ liệu benchmark kinh điển từ Orb1 đến Orb10. Cỡ mẫu nghiên cứu gồm 10 bộ dữ liệu có mức độ phức tạp cao nhất, mỗi bộ chứa 10 công việc thực hiện trên 10 máy với 100 thao tác độc lập. Phương pháp chọn mẫu chủ đích được áp dụng nhằm đảm bảo dữ liệu nghiên cứu đại diện cho những trường hợp sản xuất phức tạp nhất, loại bỏ hoàn toàn sai số chủ quan và cho phép đối chuẩn trực tiếp với các công bố quốc tế.

Lý do lựa chọn phương pháp phân tích thực nghiệm kết hợp phân tích độ phức tạp thuật toán xuất phát từ bản chất NP-khó của bài toán lập lịch. Nghiên cứu thực hiện 10 lần chạy độc lập cho mỗi bộ dữ liệu với 50.000 vòng lặp cho mỗi lần thử nghiệm để triệt tiêu yếu tố ngẫu nhiên, từ đó trích xuất hai chỉ số định lượng: kết quả tốt nhất và kết quả trung bình. Toàn bộ quá trình nghiên cứu, mô hình hóa toán học, tinh chỉnh tham số với hệ số bay hơi mùi 0.01, quy mô đàn kiến 10 cá thể, trọng số vết mùi 1.4 và kiểm chứng đối chuẩn được thực hiện trong khung thời gian 18 tháng.

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

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

Thứ nhất, nghiên cứu phát hiện sự ảnh hưởng quyết định của tỷ lệ biên vết mùi đến chất lượng nghiệm. Khi thực nghiệm thuật toán Hệ kiến cực đại - cực tiểu trên các bộ dữ liệu Orb với các tỷ lệ biên mùi khác nhau từ 1/2, 1/3, 1/4 đến 1/5, kết quả chứng minh tỷ lệ 1/2 đem lại hiệu năng vượt trội nhất. Điển hình trên bộ dữ liệu Orb1, tỷ lệ 1/2 đạt kết quả tốt nhất là 1340 và trung bình là 1368 đơn vị thời gian, trong khi tỷ lệ 1/3 khiến kết quả tốt nhất suy giảm xuống 1366 và trung bình lên tới 1398.9, tương đương mức suy giảm hiệu năng hơn 2.2%.

Thứ hai, thuật toán Hệ kiến cực đại - cực tiểu trơn giúp làm chậm tốc độ suy giảm mùi trên các cạnh không thuộc hành trình tốt nhất về mức cực tiểu. Cơ chế này giúp đàn kiến duy trì khả năng khám phá không gian giải pháp rộng hơn, cải thiện chất lượng nghiệm trung bình thêm 3.5% và loại bỏ hoàn toàn chi phí thời gian kiểm soát biên mùi so với phương pháp gốc.

Thứ ba, thuật toán Hệ kiến đa mức tạo ra bước đột phá về tối ưu hóa chi phí tính toán. Bằng việc phân tách thành cập nhật trực tuyến cho mọi cá thể với mức mùi trung gian và cập nhật ngoại tuyến cho cá thể tốt nhất với mức mùi tối đa, thuật toán đã loại bỏ hoàn toàn giai đoạn bay hơi toàn cục tốn kém. Độ phức tạp tính toán được giảm từ mức bậc hai theo tích số công việc và máy xuống mức tuyến tính, giúp tiết kiệm hơn 40% tài nguyên xử lý trên mỗi vòng lặp.

Thứ tư, kết quả thử nghiệm trên toàn bộ 10 bộ dữ liệu chuẩn Orb1 đến Orb10 đều cho thấy các thuật toán cải tiến đạt chất lượng tiệm cận nghiệm tối ưu lý thuyết, vượt xa ngưỡng chặn xấp xỉ 5/4 của định lý Williamson với độ lệch trung bình dưới 8%.

Thảo luận kết quả

Nguyên nhân căn bản giúp các thuật toán cải tiến đạt kết quả vượt trội nằm ở việc cân bằng hoàn hảo giữa hai yếu tố: khai thác tri thức đã biết và khám phá không gian tìm kiếm mới. Trong các hệ thống truyền thống, sự chênh lệch quá lớn giữa mức mùi cực đại và cực tiểu khiến các cạnh tiềm năng nhanh chóng bị triệt tiêu mùi, khóa đàn kiến vào các nghiệm cục bộ. Việc áp dụng mức mùi trung gian bằng một nửa mức mùi tối đa trong thuật toán đa mức đã tạo ra một lực đẩy phân tán hợp lý, mở rộng diện tích tìm kiếm trong những vòng lặp đầu và hội tụ êm thuận ở những vòng lặp cuối.

Dữ liệu thực nghiệm của nghiên cứu được trực quan hóa tối ưu thông qua hai dạng thức:

• Biểu đồ đường tiến hóa: Thể hiện quỹ đạo hội tụ của tổng thời gian hoàn thành công việc qua 50.000 bước lặp, minh chứng tốc độ giảm thời gian hoàn thành vượt trội của Hệ kiến đa mức so với Hệ kiến cực đại - cực tiểu ngay từ vòng lặp thứ 10.000.
• Bảng ma trận so sánh 10 bộ dữ liệu: Trình bày chi tiết các cột chỉ số giá trị tốt nhất, giá trị trung bình và thời gian CPU thực thi, khẳng định độ lệch chuẩn cực nhỏ của thuật toán mới sau 10 lần chạy thử nghiệm độc lập.

So với các phương pháp giải tích tiến hóa như Giải thuật Di truyền hay phương pháp Nhánh cận, cách tiếp cận bằng đàn kiến cải tiến cho thấy khả năng thích ứng linh hoạt hơn hẳn khi số lượng thao tác vượt mốc 50, giảm đáng kể nguy cơ tràn bộ nhớ hệ thống.

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

Thứ nhất, tích hợp trực tiếp thuật toán Hệ kiến đa mức vào các hệ sinh thái phần mềm quản trị sản xuất và hoạch định tài nguyên doanh nghiệp. Chủ thể thực hiện là các giám đốc công nghệ và kỹ sư phát triển phần mềm công nghiệp. Mục tiêu cần đạt là cắt giảm tối thiểu 25% thời gian máy chạy không tải và nâng cao chỉ số hiệu suất thiết bị tổng thể thêm 15%. Lộ trình triển khai khuyến nghị trong vòng 6 tháng đầu năm.

Thứ hai, chuẩn hóa và tự động hóa khâu thu thập dữ liệu đầu vào bao gồm ma trận công nghệ và ma trận thời gian gia công thông qua hệ thống cảm biến Internet vạn vật công nghiệp. Chủ thể thực hiện là phòng điều độ sản xuất kết hợp cùng bộ phận chuyển đổi số. Mục tiêu là triệt tiêu hoàn toàn độ trễ dữ liệu và giữ sai số thời gian thực thi dưới mức 3%. Thời gian hoàn thiện quy chuẩn trong vòng 9 tháng.

Thứ ba, nghiên cứu lai ghép thuật toán Hệ kiến đa mức với các kỹ thuật tìm kiếm địa phương như Tìm kiếm Cấm hoặc Thuật toán Tìm kiếm Ngẫu nhiên Thích nghi Cục bộ. Chủ thể thực hiện là các nhóm nghiên cứu và phát triển tại viện nghiên cứu và trường đại học. Mục tiêu nhằm tối ưu thêm từ 5% đến 8% thời gian hoàn thành đối với các xưởng sản xuất siêu lớn có quy mô trên 50 máy gia công. Lộ trình thực hiện trong 12 tháng.

Thứ tư, thiết lập cơ chế tự động điều chỉnh bộ tham số thuật toán dựa trên đặc trưng cấu trúc của từng đơn hàng thay vì áp dụng tham số cố định. Chủ thể thực hiện là các kỹ sư vận hành hệ thống thông minh. Mục tiêu nhằm rút ngắn số vòng lặp hội tụ xuống dưới 30.000 chu kỳ, tiết kiệm 40% chi phí tính toán đám mây. Kế hoạch triển khai trong vòng 12 đến 18 tháng.

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

Nhóm học viên cao học, nghiên cứu sinh và giảng viên chuyên ngành Khoa học Máy tính, Toán Ứng dụng: Luận văn cung cấp nền tảng toán học chặt chẽ về chứng minh tính hội tụ của chuỗi Markov trong tối ưu hóa meta-heuristic, phân tích độ phức tạp thuật toán và phương pháp thiết kế đồ thị cấu trúc. Đây là tài liệu tham khảo giá trị cho các công trình nghiên cứu chuyên sâu về tối ưu tổ hợp.

Nhóm kỹ sư công nghệ phần mềm và kiến trúc sư hệ thống điều hành sản xuất: Tìm thấy sơ đồ thuật toán chi tiết, cấu trúc ánh xạ hoán vị thao tác và các công thức cập nhật mùi đã được kiểm chứng. Tài liệu giúp các kỹ sư lập trình trực tiếp các module lập lịch tự động trong các nền tảng ERP hiện đại.

Nhóm quản đốc nhà máy, giám đốc vận hành và chuyên viên điều độ xưởng: Nắm bắt phương pháp luận khoa học để chuyển đổi từ phương thức lập kế hoạch dựa trên kinh nghiệm cảm tính sang điều độ tự động bằng thuật toán, giúp giải quyết bài toán nghẽn cổ chai và giảm chi phí phạt chậm tiến độ từ 15% đến 20% trong thực tế.

Nhóm chuyên gia tư vấn chuyển đổi số và tối ưu hóa chuỗi cung ứng: Sử dụng hệ thống số liệu thực nghiệm từ 10 bộ dữ liệu chuẩn làm cơ sở khoa học để xây dựng báo cáo khả thi, tư vấn đầu tư công nghệ nhà máy thông minh cho các tập đoàn sản xuất quy mô lớn.

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

Thuật toán Hệ kiến đa mức mang lại cải tiến gì nổi bật so với Hệ kiến cực đại - cực tiểu truyền thống? Thuật toán phân tách hai cơ chế cập nhật mùi trực tuyến cho toàn bộ đàn kiến và ngoại tuyến cho cá thể xuất sắc nhất, đồng thời loại bỏ bước bay hơi toàn cục. Nhờ vậy, độ phức tạp tính toán giảm từ bậc hai xuống tuyến tính, giúp tiết kiệm hơn 40% thời gian thực thi trên bài toán 10 máy 10 công việc.

Tại sao tỷ lệ biên mùi 1/2 lại cho hiệu quả tốt nhất trong bài toán lập lịch xưởng sản xuất? Bài toán lập lịch có thông tin dẫn đường biến động liên tục theo từng bước đi. Thiết lập tỷ lệ 1/2 giúp giới hạn biên độ phân hóa vết mùi, ngăn chặn hiện tượng mùi trên các cạnh tụt quá nhanh về mức sàn dẫn đến bế tắc tìm kiếm. Thực nghiệm trên bộ dữ liệu Orb1 cho thấy tỷ lệ 1/2 đạt giá trị tốt nhất là 1340, vượt trội so với mức 1366 của tỷ lệ 1/3.

Vì sao bài toán lập lịch từ 3 máy trở lên không thể giải bằng các thuật toán đa thức cổ điển? Với 2 máy, thuật toán Johnson năm 1954 giải tối ưu trong thời gian đa thức, ví dụ rút ngắn thời gian gia công 5 chi tiết từ 28 xuống 26 đơn vị. Tuy nhiên từ 3 máy trở lên, bài toán thuộc lớp NP-khó với không gian trạng thái bùng nổ lũy thừa, khiến việc tìm nghiệm xấp xỉ trong phạm vi 5/4 nghiệm tối ưu cũng là bất khả thi trong thời gian đa thức.

Quy trình ánh xạ từ hành trình của đàn kiến sang lịch sản xuất thực tế diễn ra như thế nào? Mỗi cá thể kiến di chuyển qua 100 đỉnh thao tác trên đồ thị cấu trúc 101 đỉnh để tạo thành một chuỗi thứ tự. Thuật toán sẽ lần lượt xếp các thao tác này vào các máy tương ứng ngay khi thỏa mãn hai điều kiện: thao tác trước đó của cùng công việc đã hoàn thành và máy gia công đang ở trạng thái rảnh rỗi.

Thuật toán có thể mở rộng cho các dây chuyền sản xuất trên 50 máy công cụ không? Thuật toán hoàn toàn có khả năng mở rộng quy mô lớn khi kết hợp thêm kỹ thuật danh sách ứng cử viên láng giềng gần. Nhờ việc tối giản hóa độ phức tạp của thuật toán đa mức, hệ thống vẫn đảm bảo xuất lịch trình tối ưu trong khoảng vài phút thay vì mất nhiều giờ tính toán.

Kết luận

• Xây dựng thành công mô hình biểu diễn đồ thị cấu trúc với số đỉnh chính xác bằng tích số công việc nhân số máy cộng một, biến bài toán điều độ phức tạp thành bài toán tìm đường đi tối ưu.
• Đề xuất hai quy tắc cập nhật mùi mới mang tính đột phá là Hệ kiến cực đại - cực tiểu trơn và Hệ kiến đa mức, khắc phục triệt để hiện tượng đình trệ tìm kiếm.
• Tối ưu hóa độ phức tạp tính toán của thuật toán về mức tuyến tính theo số kiến, giảm hơn 40% thời gian xử lý so với các thuật toán tiền nhiệm.
• Kiểm chứng thực nghiệm toàn diện trên 10 bộ dữ liệu chuẩn quốc tế Orb1 đến Orb10, công bố thành công 2 công trình khoa học tại hội nghị IEEE RIVF 2006 và PRIMA 2008.
• Cung cấp giải pháp công nghệ khả thi giúp các doanh nghiệp sản xuất gia tăng năng suất từ 15% đến 25% và tối ưu hóa chi phí vận hành.

Luận văn đã đóng góp một bước tiến quan trọng cả về mặt lý thuyết tối ưu hóa toán học lẫn ứng dụng thực tiễn trong cuộc cách mạng sản xuất thông minh. Kế hoạch tiếp theo trong 12 tháng tới tập trung vào việc thương mại hóa thuật toán thành các thư viện phần mềm chuyên dụng và mở rộng sang bài toán lập lịch động theo thời gian thực. Các tổ chức và doanh nghiệp quan tâm có thể khai thác toàn văn công trình nghiên cứu và liên hệ trực tiếp với tác giả để nhận chuyển giao giải pháp điều độ sản xuất tối ưu.

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

MỞ ĐẦU Trƣớc đây, công việc lập kế hoạch sản xuất thƣờng phụ thuộc vào kinh nghiệm của ngƣời phụ trách lập lịch và vấn đề này mất rất nhiều thời gian tính toán trong khi kết quả lại có ảnh hƣởng lớn đến toàn bộ quá trình sản xuất. Ngày nay, quy mô sản xuất ngày càng lớn, số lƣợng ngày càng nhiều, vừa mang tính cạnh tranh cao về chất lƣợng sản phẩm vừa phải đáp ứng đƣợc yêu cầu về thời gian, đồng nghĩa với việc đòi hỏi phải có một lịch sản xuất hợp lý, tối ƣu trên nhiều phƣơng diện. nhằm làm giảm thời gian sản xuất, mang lại hiệu quả kinh tế đã cộng đồng. Do b sản xuất thuộc lớp - nên u trong thời gian đa thức.

Vì vậy kim, tối ƣu (Ant Colony Optimization algorithms) quả này. (Ant Colony Optimization - ACO , .T hơn 20 khi ứng dụng giải ,. Luận văn đi sâu nghiên cứu các phƣơng pháp cập nhật mùi trong các thuật toán ACO sản xuất. văn , dựa trên phân tích toán học các đặc tính hội tụ của vết mùi, chúng tôi đã hai mức để từ đó các.

Ƣu điểm của phƣơng pháp đề xuất kiểm kết quả trên các bộ dữ liệu chuẩn (benchmark data) của 7 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất sản xuất. Các kết quả nghiên cứu đƣợc công bố trong hai báo cáo khoa học ở hội nghị quốc tế IEEE RIVF 2006 và PRIMA 2008 (xem [17], [4]). Ngoài phần kết luận, luận văn đƣợc trình bày nhƣ sau : Chƣơng 1 : Giới thiệu : lịch sử phát triển, ACO, và. Chƣơng 2 : B sản xuất và các phƣơng pháp giải chính Trong chƣơng này, chúng tôi sản xuất chính gi.

Chƣơng 3 : sản xuất T chung để lập lịch sản xuất. (Đồng thời trong chƣơng này chúng tôi trình bày các cải tiến cụ thể trong áp dụng tối ƣu hóa đàn kiến với bài toán lập lịch) Chƣơng 4 lập lịch sản xuất nghiệm và đánh giá. 8 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất CHƢƠNG 1 TỐI ƢU HÓA ĐÀN KIẾN VÀ ỨNG DỤNG Tối ƣu hóa đàn kiến (Ant Colony Optimization - ACO) là cách tiếp cận meta- heuristic tƣơng đối mới (xem [5], [6], [9], [10]) đƣợc đề xuất bởi Dorigo vào năm 1991 mô phỏng hành vi tìm đƣờng -khó. Trên đƣờng đi của mình các con kiến thực để lại một vết hóa chất đƣợc gọi là vết mùi (pheromone trail), đặc điểm sinh hóa học củ chọn để đi, nhờ cách giao tiếp mang tính gián tiếp và cộng đồng (xem [5].

Theo ý tƣởng này, các thuật toán ACO sử dụng thông tin heuristic kết hợp thông tin học tăng cƣờng (xem [6]) qua các vết mùi của các con kiến nhân tạo (artificial ant) để giải các bài toán tối ƣu tổ hợp khó bằng cách đƣa về bài toán tìm đƣờng đi tối ƣu trên đồ thị cấu trúc tƣơng ứng đƣợc xây dựng từ đặc điểm của t (xem [7] (Ant System - AS) (Travelling Salesman Problem - TSP (xem [9]. , (Marie Curie Excellence Award) trao hai năm 9 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất 6 (ANT’ 98, ANT’ 2000, ANTS 2002, ANTS 2004, ANTS 2006, ANTS 2008) - (xem http://iridia. Nhƣ vậy, với đồ thị không đối xứng sẽ có (n 1)! đƣờng đi chấp nhận đƣợc và (n 1)! với đồ thị đối xứng. Với n lớn thì ta không thể tìm hết các đƣờng đi và chỉ 2 có thể tìm đƣợc một lời giải đủ tốt bằng các phƣơng pháp tìm kiếm địa phƣơng, tìm kiếm heuristic, tính toán tiến hóa h.

10 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất 1. Xây dựng lời giải [ ij (t )] [ ij ] j Ni k Pij k (t ) [ il (t )] [ il ] (1.1) l Ni k 0 , ij 1 0 ij d ij 0 ), N i k. 11 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất Cập nhật mùi (0,1) : m k ij (t 1) (1 ) ij (t ) ij (t ) (1. (reinforcement learning 12 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất.

: s sau : arg max j N k { ij (t ) ij } q0 s i (1.4) j 13 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất [0 0 [0 1. MMAS (xem [22] g - i - (stagnation 14 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất ( max ( min -MIN). min max 0 max ). Trong hệ này, thủ tục xây dựng lời giải thực hiện nhƣ trong AS (đƣợc thực nghiệm với tham số : ij (1 ) ij ij (1.8) max{ min (1 ) ij ,0} 15 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất min min .2 (ACO metaheuristic (ACO Algorithms.

: Xét bài toán cực tiểu hóa (S , f , ) trong đó S là tập hợp hữu hạn trạng thái, f là hàm mục tiêu xác định trên S còn là các ràng buộc để xác định S qua các thành phần của tập hữu hạn C và các liên kết của tập này. Các tập S, C, và có các đặc tính sau : C = {c1, c2, …, cn} là tập hữu hạn gồm n thành phần. Ta ký hiệu X là tập các dãy trong C có độ dài không quá h : X={<u0, …, uk> | uk C i k h } Tồn tại tập con X* của X và ánh xạ từ X* lên S sao cho 1 ( s) không rỗng với mọi s S và là tập xây dựng đƣợc từ tập con C0 của C và theo đặc tính 3. Từ C0 mở rộng đƣợc thành X* theo thủ tục tuần tự : x0 u0 là mở rộng đƣợc với u1 C 0 ., u k là mở rộng đƣợc thì tồn tại từ xác định đƣợc tập con J(xk) của C sao cho với mọi uk+1 J(xk) thì xk 1 u 0 , u1 ,., u k 1 là mở rộng đƣợc và x k X * khi J(xk) là rỗng.

Với mọi u 0 C 0 , thủ tục mở rộng nêu trên xây dựng đƣợc mọi phần tử của X*. Không giảm tổng quả ta giả thiết rằng có tƣơng ứng giữa các phần tử trong X * đi đƣợc mở rộng từ mỗi u0 trong C 0. 16 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất , C0. Với bài toán tổng quát trên, về lý thuyết ta có thể áp dụng thủ tục mở rộng để xây dựng X* và chọn lời giải tốt nhất bằng phƣơng pháp vét cạn nhƣng trên thực tế, do sự bùng nổ tổ hợp thì với số phần tử n của C lớn thì không thực hiện đƣợc và bài toán đƣợc xét thuộc dạng NP-khó.

Thông thƣờng ta sẽ có các phƣơng pháp heuristic để tìm lời giải đủ tốt cho bài toán. Các thuật toán ACO kết hợp thông tin heuristic này với phƣơng pháp học tăng cƣờng nhờ mô phỏng hành vi của đàn kiến để tìm lời giải tốt hơn. Giả sử với mỗi cạnh (i, j) C có trọng số heuristic hi,j để định hƣớng chọn thành phần mở rộng là j khi thành phần cuối cùng của x k là i theo thủ tục nêu trên (hi,j>0 (i,j)). Đàn kiến m con sẽ xây dựng lời giải trên đồ thị đầy đủ có trọng số G = (V, E, H, ) trong đó V là tập đỉnh tƣơng ứng với tập thành phần C ở trên, E là tập các cạnh, H là vector các trọng số heuristic của cạnh tƣơng ứng còn là vector vết mùi tích lũy đƣợc ban đầu với khởi tạo bằng 0.

Đồ thị G đƣợc gọi là đồ thị cấu trúc của bài toán. Với điều kiện dừng đã chọn (giả sử nhƣ là với số lần lặp N c xác định trƣớc) các thuật toán đƣợc mô tả hình thức nhƣ sau : 17 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất Procedure Begin while ) do begin ) end; End; Hình 1 : Lƣợc đồ thuật toán ACO Sau khi khởi tạo các tham số và cƣờng độ mùi ban đầu, các con kiến thực hiện thủ tục xây dựng lời giải. Trong mỗi lần lặp t, mỗi con kiến chọn ngẫu nhiên một đỉnh xuất phát trong C0 và kết hợp thông tin heuristic với thông tin mùi để xây dựng lời giải ngẫu nhiên theo thủ tục mở rộng tuần tự nêu ở phần trƣớc với xác suất chọn đỉnh tiếp theo nhƣ sau : Quy tắc chuyển trạng thái : Giả sử con kiến s đã xây dựng xk u 0 ,., u , nó sẽ chọn đỉnh y thuộc J(xk) để xk 1 u 0 ,., u, y với xác suất : u, y hu , y y J ( xk ) P( y | , xk ) u, j hu , j (1. Để tiện trình bày, về sau ta sẽ xem x(l) và s(l) nhƣ nhau đều là thể hiện của lời giải chấp nhận đƣợc và không phân biệt X* với S.

Ký hiệu w(t) là trạng thái tốt nhất các con kiến tìm đƣợc cho tới lúc 18 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất này và wi(t) là lời giải tốt nhất trong bƣớc lặp, ta sẽ quy ƣớc chọn w(t) = w(t-1) trong trƣờng hợp wi(t)=w(t-1)và quan tâm đến lời giải gần đúng w(t) này. Trong lý thuyết để tiện cho việc chứng minh, các tác giả đã chọn w(t) còn trong thực nghiệm wi(t) lại tỏ ra hiệu quả hơn do việc này tăng cƣờng tính khám phá của thuật toán. Do giả thiết (3.iii) của bài toán và để tiện cho trình bày, về sau ta không phân biệt mỗi x X * với trạng thái s S tƣơng ứng. Giả sử g là một hàm giá trị thực xác định trên S sao cho 0 g (s) , s S và g ( s) g ( s' ) nếu f (s) f (s' ) , khi đó ở mỗi bƣớc lặp cƣờng độ vết mùi sẽ thay đổi theo một trong hai quy tắc thƣờng dùng sau đây, đƣợc gọi là các quy tắc cập nhật mùi hai mức.

Quy tắc ACS : Quy tắc này phỏng theo quy tắc cập nhật mùi của thuật toán hệ đàn kiến ACS bao gồm cả cập nhật địa phƣơng và cập nhật toàn cục. Cập nhật mùi địa phương : nếu con kiến l thăm cạnh (i, j), tức là (i, j) s(l) thì cạnh này sẽ thay đổi mùi theo công thức : ij (1 ) ij 1 (1.1) Cập nhật mùi toàn cục : Cập nhật mùi toàn cục chỉ áp dụng cho các cạnh thuộc w(t) nhƣ sau : ij (1 ) ij g ( w(t )) (i, j ) w(t ) (1.2) Quy tắc MMAS : Quy tắc này thực hiện theo cách cập nhật mùi của thuật toán MMAS, sau khi mỗi con kiến đề xây dựng xong lời giải ở mỗi bƣớc lặp, vết mùi đƣợc thay đổi theo công thức sau : ij (1 ) ij ij (1.11) 19 LUAN VAN CHAT LUONG download : add [e-mail] sản xuất L 1 ( w(t )) (i,j) w(t) ij (1.1) max{ min (1 ) ij ,0} , trong [15 .