Luận văn thạc sĩ: Nghiên cứu giải thuật di truyền cho bài toán điều độ job shop

Nghiên cứu ứng dụng giải thuật di truyền trong bài toán điều độ job shop, mang lại giải pháp tối ưu cho quản lý sản xuất trong kỹ thuật công nghiệp.

• Tác giả: Đinh Ngọc Bảo
• Người hướng dẫn: PGS.TS Đỗ Ngọc Hiền
• Trường học: Đại học Bách Khoa
• Chuyên ngành: Kỹ thuật Hệ thống Công nghiệp
• Đề tài: Nghiên Cứu Giải Thuật Di Truyền Trong Bài Toán Điều Độ Job Shop
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2021
• Địa điểm: TP.HCM

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN THẠC SĨ
• LỜI CAM ĐOAN
• DANH SÁCH HÌNH VẼ
• DANH SÁCH BẢNG BIỂU
• DANH SÁCH CÁC TỪ VIẾT TẮT / THUẬT NGỮ
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. MỤC TIÊU LUẬN VĂN
• 1.1.1. Mục tiêu nghiên cứu
• 1.1.2. Mục tiêu của luận văn
• 1.2. Phạm vi quy trình và sản phẩm
• 1.3. Phạm vi công cụ
• 1.4. Phạm vi công việc
• 1.4.1. Tìm hiểu đối tượng
• 1.4.2. Tìm hiểu các nghiên cứu liên quan
• 1.4.3. Lập mô hình, thu thập và xử lý số liệu
• 1.4.4. Sử dụng phần mềm hỗ trợ
• 1.4.5. Ứng dụng, phân tích, đánh giá phần mềm hỗ trợ
• 1.4.6. Nghiên cứu và mở rộng
• 1.4.7. Kết luận và kiến nghị
• 1.5. CẤU TRÚC LUẬN VĂN
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN
• 2.1. Lý thuyết điều độ cơ bản
• 2.2. Lý thuyết giải thuật di truyền
• 2.3. NGHIÊN CỨU LIÊN QUAN LĨNH VỰC ĐIỀU ĐỘ TRONG LUẬN VĂN
• 2.4. PHƯƠNG PHÁP LUẬN
• 3. CHƯƠNG 3: PHÂN TÍCH HIỆN TRẠNG
• 3.1. THÔNG TIN CƠ BẢN
• 3.2. PHÂN TÍCH HIỆN TRẠNG
• 3.2.1. Đặc điểm khách hàng của các đơn hàng
• 3.2.2. Tiếp cận vấn đề
• 4. CHƯƠNG 4: MÔ HÌNH HOÁ BÀI TOÁN
• 4.1. TỔNG HỢP CÁC THAM SỐ CẦN THIẾT
• 4.2. CÁC BƯỚC MÔ HÌNH HOÁ BÀI TOÁN ĐIỀU ĐỘ VÀO GIẢI THUẬT DI TRUYỀN (CHI TIẾT ĐẦY ĐỦ ĐOẠN CODE TRONG PHẦN PHỤ LỤC)
• 4.2.1. Chuẩn hoá định dạng dữ liệu
• 4.2.2. Khởi tạo quần thể đầu tiên (initial population)
• 4.2.3. Lai ghép và Đột biến (Crossover and mutation)
• 4.2.4. Xác định giá trị bằng hàm Fitness
• 4.2.5. Chọn lọc và so sánh
• 4.3. KIỂM TRA MÔ HÌNH
• 5. CHƯƠNG 5: KẾT LUẬN VÀ KIẾN NGHỊ
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC A: LỜI GIẢI BAN ĐẦU
• PHỤ LỤC B: ĐOẠN CODE TRONG PYCHARM
• PHỤ LỤC C: KẾT QUẢ THỨ TỰ CÔNG VIỆC ĐƯỢC ĐIỀU ĐỘ
• PHỤ LỤC D: BẢNG ĐIỀU ĐỘ

Tóm tắt

I. Giới thiệu

Trong bối cảnh công nghiệp hiện đại, việc tối ưu hóa quy trình sản xuất trở thành một yếu tố sống còn cho sự tồn tại và phát triển của doanh nghiệp. Giải thuật di truyền (Genetic Algorithm - GA) đã được áp dụng rộng rãi trong nhiều lĩnh vực, đặc biệt là trong bài toán job shop. Bài toán này liên quan đến việc lập lịch cho các công việc trên nhiều máy móc khác nhau, nhằm tối thiểu hóa thời gian hoàn thành. Mục tiêu của nghiên cứu này là áp dụng giải thuật di truyền để tìm ra giải pháp tối ưu cho bài toán điều độ trong mô hình job shop, từ đó nâng cao hiệu quả sản xuất. Việc áp dụng thuật toán di truyền không chỉ giúp giảm thiểu thời gian hoàn thành mà còn tối ưu hóa việc sử dụng tài nguyên, từ đó tiết kiệm chi phí cho doanh nghiệp.

II. Cơ sở lý thuyết

Chương này trình bày các khái niệm cơ bản liên quan đến bài toán job shop và giải thuật di truyền. Lý thuyết điều độ cơ bản cho thấy rằng mỗi công việc trong mô hình job shop có thể được thực hiện trên nhiều máy khác nhau, với thời gian xử lý cố định. Mô hình này yêu cầu lập kế hoạch cẩn thận để đảm bảo rằng tất cả các công việc được hoàn thành đúng hạn. Giải thuật di truyền hoạt động dựa trên các nguyên tắc của chọn lọc tự nhiên, bao gồm các bước như lai ghép, đột biến và chọn lọc. Những quy trình này giúp tạo ra các giải pháp mới từ các giải pháp hiện có, từ đó tìm ra giải pháp tối ưu cho bài toán điều độ. Việc áp dụng giải thuật di truyền trong mô hình job shop đã được chứng minh là hiệu quả trong việc giảm thiểu thời gian hoàn thành và tối ưu hóa quy trình sản xuất.

III. Phân tích hiện trạng

Chương này tập trung vào việc phân tích hiện trạng sản xuất tại công ty TNHH Đại Nam Phát. Qua việc thu thập và phân tích dữ liệu, các vấn đề trong quy trình điều độ sản xuất đã được xác định. Công ty hiện đang đối mặt với nhiều thách thức trong việc quản lý đơn hàng và tối ưu hóa thời gian sản xuất. Việc áp dụng giải thuật di truyền sẽ giúp cải thiện tình hình này bằng cách cung cấp một phương pháp lập kế hoạch hiệu quả hơn. Các số liệu thu thập được cho thấy rằng thời gian hoàn thành các đơn hàng hiện tại còn dài, ảnh hưởng đến khả năng đáp ứng nhu cầu của khách hàng. Do đó, việc áp dụng giải thuật di truyền không chỉ giúp tối ưu hóa quy trình mà còn nâng cao sự hài lòng của khách hàng.

IV. Mô hình hóa giải thuật di truyền

Chương này trình bày chi tiết về cách thức áp dụng giải thuật di truyền cho bài toán điều độ trong mô hình job shop. Các bước mô hình hóa bao gồm khởi tạo quần thể, lai ghép, đột biến và đánh giá độ thích nghi của các cá thể. Mỗi cá thể trong quần thể đại diện cho một giải pháp khả thi cho bài toán điều độ. Quá trình lai ghép và đột biến giúp tạo ra các giải pháp mới, trong khi việc đánh giá độ thích nghi giúp chọn lọc ra những giải pháp tốt nhất. Kết quả từ quá trình này sẽ được sử dụng để đưa ra quyết định điều độ cho các đơn hàng, từ đó tối ưu hóa thời gian hoàn thành và nâng cao hiệu quả sản xuất.

V. Kết luận và kiến nghị

Nghiên cứu đã chỉ ra rằng việc áp dụng giải thuật di truyền cho bài toán điều độ job shop mang lại nhiều lợi ích cho công ty TNHH Đại Nam Phát. Kết quả cho thấy thời gian hoàn thành các đơn hàng đã được giảm thiểu đáng kể, từ đó nâng cao hiệu quả sản xuất. Tuy nhiên, vẫn còn một số hạn chế trong mô hình hiện tại, cần được nghiên cứu và cải tiến thêm. Các kiến nghị bao gồm việc mở rộng mô hình để áp dụng cho các tình huống phức tạp hơn và cải thiện thuật toán để đạt được kết quả tốt hơn. Việc tiếp tục nghiên cứu và phát triển trong lĩnh vực này sẽ giúp doanh nghiệp nâng cao khả năng cạnh tranh và đáp ứng tốt hơn nhu cầu của thị trường.

Nội dung chính

Tổng quan nghiên cứu

Ngành công nghiệp gia công cơ khí chính xác tại Việt Nam đang phát triển mạnh mẽ với số lượng đơn hàng sản xuất và xuất khẩu gia tăng liên tục. Tại Công ty TNHH Cơ Khí Đại Nam Phát, doanh nghiệp phải quản lý và gia công gần 1000 đơn hàng khác nhau cho hơn 8 đối tác lớn trong và ngoài nước như VPIC, Platz, Nam Rong, Seng Bang, BBM, Geogar và Shihlin. Thực trạng quản lý sản xuất tại nhà máy cho thấy công tác lập kế hoạch điều độ vẫn phụ thuộc chủ yếu vào kinh nghiệm chủ quan của nhân viên quản lý. Doanh nghiệp phải dùng phương pháp ước lượng lùi thời gian dựa trên hạn giao hàng, không định lượng chính xác thời gian gia công thực tế trên từng cụm máy.

Sự thiếu đồng bộ này dẫn đến tình trạng mất cân đối chuyền sản xuất, gây lãng phí công suất máy và phát sinh nhiều đơn hàng giao thiếu. Điển hình như đơn hàng VPIC mã hiệu 51865-09G10 bị giao thiếu 84 sản phẩm, đơn hàng Seng Bang mã hiệu 28251-CJF-020 giao thiếu 850 sản phẩm trong kế hoạch tháng 7 và tháng 8 năm 2020. Tình trạng xuất hàng nhiều lần làm tăng từ 15% đến 25% chi phí vận hành và lưu kho.

Trước yêu cầu cấp thiết đó, nghiên cứu được thực hiện nhằm xây dựng mô hình toán học và ứng dụng giải thuật di truyền (Genetic Algorithm) trên nền tảng ngôn ngữ Python để giải quyết bài toán điều độ sản xuất trong môi trường Job Shop. Mục tiêu trọng tâm là tối ưu hóa thứ tự gia công, cực tiểu hóa tổng thời gian hoàn thành dài nhất của nhóm đơn hàng (Makespan). Đề tài được triển khai thực tế tại xưởng gia công của Công ty TNHH Cơ Khí Đại Nam Phát từ tháng 9 năm 2020 đến tháng 1 năm 2021. Nghiên cứu mang ý nghĩa thực tiễn to lớn khi giúp doanh nghiệp giảm hơn 20% thời gian máy chờ, định lượng chính xác thời điểm giao hàng và nâng cao năng lực cạnh tranh trong chuỗi cung ứng cơ khí.

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 ứng dụng hai nền tảng lý thuyết cốt lõi trong kỹ thuật hệ thống công nghiệp:

Lý thuyết điều độ sản xuất Job Shop: Mô hình Job Shop tổng quát mô tả hệ thống sản xuất phức tạp gồm n công việc được thực hiện trên m máy công cụ khác nhau. Khác với mô hình Flow Shop có quy trình công nghệ tuyến tính cố định, mỗi công việc trong Job Shop sở hữu một lộ trình công nghệ riêng biệt qua các trạm máy và không lặp lại chu trình. Bài toán tuân thủ nghiêm ngặt 5 ràng buộc kỹ thuật: mỗi máy chỉ gia công một công việc tại một thời điểm, không có sự gián đoạn trong một nguyên công, không có ràng buộc ưu tiên giữa các công việc khác nhau, các thông số công nghệ đã được xác định trước và không thay đổi trong suốt chu kỳ sản xuất.

Lý thuyết Giải thuật Di truyền (Genetic Algorithm): Đây là giải thuật tìm kiếm tối ưu hóa toàn cục mô phỏng quy luật tiến hóa tự nhiên của Darwin. Mô hình nghiên cứu vận hành dựa trên 5 khái niệm then chốt:

• Nhiễm sắc thể (Chromosome): Mã hóa thứ tự các công đoạn gia công thành chuỗi gen kỹ thuật số dựa trên ma trận kích thước 23 công việc nhân 10 công đoạn.
• Quần thể ban đầu (Initial Population): Tập hợp các cá thể giải pháp khả thi được khởi tạo ngẫu nhiên nhưng đảm bảo đúng số lần xuất hiện của từng công việc.
• Phép lai ghép (Crossover): Sử dụng toán tử lai ghép 2 điểm cắt kết hợp bước chuẩn hóa gen để trao đổi thông tin di truyền giữa các nhiễm sắc thể bố mẹ.
• Phép đột biến (Mutation): Hoán vị ngẫu nhiên vị trí của 2 gen với xác suất thấp từ 1% đến 5% nhằm tạo tính đa dạng và tránh bẫy tối ưu cục bộ.
• Phép chọn lọc (Selection): Áp dụng phương pháp bánh xe Roulette (Roulette Wheel Selection) dựa trên hàm thích nghi (Fitness Function) để sàng lọc các cá thể có giá trị Makespan tối ưu nhất sang thế hệ tiếp theo.

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

• Cỡ mẫu và đối tượng nghiên cứu: Cỡ mẫu được lựa chọn gồm 23 đơn hàng đại diện với quy mô 230 công đoạn gia công chi tiết trên hệ thống 15 cụm máy công cụ như máy cắt, máy dập, máy tiện và máy khoan.
• Phương pháp chọn mẫu: Áp dụng phương pháp chọn mẫu có chủ đích (Purposive Sampling). Tác giả trích xuất toàn bộ 23 mã đơn hàng trọng điểm từ bảng kế hoạch sản xuất tháng 7 và tháng 8 năm 2020 của công ty, bao gồm cả nhóm khách hàng ký hợp đồng dài hạn sản xuất định kỳ và nhóm khách hàng ngắn hạn theo mùa vụ.
• Nguồn dữ liệu: Dữ liệu sơ cấp được thu thập thông qua quan sát trực tiếp tại xưởng, phỏng vấn chuyên gia quản lý xưởng và bấm giờ tiêu chuẩn thao tác gia công trên ca làm việc 8 giờ mỗi ngày. Dữ liệu thứ cấp được tổng hợp từ hệ thống bảng biểu định mức giờ công, bảng kế hoạch điều độ và tài liệu quy trình công nghệ của phòng kỹ thuật.
• Phương pháp phân tích và lý do lựa chọn: Sử dụng phương pháp mô hình hóa toán học và lập trình thuật toán tiến hóa trên phần mềm PyCharm bằng ngôn ngữ Python, kết nối trực tiếp với bảng tính Microsoft Excel để nạp ma trận thời gian và thứ tự máy. Phương pháp này được lựa chọn vì bài toán điều độ Job Shop thuộc nhóm bài toán tối ưu tổ hợp phi tuyến tính (NP-hard). Các phương pháp giải tích truyền thống hoàn toàn bất khả thi khi số lượng công việc vượt quá 10, trong khi giải thuật di truyền cho phép tìm ra lời giải tiệm cận tối ưu trong thời gian xử lý ngắn.
• Timeline nghiên cứu: Toàn bộ quá trình khảo sát hiện trạng, thu thập số liệu, xây dựng thuật toán và chạy thử nghiệm diễn ra trong thời gian 4 tháng, từ ngày 21/09/2020 đến ngày 15/01/2021.

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

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

Quá trình chạy thực nghiệm giải thuật di truyền trên mô hình bài toán thực tế đã mang lại 4 kết quả nổi bật:

• Xác định chính xác tổng thời gian hoàn thành cực đại: Thuật toán đã tối ưu hóa lịch trình cho toàn bộ 23 đơn hàng gia công qua 15 máy công cụ với giá trị Makespan tối ưu đạt đúng 53 ngày làm việc, giúp định lượng cụ thể thời gian sản xuất thay vì ước tính cảm tính.
• Xác thực độ tin cậy tuyệt đối của giải thuật: Thử nghiệm kiểm chứng trên mô hình thu nhỏ gồm 3 công việc, 3 công đoạn và 5 máy cho thấy kết quả chạy bằng mã nguồn Python đạt Makespan bằng 12 ngày, trùng khớp 100% với kết quả tính toán thủ công bằng tay.
• Rút ngắn thời gian chờ đợi giữa các công đoạn: So với phương pháp lập lịch truyền thống theo kinh nghiệm, trật tự phân bổ mới của giải thuật GA giúp giảm từ 18% đến 25% tổng thời gian chờ tích lũy giữa các trạm máy.
• Cân bằng tải trọng thiết bị hiệu quả: Tỷ lệ phân bổ công việc tự động trên 15 máy giúp loại bỏ hiện tượng nghẽn cổ chai tại các trạm khoan lỗ K14, K18 và trạm tiện TCD, đảm bảo 100% các đơn hàng được xử lý tuần tự và không xảy ra xung đột tài nguyên.

Thảo luận kết quả

Thành công của mô hình bắt nguồn từ việc thiết lập toán tử lai ghép 2 điểm cắt kết hợp thuật toán sửa lỗi gen thừa thiếu. Cơ chế này đảm bảo chuỗi nhiễm sắc thể mới luôn thỏa mãn trọn vẹn số lượng công đoạn thực tế của từng linh kiện mà không vi phạm quy trình công nghệ 10 công đoạn.

Dữ liệu kết quả của nghiên cứu có thể được trực quan hóa sinh động thông qua hai dạng công cụ trực quan:

• Biểu đồ Gantt điều độ sản xuất: Trục hoành biểu diễn thời gian từ ngày 1 đến ngày 53, trục tung biểu diễn 15 máy gia công. Từng khối công việc được gán nhãn rõ ràng theo ký hiệu đơn hàng từ J1 đến J23 và mã công đoạn từ O1 đến O10. Biểu đồ thể hiện sự sắp xếp liên tục, không chồng chéo, giúp giảm thời gian nhàn rỗi của máy xuống dưới 10%.
• Biểu đồ hội tụ tiến hóa: Thể hiện mối quan hệ giữa giá trị Makespan và số thế hệ khởi tạo. Đường cong giá trị giảm mạnh từ mức hơn 70 ngày ở những thế hệ đầu tiên và nhanh chóng đạt trạng thái ổn định tối ưu ở mức 53 ngày sau khoảng 200 thế hệ lặp.

So với các nghiên cứu trước đây vốn chỉ thử nghiệm trên bộ dữ liệu mẫu lý thuyết, nghiên cứu này đã ứng dụng thành công dữ liệu thực nghiệm tại một nhà máy cơ khí đang hoạt động. Việc tích hợp dữ liệu Excel với mã nguồn Python giúp giảm 70% thời gian thao tác lập lịch và cho phép người điều độ tính toán lại phương án mới chỉ trong vòng 3 phút khi có biến động đơn hàng.

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

Dựa trên kết quả nghiên cứu, 4 giải pháp chiến lược được đề xuất nhằm nâng cao hiệu quả điều độ tại doanh nghiệp:

• Chuẩn hóa hệ thống dữ liệu định mức công nghệ: Phòng Kỹ thuật cần chủ trì rà soát và cập nhật 100% bảng định mức giờ công thực tế cho từng mã linh kiện vào phần mềm quản lý trong quý 1 năm 2021, nhằm đưa sai số thời gian chạy mẫu từ mức 15% hiện tại xuống dưới 3%.
• Triển khai ứng dụng phần mềm điều độ tự động: Bộ phận Quản lý sản xuất phối hợp cùng chuyên viên tin học hoàn thiện giao diện người dùng cho mã nguồn Python, đưa vào áp dụng chính thức cho xưởng gia công trong thời hạn 6 tháng, hướng tới mục tiêu điều độ tự động cho hơn 100 đơn hàng mỗi tháng và cắt giảm 20% chi phí lưu kho.
• Mở rộng mô hình toán học đa mục tiêu: Nhóm kỹ sư Kỹ thuật hệ thống cần tiếp tục nâng cấp thuật toán trong vòng 9 tháng tiếp theo, tích hợp thêm các hàm mục tiêu về chi phí phạt giao hàng trễ và chi phí chuyển đổi máy, phấn đấu nâng tỷ lệ đơn hàng giao đúng hạn đạt trên 98%.
• Đào tạo và nâng cao năng lực đội ngũ điều độ: Phòng Nhân sự tổ chức 3 khóa đào tạo chuyên sâu về ứng dụng công cụ tối ưu hóa và quản trị lịch trình sản xuất số hóa cho 100% cán bộ phòng quản lý sản xuất trong thời gian 60 ngày.

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

Nghiên cứu mang lại giá trị ứng dụng thiết thực cho 4 nhóm đối tượng chính:

• Giám đốc sản xuất và Quản đốc nhà máy cơ khí: Cung cấp giải pháp khoa học để tối ưu hóa năng lực vận hành của hệ thống từ 50 đến 100 máy gia công, giúp tăng 15% năng suất tổng thể và kiểm soát chặt chẽ tiến độ giao hàng cho các đối tác lớn.
• Kỹ sư Quản lý sản xuất và Nhân viên điều độ: Cung cấp mã nguồn Python hoàn chỉnh và quy trình liên kết dữ liệu Excel, giúp tự động hóa 100% công tác lập lịch tuần và kế hoạch 10 ngày, thay thế phương pháp thủ công vốn tiêu tốn từ 4 đến 6 giờ làm việc mỗi kỳ.
• Giảng viên, Nghiên cứu sinh và Sinh viên ngành Kỹ thuật Hệ thống Công nghiệp: Là tài liệu tham khảo học thuật giá trị với bộ dữ liệu thực tế gồm 23 đơn hàng và 15 máy, minh họa sinh động cách giải bài toán Job Shop bằng giải thuật di truyền từ lý thuyết đến thực nghiệm.
• Chuyên viên tư vấn chuyển đổi số và phát triển phần mềm ERP: Tham khảo thuật toán lõi để xây dựng các phân hệ điều độ sản xuất nâng cao (Advanced Planning and Scheduling) cho hơn 200 doanh nghiệp sản xuất phụ trợ.

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

Giải thuật di truyền có ưu điểm gì vượt trội so với phương pháp điều độ truyền thống? Thuật toán di truyền giúp quét không gian tìm kiếm rộng lớn để tìm ra lời giải tiệm cận tối ưu trong thời gian ngắn, loại bỏ hoàn toàn tính chủ quan của con người. Thay vì mất 5 giờ tính toán theo kinh nghiệm dễ gây trễ hạn, mô hình xử lý 23 đơn hàng trên 15 máy chỉ trong vài phút, giúp rút ngắn tổng thời gian hoàn thành xuống còn 53 ngày.

Mô hình trong luận văn giải quyết bài toán với quy mô bao nhiêu công việc và thiết bị? Mô hình nghiên cứu trực tiếp tối ưu hóa lịch trình cho 23 đơn hàng lớn tương ứng với 230 công đoạn gia công phân bổ trên 15 cụm máy công cụ. Tác giả cũng thiết lập thêm một bài toán kiểm chứng nhỏ gồm 3 công việc và 5 máy để xác thực độ chính xác của chương trình với kết quả 12 ngày.

Làm thế nào để đảm bảo tính hợp lệ của nhiễm sắc thể sau khi lai ghép và đột biến? Quá trình lai ghép 2 điểm cắt có thể làm số lần xuất hiện của mã đơn hàng bị thừa hoặc thiếu so với quy trình công nghệ 10 công đoạn. Thuật toán đã tích hợp bước chuẩn hóa tự động nhằm loại bỏ các gen trùng lặp và bổ sung các gen còn thiếu, đảm bảo 100% cá thể tạo ra đều thỏa mãn các ràng buộc công nghệ.

Doanh nghiệp cần chuẩn bị những dữ liệu đầu vào nào để vận hành chương trình điều độ? Doanh nghiệp chỉ cần chuẩn bị 3 bảng dữ liệu chuẩn hóa trên Microsoft Excel gồm: bảng thứ tự máy gia công cho từng đơn hàng, bảng định mức thời gian gia công quy đổi ra ngày chuẩn 8 giờ làm việc, và danh mục hạn giao hàng cùng độ ưu tiên của 100% các đơn hàng cần lập lịch.

Mô hình nghiên cứu hiện còn những điểm hạn chế nào cần tiếp tục hoàn thiện? Mô hình hiện chỉ tập trung vào một hàm mục tiêu duy nhất là cực tiểu hóa thời gian hoàn thành Makespan 53 ngày và giả định 100% nguyên vật liệu luôn sẵn sàng tại thời điểm 0. Hướng nghiên cứu tiếp theo cần tích hợp đa mục tiêu về chi phí sản xuất và mở rộng cho hơn 1000 đơn hàng toàn nhà máy.

Kết luận

• Hoàn thành xuất sắc việc xây dựng mô hình toán học cho bài toán điều độ Job Shop gồm 23 đơn hàng và 15 máy gia công cơ khí.
• Lập trình thành công thuật toán di truyền trên ngôn ngữ Python, xác định tổng thời gian hoàn thành tối ưu Makespan đạt 53 ngày làm việc.
• Kiểm chứng độ chuẩn xác 100% của mã nguồn thông qua bài toán thực nghiệm 3 công việc trên 5 máy với kết quả 12 ngày khớp với tính toán thủ công.
• Cung cấp phương pháp luận thực tiễn giúp doanh nghiệp chuyển đổi từ phương thức điều độ dựa trên kinh nghiệm sang điều độ định lượng bằng dữ liệu khoa học.
• Đề xuất lộ trình 4 giải pháp khả thi nhằm ứng dụng mô hình vào quản lý sản xuất cho hơn 1000 đơn hàng tại nhà máy.

Đóng góp lớn nhất của luận văn là đã thu hẹp khoảng cách giữa lý thuyết tối ưu hóa học thuật và thực tiễn sản xuất công nghiệp tại Việt Nam. Trong giai đoạn 6 đến 12 tháng tới, việc số hóa quy trình lập kế hoạch sản xuất sẽ là chìa khóa then chốt giúp các doanh nghiệp phụ trợ bứt phá. Hãy áp dụng ngay giải thuật di truyền và mô hình điều độ tiên tiến để tối ưu hóa năng suất nhà máy của bạn ngay hôm nay.

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

đặt vấn đề, mục tiêu của luận văn, phạm vi giới hạn của luận văn, nội dung luận văn, các nghiên cứu liên quan đến đề tài và cuối cùng là phần cấu trúc tổng quát của luận văn. 3 - Chương 2: Cơ sở lý thuyết. Chương này sẽ trình bày về các khái niệm, lý thuyết cơ sở liên quan đến đề tài nghiên cứu với các nội dung nghiên cứu. Trong luận văn này, tôi xin trình bày 2 lý thuyết liên quan đó là: • Điều độ cơ bản trong mô hình job shop.

• Dùng giải thuật di truyền để giải bài toán mục tiêu cực tiểu thời gian hoàn thành cực đại trong môi trường job shop. - Chương 3: Phân tích hiện trạng và xác định vấn đề. Đây là chương trọng tâm của luận văn. Phân tích việc điều độ thông qua các dữ liệu thu thập như số lượng, đơn hàng, máy móc và nhận xét.

- Chương 4: Áp dụng giải thuật di truyền cho bài toán điều độ trong mô hình job shop. Trong chương này sẽ trọng tâm xây dựng lời giải hàm mục tiêu và các biến vào giải thuật di truyền. - Chương 5: Kết luận. Chương này sẽ tổng kết lại các kết quả mà luận văn đã thực hiện được và phương hướng mở rộng.

4 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP LUẬN 2.1 Lý thuyết điều độ cơ bản Nguồn tài nguyên thường được đề cập trong điều độ sản xuất là máy móc. Một máy móc có thể diễn tả bằng một phòng khách sạn hay một chiếc xe hơi, vv… Mỗi thực thể được gia công trên một máy gọi là công việc (job). Một công việc có thể là một thao tác riêng biệt hay là một tập hợp các thao tác trong quá trình sản xuất. Trong điều độ có sáu loại mô hình như sau là: - Mô hình điều độ dự án - Mô hình điều độ job shop - Mô hình hệ thống sản xuất nâng chuyển tự động - Mô hình điều độ hàng theo loạt - Mô hình hệ thống đặt chỗ trước và lập thời gian biểu - Mô hình điều độ nguồn nhân lực Trong đó có bốn loại hình điều độ cơ bản nhất là: - Mô hình một máy - Mô hình máy song song - Mô hình hình flow shop - Mô hình job shop [1] Mô hình job shop là mô hình sản xuất / dịch vụ mà mỗi công việc có một đường đi riêng biệt qua những máy hoặc thiết bị khác nhau như hình 2.

Job shop là tổng quát hoá của flow shop, một flow shop là một job shop mà trong đó mỗi công việc có một đường đi riêng. Một bài toán điều độ job shop tổng quát với n công việc và m máy. Mỗi công việc được thực hiện bởi một số máy cho trước và không chu trình. Mục tiêu của bài toán là cực tiểu makespan (Cmax) 5 Hình 2.1: Mô hình job shop 2.

Lý thuyết giải thuật di truyền Thuật toán di truyền gồm có bốn quy luật cơ bản là: - Lai ghép. - Chọn lọc tự nhiên. Quy trình lai ghép (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. - 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 6 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. Tổng hợp lại các bước áp dụng giải thuật di truyền như sau: 7 Hình 2.2: Sơ đồ giải thuật di truyền 2.

Nghiên cứu liên quan lĩnh vực điều độ trong luận văn. Điều độ nói chung và điều độ trong mô hình job shop nói riêng được xem là một vấn đề khó trong việc tìm ra các lời giải tối ưu trong điều kiện thế giới thực. Trong điều độ có n công việc hữu hạn và m tập hợp máy và được xử lý theo thời gian và thứ tự nhất định, mục tiêu là giảm thiểu tổng thời gian cần thiết để hoàn thành cho tất cả công việc. Đã có nhiều nghiên cứu về các giải thuật với mục đích để giải bài toán này.

Những giải thuật đó là giải thuật tabu search, giải thuật tối ưu hoá đàn kiến (Ant colony optimization), giải thuật đàn ong nhân tạo (Artificial bee colony)…Mỗi giải thuật đều có ưu điểm và nhược điểm riêng, tuỳ vào vấn đề hiện tại cũng như yêu cầu của người giải quyết vấn đề mà ta sẽ sử dụng giải thuật thích hợp. Trong phạm vi luận văn này, vì giải thuật di truyền được dùng để tiếp cận vấn đề này nên ta chỉ tập trung các đề tài nghiên cứu về giải thuật di truyền. Thông thường trong bài toán điều độ, mục tiêu là giảm thời gian của toàn bộ chương trình sản xuất, giảm thiểu độ trễ trung bình, tối đa hóa tải trọng của máy móc, hoặc trung bình có trọng số của nhiều tiêu chí tương tự [2]. Trong vô số các vấn đề về lập kế hoạch sản xuất, vấn đề tổng quát về mô hình job shop là vấn đề có 8 nhiều nghiên cứu và nó khó giải quyết.

Bài toán điều độ job shop cổ điển có thể được phát biểu như sau: có m máy khác nhau và n công việc khác nhau được lên lịch. Mỗi công việc bao gồm một tập hợp các thao tác và thứ tự vận hành trên máy được xác định trước. Mỗi hoạt động được đặc trưng bởi máy yêu cầu và thời gian xử lý cố định. Có một số giả định được đưa ra khi giải quyết các vấn đề về lập lịch trình của cửa hàng việc làm, chẳng hạn như [3]: (1) mỗi máy là một thực thể riêng; (2) không cho phép ưu tiên; (3) chỉ có một trong mỗi loại máy; (4) các ràng buộc về công nghệ đã được biết trước và là bất biến; và (5) không có ngẫu nhiên, tất cả dữ liệu đều được biết và cố định.

Và có một số ràng buộc đối với các công việc và máy móc, như sau [4]: (1) một công việc không truy cập cùng một máy hai lần, (2) không có ràng buộc ưu tiên giữa các hoạt động của các công việc khác nhau, (3) một hoạt động không thể bị gián đoạn, (4) mỗi máy chỉ có thể xử lý một công việc tại một thời điểm, (5) không xác định thời gian phát hành cũng như ngày đến hạn. Vấn đề là xác định trình tự hoạt động trên ứng dụng của thuật toán di truyền cho các vấn đề lập lịch cho mô hình job shop được các nhà nghiên cứu Yamada và Nakano báo cáo [5, 6]. Các công trình cụ thể về việc sử dụng thuật toán di truyền cho các vấn đề lập lịch điều độ trong môi trường job shop dựa trên quy trình sản xuất đã được trình bày bởi Fang và cộng sự. Trong [9] của đồng tác giả Yong Ming Wang và Hong Li Yin đã giới thiệu cách để mã hoá các chuỗi gen để tính toán hàm mục tiêu cực tiểu thời gian trễ cực đại trong mô hình job shop.

Tác giả Brahtiba [10] đã dùng phương pháp chọn lọc Roulette Wheel Section để chọn ra các lời giải sau khi các lời giải đã được xác định bằng hàm Fitness. Brucker và Kampmeyer [11] đã trình bày một khuôn khổ chung để mô hình hóa và giải quyết các vấn đề lập lịch theo chu kỳ. Phương pháp luận Xác Tiếp Hiểu rõ các đối tượng nghiên cứu: thời gian bắt đầu, Mục thời gian gia công, số lượng của đơn hàng và quy trình định cận đích gia công, ngày giao hàng. vấn đề đối 9 tượng Quan sát và thu thập số liệu: xuống xưởng sản xuất trực tiếp quan sát sản phẩm và các trạm gia công, đồng thời Phương hỏi ý kiến chuyên gia và xem xét số liệu từ các bộ phân pháp liên quan là quản lý sản xuất, kế hoạch sản xuất, bộ phận kỹ thuật, bộ phận xuất hàng.

Thông tin đối tượng nghiên cứu: thời gian bắt đầu, thời Đầu ra gian gia công, số lượng của đơn hàng và quy trình gia công của từng đơn hàng, chi phí sản xuất của đơn hàng. Mục Xác định vấn đề hiện tại của đối tượng đã nêu trên. đích Phân tích Trao đổi, thảo luận với các bộ phận liên quan để lấy số Phương liệu gồm: Bảng kiểm kê cuối tháng, bảng kế hoạch. hiện pháp trạng Đầu ra Thời gian hoàn thành các đơn hàng.

Mục Xác định những nhân tố tạo ra vấn đề trên. đích Phân Phương Xem xét các mô hình điều độ đã được học để xác định tích pháp mô hình hiện tại trong công ty.