Tài liệu Luận văn tiếp cận thuật toán meta heuristic giải bài toán tối ưu hóa quá trình sản xuất​

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- PHẠM QUỐC PHƯƠNG TIẾP CẬN THUẬT TOÁN META-HEURISTIC GIẢI BÀI TOÁN TỐI ƯU HÓA QUÁ TRÌNH SẢN XUẤT LUẬN VĂN THẠC SĨ Chuyên ngành : Kỹ thuật Cơ điện tử Mã số ngành: 60520114 TP. HỒ CHÍ MINH, tháng 11 năm 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- PHẠM QUỐC PHƯƠNG TIẾP CẬN THUẬT TOÁN META-HEURISTIC GIẢI BÀI TOÁN TỐI ƯU HÓA QUÁ TRÌNH SẢN XUẤT LUẬN VĂN THẠC SĨ Chuyên ngành : Kỹ thuật Cơ điện tử Mã số ngành: 60520114 CÁN BỘ HƯỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN THANH PHƯƠNG TP. HỒ CHÍ MINH, tháng 11 năm 2017 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM Cán bộ hướng dẫn khoa học : PGS. TS. Nguyễn Thanh Phương (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Công nghệ TP. HCM ngày 12 tháng 11 năm 2017 Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm: (Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ Luận văn Thạc sĩ) TT 1 2 3 4 5 Họ và tên TS. Nguyễn Hùng TS. Ngô Hà Quang Thịnh TS. Nguyễn Hoài Nhân TS. Võ Hoàng Duy TS. Võ Đình Tùng Chức danh Hội đồng Chủ tịch Phản biện 1 Phản biện 2 Ủy viên Ủy viên, Thư ký Xác nhận của Chủ tịch Hội đồng đánh giá Luận văn sau khi Luận văn đã được sửa chữa (nếu có). Chủ tịch Hội đồng đánh giá LV TRƯỜNG ĐH CÔNG NGHỆ TP. HCM VIỆN ĐÀO TẠO SAU ĐẠI HỌC CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc TP. HCM, ngày..… tháng….. năm 2017 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Phạm Quốc Phương........................................Giới tính: Nam Ngày, tháng, năm sinh: 05/01/1980............................................Nơi sinh: Ninh Bình Chuyên ngành: Kỹ thuật Cơ điện tử...........................................MSHV:1441840008 I- Tên đề tài: Tiếp cận thuật toán meta-heuristic giải bài toán tối ưu hóa quá trình sản xuất. II- Nhiệm vụ và nội dung: Luận văn nghiên cứu về vấn đề tối ưu áp dụng trong bố trí sản xuất. Để tiếp bước đến nền công nghiệp 4.0, sắp xếp lịch trong sản xuất/công tác nhằm giảm quá trình “đợi” nhau trong các công đoạn và tận dụng được nhiều tài nguyên phục vụ sản xuất. Bài toán trong luận văn nghiên cứu cụ thể là bài toán về CF (cell formation). Theo đó, việc hình thành các ô (cell) là hoán vị các công việc và các “máy” thực hiện. Về phương pháp, luận văn nghiên cứu về giải pháp heuristic (gần đúng). Giải pháp gần đúng theo phương pháp di truyền sẽ góp phần vào tốc độ tính toán. Từ đó, những vấn đề được luận văn nêu lên gồm: - Phát biểu bài toán CFP. - Cơ sở lý luận về heuristic - Giải pháp, kỹ thuật giải bài toán CFP - Tiếp cận về meta-heuristic và hiện thực thuật toán. III- Ngày giao nhiệm vụ: 23/01/2016 IV- Ngày hoàn thành nhiệm vụ: ............................................................................ V- Cán bộ hướng dẫn: PGS. TS. Nguyễn Thanh Phương .................................................................................................................................. .................................................................................................................................. CÁN BỘ HƯỚNG DẪN (Họ tên và chữ ký) PGS.TS. Nguyễn Thanh Phương KHOA QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã được cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Học viên thực hiện Luận văn (Ký và ghi rõ họ tên) Phạm Quốc Phương ii LỜI CÁM ƠN Trong thời gian học tập, nghiên cứu và thực hiện luận văn tốt nghiệp, tôi đã luôn nhận được sự giúp đỡ vô cùng to lớn của Quý Thầy, Cô trường Đại học Công nghệ Thành phố Hồ Chí Minh, cơ quan, bạn bè và gia đình. Tôi xin tỏ lòng biết ơn đến:  Thầy PGS.TS. Nguyễn Thanh Phương đã tận tình hướng dẫn, giúp đỡ, định hướng tôi trong quá trình nghiên cứu và thực hiện luận văn tốt nghiệp;  Quý Thầy, Quý Cô giảng dạy trong khóa của Trường Đại học Công nghệ Thành phố Hồ Chí Minh đã tận tình giảng dạy và giúp đỡ tôi trong suốt thời gian học tập và nghiên cứu;  Viện Đào tạo Sau Đại học - trường Đại học Công nghệ Thành phố Hồ Chí Minh đã có kế hoạch và tạo điều kiện tốt để tôi được tham gia học tập và nghiên cứu;  Lãnh đạo Khoa và Bộ môn Trường Đại học Công nghệ Thành phố Hồ Chí Minh đã tạo điều kiện thuận lợi cho tôi trong suốt thời gian học tập, nghiên cứu, và làm việc  Ban giám đốc, lãnh đạo Sở Khoa học và Công nghệ TP.HCM đã tạo điều kiện tốt nhất về vật chất và tinh thần cho tôi nghiên cứu và học tập;  Và đặc biệt, gia đình, bạn bè, những người thân thiết đã ủng hộ, giúp đỡ, khuyến khích, dành mọi điều kiện để tôi học tập và nghiên cứu. Một lần nữa, tôi xin trân trọng biết ơn! Phạm Quốc Phương iii TÓM TẮT Luận văn nghiên cứu về vấn đề tối ưu áp dụng trong bố trí sản xuất. Để tiếp bước đến nền công nghiệp 4.0, sắp xếp lịch trong sản xuất/công tác nhằm giảm quá trình “đợi” nhau trong các công đoạn và tận dụng được nhiều tài nguyên phục vụ sản xuất. Bài toán trong luận văn nghiên cứu cụ thể là bài toán về CF (cell formation). Theo đó, việc hình thành các ô (cell) là hoán vị các công việc và các “máy” thực hiện. Về phương pháp, luận văn nghiên cứu về giải pháp heuristic (gần đúng). Giải pháp gần đúng theo phương pháp di truyền sẽ góp phần vào tốc độ tính toán. Từ đó, những vấn đề được luận văn nêu lên gồm: - Phát biểu bài toán CFP. - Cơ sở lý luận về heuristic - Giải pháp, kỹ thuật giải bài toán CFP - Tiếp cận về meta-heuristic và hiện thực thuật toán. iv ABSTRACT Thesis on the optimization problem applied in production scheduling. To get into the 4.0th of industrial generation, schedule your production / work schedules to reduce "waiting waste" processes in the process and utilize the resources available for production. The problem in this particular research treatise is the CF (cell formation) problem. Accordingly, the formation of cells is the permutation of the work and the "machines" performed. On the method, the dissertation study on the heuristic solution. The approximation solution by genetic method will contribute to computational speed. Since then, the issues solved by this thesis include: - Stating of the CFP problem. - Overview the heuristics - Checking the solutions and techniques for solving CFP problem. - Meta-heuristic approach and code implementation for CFP. v MỤC LỤC TRANG PHỤ BÌA LỜI CAM ĐOAN ................................................................................................... i LỜI CÁM ƠN ........................................................................................................ ii TÓM TẮT .............................................................................................................iii ABSTRACT .......................................................................................................... iv MỤC LỤC.............................................................................................................. v DANH MỤC CÁC TỪ VIẾT TẮT ..................................................................... vii DANH MỤC CÁC BẢNG .................................................................................. viii DANH MỤC CÁC HÌNH ..................................................................................... ix CHƯƠNG 1: MỞ ĐẦU ......................................................................................... 1 1.1. Đặt vấn đề ..................................................................................................... 1 1.2. Mục tiêu nghiên cứu...................................................................................... 3 1.2.1 Mục tiêu tổng quát ................................................................................... 3 1.2.2 Mục tiêu cụ thể ........................................................................................ 3 1.3. Phạm vi và giới hạn của luận văn .................................................................. 3 1.4. Nội dung nghiên cứu ..................................................................................... 3 1.5. Phương pháp nghiên cứu ............................................................................... 4 1.5.1 Mô hình bài toán hình thành tế bào (CFP) ............................................... 4 1.5.2. Phương pháp........................................................................................... 4 1.6. Những đóng góp của luận văn ....................................................................... 5 1.7. Cấu trúc của luận văn .................................................................................... 5 CHƯƠNG 2: TỔNG QUAN VÀ CÁC PHƯƠNG PHÁP HEURISTIC ............. 6 2.1. Tổng quan về bài toán tối ưu trong sản xuất và bàn toán CF.......................... 6 2.1.1 Tổng quan về bài toán tối ưu trong sản xuất............................................. 6 2.2.2 Giới thiệu bài toán cell formation (CF) .................................................... 9 2.2. Tổng quan về heuristic và tìm kiếm cục bộ ................................................. 20 2.2.1 Tìm kiếm heuristic................................................................................. 20 2.2.2 Tìm kiếm meta-heuristic ........................................................................ 21 vi 2.2.3 Tìm kiếm cục bộ .................................................................................... 22 2.4. Các thuật toán giải gần đúng CFP ............................................................... 24 2.4.1 Xây dựng lược đồ mã hóa ...................................................................... 27 2.4.2 Khởi tạo quần thể .................................................................................. 28 2.4.3 Mức độ tuân theo độ phù hợp của mỗi thành phần trong quần thể.......... 29 2.4.4 Luật chọn............................................................................................... 29 2.4.5 Phép toán di truyền ................................................................................ 29 2.4.6 Các giá trị tham số (để điều khiển nhất định) ......................................... 31 CHƯƠNG 3 CÀI ĐẶT VÀ THỬ NGHIỆM ...................................................... 33 3.1. Nghiên cứu lựa chọn dữ liệu nhập ............................................................... 33 3.2. Giải mô hình và xem xét thử nghiệm các nghiệm mô hình .......................... 35 3.3. Thiết lập các điều kiện trên nghiệm ............................................................. 40 3.4. Xây dựng chương trình bằng ngôn ngữ lập trình ......................................... 40 CHƯƠNG 4 MÔ PHỎNG VÀ KẾT LUẬN ....................................................... 47 4.1. Mô phỏng thực tế ........................................................................................ 47 4.1.1 Xây dựng đồ thị mức độ phù hợp nghiệm .............................................. 47 4.1.2 Xây dựng đồ thị mô tả dữ liệu nhập và kết quả kết xuất thực thi ............ 48 4.1.3 Xây dựng đoạn lệnh triệu gọi thực thi .................................................... 49 4.2. Kết quả mô phỏng ....................................................................................... 50 4.2.1 Thử nghiệm với bộ dữ liệu Boctor ......................................................... 50 4.2.2 Thử nghiệm với bộ dữ liệu Kusiak......................................................... 54 4.2.3 Thử nghiệm với bộ dữ liệu phát sinh ngẫu nhiên: .................................. 61 4.3. Phân tích số liệu mô phỏng ......................................................................... 82 4.4. Kết luận về đề tài ........................................................................................ 82 4.5. Kiến nghị những hướng nghiên cứu tiếp theo .............................................. 83 TÀI LIỆU THAM KHẢO ................................................................................... 84 vii DANH MỤC CÁC TỪ VIẾT TẮT ANN Artificial Neural Network – Mạng nơ-ron nhân tạo BnB Phương pháp nhánh-cận CAD Computer Aided Design – Thiết kế có sử dụng máy tính hỗ trợ CFP Cell Formation Problem – Bài toán hình thành tế bào CM Cellular manufacturing - Sản xuất tế bào ERP Enterprise Resource Planning - Hoạch định tài nguyên doanh nghiệp GA Genetic Algorithms - Thuật toán di truyền LP Linear Programming – Quy hoạch tuyến tính MIP Mixed Integer Programming - Quy hoạch nguyên hỗn hợp NP Nondeterministic polynomial time - Độ phức tạp phi đa thức TQM Total Quality Management – Quản lý chất lượng toàn diện viii DANH MỤC CÁC BẢNG Bảng 2.1: Những nghiên cứu về bài toán CFP ................................................... 13 Bảng 2.2: Kích thước dữ liệu thực nghiệm......................................................... 14 Bảng 2.3: So sánh về hiệu suất tối ưu và tốc độ phương pháp của Iraj Mahdavi .............................................................................................................................. 15 Bảng 2.4: Các dạng tìm kiếm cục bộ .................................................................. 23 Bảng 2.5. Bộ giá trị tham số ứng dụng thuật toán di truyền trong các thuật toán....................................................................................................................... 31 Bảng 3.1. Các thủ tục cần xây dựng cho chương trình ...................................... 41 ix DANH MỤC CÁC HÌNH Hình 2.1: Một số loại máy xử lý công việc được J.Blazewicz (1983) phân loại ... 7 Sơ đồ 2.1: Các phương pháp tổng quát giải các mô hình và bài toán tối ưu ...... 9 Hình 2.2: Minh họa việc nhóm các tiến trình ..................................................... 11 Hình 2.3: Minh họa về một chuỗi “nhiễm sắc thể” ............................................ 25 Hình 2.4: Lược đồ công việc khung tổng quát cho thuật toán di truyền .......... 26 Hình 2.5: Minh họa một phép “lai” crossover ................................................... 27 Hình 2.6: Minh họa về phép toán lai đơn giản (simple crossover) .................... 30 Hình 2.7: Minh họa phép toán lai đồng dạng (uniform crossover) ................... 30 Hình 3.1: Lưu đồ thuật toán bài toán CF theo Araj Mahdavi (2009) [1] ......... 35 Hình 3.2: Chi tiết cài đặt ..................................................................................... 36 Hình 4.1: Dữ liệu Boctor, kích thước 7x11 ......................................................... 50 Hình 4.2: Kết quả bố trí được thể hiện với dữ liệu Boctor (K=2) ..................... 51 Hình 4.3: Thuật toán thực thi trong 100 bước lặp (K=2), trục tung là hệ số Eff, trục hoành là số lần lặp ....................................................................................... 51 Hình 4.4: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu Boctor (K=2), giá trị Eff thấp. .......................................................................................................... 52 Hình 4.5: Kết quả bố trí được thể hiện với dữ liệu Boctor ............................... 53 Hình 4.6: Thuật toán thực thi trong 100 bước lặp, trục tung là hệ số Eff, trục hoành là số lần lặp ............................................................................................... 53 Hình 4.7: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu Boctor, giá trị hội tụ khá nhanh từ các vòng lặp. ............................................................................. 54 Hình 4.8: Dữ liệu đầu vào Kusiak....................................................................... 55 Hình 4.9: Kết quả bố trí được thể hiện với dữ liệu Kusiak (K=2)..................... 55 Hình 4.10: Thuật toán thực thi trong 100 bước lặp (K=2), trục tung là giá trị tối ưu Eff, trục hoành là số bước lặp .................................................................. 56 Hình 4.11: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu Kusiak (K=2)... 56 Hình 4.12: Kết quả bố trí được thể hiện với dữ liệu Kusiak (K=4) ................... 57 x Hình 4.13: Thuật toán thực thi trong 100 bước lặp (K=4), trục tung là giá trị tối ưu Eff, trục hoành là số bước lặp .................................................................. 57 Hình 4.14: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu Kusiak (K=4)... 58 Hình 4.15: Kết quả bố trí được thể hiện với dữ liệu Kusiak (K=5) ................... 59 Hình 4.16: Thuật toán thực thi trong 100 bước lặp (K=5), trục tung là giá trị tối ưu Eff, trục hoành là số bước lặp .................................................................. 59 Hình 4.17: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu Kusiak (K=5)... 60 Hình 4.18: Ma trận thử nghiệm 20x23 tự phát sinh ngẫu nhiên ....................... 61 Hình 4.19: Với số nhóm là 3, trục tung là hệ số Eff, trục hoành là số lần lặp và hình dưới bên phải là bố trí 3 nhóm ................................................................... 61 Hình 4.20: Với số nhóm là 6, trục tung là hệ số Eff, trục hoành là số lần lặp và hình dưới bên phải là bố trí 6 nhóm ................................................................... 62 Hình 4.21: Dữ liệu phát sinh từ chương trình .................................................... 66 Hình 4.22: Dữ liệu được chuyển đổi cột-dòng ngẫu nhiên................................. 68 Hình 4.23: Dữ liệu được chuyển đổi cột-dòng ngẫu nhiên “dulieu” ................. 68 Hình 4.24: Kết quả bố trí được thể hiện với dữ liệu ngẫu nhiên “dulieu” (K=2) .............................................................................................................................. 69 Hình 4.25: Thuật toán thực thi trong 100 bước lặp (K=2), trục tung là hệ số Eff, trục hoành là số lần lặp ................................................................................ 69 Hình 4.26: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu ngẫu nhiên “dulieu” (K=2), hệ số ở mức thập 0.42 ............................................................... 70 Hình 4.27: Kết quả bố trí được thể hiện với dữ liệu ngẫu nhiên “dulieu” (K=5) .............................................................................................................................. 71 Hình 4.28: Thuật toán thực thi trong 100 bước lặp (K=5), trục tung là hệ số Eff, trục hoành là số lần lặp ................................................................................ 71 Hình 4.29: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu ngẫu nhiên “dulieu” (K=5), hệ số Eff ở mức cao 0.93 ........................................................... 72 Hình 4.30: Kết quả bố trí được thể hiện với dữ liệu ngẫu nhiên “dulieu” (K=>6) .................................................................................................................. 73 xi Hình 4.31: Thuật toán thực thi trong 100 bước lặp (K>=6), trục tung là hệ số Eff, trục hoành là số lần lặp ................................................................................ 73 Hình 4.32: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu ngẫu nhiên “dulieu” (K>=6), hệ số ở mức cao 0.8 ................................................................. 74 Hình 4.33: Dữ liệu được chuyển đổi cột-dòng ngẫu nhiên “dulieu1” ............... 75 Hình 4.34: Kết quả bố trí được thể hiện với dữ liệu ngẫu nhiên “dulieu1” (K=2) .................................................................................................................... 75 Hình 4.35: Thuật toán thực thi trong 100 bước lặp (K=2), trục tung là hệ số Eff, trục hoành là số lần lặp ................................................................................ 76 Hình 4.36: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu ngẫu nhiên “dulieu1” (K=2), hệ số Eff ởmức trung bình 0.5 ................................................ 77 Hình 4.37: Kết quả bố trí được thể hiện với dữ liệu ngẫu nhiên “dulieu1” (K=4) .................................................................................................................... 78 Hình 4.38: Thuật toán thực thi trong 100 bước lặp (K=4), trục tung là hệ số Eff, trục hoành là số lần lặp ................................................................................ 78 Hình 4.39: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu ngẫu nhiên “dulieu1” (K=4), hệ số Eff ở mức rất cao 0.85. .................................................. 79 Hình 4.40: Kết quả bố trí được thể hiện với dữ liệu ngẫu nhiên “dulieu1” (K=5) .................................................................................................................... 80 Hình 4.41: Thuật toán thực thi trong 100 bước lặp (K=4), trục tung là hệ số Eff, trục hoành là số lần lặp ................................................................................ 80 Hình 4.42: Giá trị tối ưu của nghiệm trong mô phỏng dữ liệu ngẫu nhiên “dulieu1” (K>=5), hệ số phù hợp ở mức 0.9 là rất cao ...................................... 81 1 CHƯƠNG 1: MỞ ĐẦU 1.1. Đặt vấn đề Vấn đề tối ưu trong sản xuất ngày nay là vấn đề sống còn của một doanh nghiệp do tính cạnh tranh, nguồn lực có hạn, thời gian hoàn thành sản phẩm hay dịch vụ phải nhanh chóng để đáp ứng kịp nhu cầu của khách hàng. Ngược dòng lịch sử, ngành công nghiệp đã trải qua 3 giai đoạn tương ứng với 3 thời kì công nghệ, đặc biệt là sự can thiệp của công nghệ thông tin. Đó là giai đoạn tập trung vào chi phí (cost focus) kéo dài từ những năm của thế kỷ thứ 18 đến những năm 1980. Trong khoảng thời gian dài này, các định hướng trong sản xuất được ghi nhận thông qua những nghiên cứu định hướng như: công nhân chuyên nghiệp (labor specialization của Smith và Babbage), các thành phần sản xuất được chuẩn hóa thành các sản phẩm (standardized parts của Whitney). Tiếp đó từ những năm 1880 đến năm 1910, hàng loạt các lí thuyết về quản lý sản xuất được hình thành như: Gantt Charts (Gantt), Motion&Time Studies, Process Analysis, lý thuyết hàng đợi (của Erlang)… Tiếp đó, kỷ nguyên sản xuất lượng hàng hóa cực lớn được cho là bắt đầu từ năm 1910 đến năm 1980. Khi đó, nhiều công cụ toán học được phát triển để đáp ứng với việc tối ưu trong sản xuất như: quy hoạch tuyến tính (của Dantzig), phân tích mẫu thống kê (của ông Shewhart),… Giai đoạn từ năm 1980 đến năm 1995 được xem là giai đoạn tập trung vào chất lượng (quality focus), nhiều giải pháp được công nghệ thông tin hóa như CAD (computer aided design), TQM (total quality management),… Và cuối cùng là giai đoạn từ năm 1995 đến nay được xem là giai đoạn tập trung vào khách hàng (customization focus). Tính toàn cầu hóa, internet, các công cụ hoạch định tài nguyên doanh nghiệp (ERP) và đặc biệt là các xu hướng lập lịch quản lý tối ưu được đề ra nhằm giải quyết vấn đề mâu thuẫn giữa nguồn lực bị giới hạn và số công việc hoàn thành. Trong đó, đối với sản xuất công nghiệp, chẳng hạn công nghệ sản xuất vi mạch, nhiều công đoạn hay thành phần/linh kiện có sự tương đồng cao trong thiết kế hay trong quy trình. Các công đoạn có sự tương đồng cao như thế thường được gom nhóm để tận dụng tối đa công suất của máy móc nhằm cực đại hóa hiệu quả tổng thể 2 của hệ thống sản xuất. Chi tiết hơn, xét một ví dụ khác, một robot thông minh được chế tạo để giải quyết các công việc giả định trong đường hầm. Khi làm việc thực tế, mỗi bộ phận của robot có thể làm số nhóm công việc nhiều nhất có thể. Vấn đề là làm thế nào để robot có thể làm cùng lúc. Một cách hình thức, bài toán trên về điều khiển được phát biểu như sau: “Hệ thống sản suất gồm m máy, sản xuất sản phẩm gồm n linh kiện ghép. Bài toán đặt ra là tìm một giải pháp gồm K nhóm sao cho sự tương tác giữa các máy trong cùng nhóm và các linh kiện do các máy đó sản xuất ra là tối đa trong khi sự tương tác với các máy trong các nhóm khác là tối thiểu”. Theo đó, lớp bài toán nghiên cứu về điều khiển (operations research) là nền tảng của các hệ thống, đặc biệt ngày nay các hệ thống cơ điện tử. Thật vậy, các nghiên cứu sẽ giúp các hệ thống thực thi tốt tác vụ, giảm thời gian thực thi và đồng thời tiết kiệm năng lượng,… Trên lý thuyết, nhiều giải pháp được nêu ra dưới dạng các mô hình toán học. Tuy nhiên, trên thực tế, tùy thuộc vào môi trường vận hành, hiện thực các mô hình cần được xem xét, so sánh, đánh giá phân tích lựa chọn phù hợp. Chi tiết hơn, đối với bài toán trình bày trong phần giới thiệu có thể được hình thức hóa về bài toán nổi tiếng của quy hoạch nguyên, bài toán Hình thành Tế bào – Cell Formation Problem, viết tắt là CFP. Trong CFP, mỗi nhóm máy-sản phẩm được gọi là một Cell (tế bào). Về mặt lý luận, đây là bài toán khó và chưa có phương pháp giải tuyệt đối. Về mặt thực tiễn, CFP có thể được áp dụng trong các hệ thống tự động quản lý sản xuất, chẳng hạn như trong thiết kế kiến trúc các chip máy tính hay trong tự động hóa cho các hệ thống tính toán song song. Với các bài toán như thế, CFP được cho là thích hợp để hoàn thành việc phân rã các bộ xử lý và các đơn vị dữ liệu vào một số tế bào xác định trước. Trong luận văn này sẽ trả lời các câu hỏi khoa học và thực tiễn sau: - Biểu diễn lại CFP dưới dạng bài toán tối ưu? - Làm sao để giải bài toán tối ưu CFP? - Áp dụng trong 1 bài toán thực tế đơn giản? Một số giả thuyết nghiên cứu được đặt ra như sau: 3 - CFP có thể được giải bằng các kỹ thuật heuristic. - Tiếp cận meta-heuristic có thể cho kết quả tốt hơn. Đó là lý do để chọn đề tài “Tiếp cận thuật toán meta-heuristic giải bài toán tối ưu hóa quá trình sản xuất”. 1.2. Mục tiêu nghiên cứu 1.2.1 Mục tiêu tổng quát Mục đích của nghiên cứu này là phát triển các thủ tục máy tính hiệu quả giải CFP và xây dựng bài toán minh họa quản lý tự động quy trình sản xuất. 1.2.2 Mục tiêu cụ thể Đề tài nghiên cứu hướng đến các mục tiêu cụ thể như sau: - Nghiên cứu các giải thuật heuristic. - Nghiên cứu một thuật giải phục vụ bài toán quản lý tự động quy trình sản xuất. - Thử nghiệm giải CFP với ràng buộc K  m  n  100 trong thời gian tối đa 60 phút. 1.3. Phạm vi và giới hạn của luận văn Đề tài giới hạn nghiên cứu: số máy (m), số linh kiện (n), và số tế bào (K) của CFP được xác định trước và thỏa K  m  n  100. Giả sử thêm là thời gian giải không quá 1 giờ. 1.4. Nội dung nghiên cứu Luận văn nghiên cứu các nội dung sau:  Vấn đề 1: Mô hình hóa CFP dưới dạng bài toán tối ưu.  Vấn đề 2: Nghiên cứu các vấn đề liên quan đến CFP như sau: - Kỹ thuật phân tích gom cụm nhằm nhận biết cấu trúc trong một tập dữ liệu. - Phân hoạch Graph với graph hay một mạng đại diện được sử dụng để xây dựng CFP. - Các phương pháp quy hoạch toán học đưa CFP về bài toán quy hoạch nguyên phi tuyến hoặc tuyến tính và giải. 4 - Các phương pháp Heuristics như mô phỏng (SA – simulated annealing), tìm kiếm Tabu (TS - Tabu Search), thuật toán di truyền (GA – genetic algorithm), tối ưu cục bộ (PSO - ), mạng nơron (ANN – artificial neural network), tối ưu hóa ngặt (extremal optimization),… 1.5. Phương pháp nghiên cứu 1.5.1 Mô hình bài toán hình thành tế bào (CFP) Bài toán được mô hình như sau: Gọi I: tập m máy, i = 1, 2,…, m J: tập n linh kiện, j = 1, 2,…, n K: số tế bào (nhóm), k = 1, 2,…, K Ck  I: nhóm các máy, k = 1, 2,…, K Fk  J: họ các linh kiện, k = 1, 2,…, K (Ck, Fk): tế bào, k = 1, 2,…, K (C, F) = {(C1, F1),…, (Ck, Fk)}: lời giải/giải pháp cho CFP A = [aij]: ma-trận biểu diễn quan hệ máy và linh kiện, trong đó - a ij = 1: máy i có thể dùng sản xuất linh kiện j - a ij = 0: ngược lại Đặt: Eff = (a – a1Out) / (a + a0In) (công thức 1) Đây là hệ số do Sarker và Khan (1990) đề xuất. Trong đó, a: số số 1 nằm trong ma trận kề. a1Out: số số 1 nằm ngoài tế bào. a0In: số số 0 nằm trong các tế bào trên đường chéo. Hàm mục tiêu: cực đại hóa giá trị Eff. 1.5.2. Phương pháp Bài toán tối trên ưu được giải bằng các kỹ thuật heuristic và/hoặc quy hoạch toán học/đồ thị.