Luận văn thạc sĩ về điều độ sản xuất động và đa mục tiêu trong môi trường job shop linh hoạt

Luận văn thạc sĩ về kỹ thuật công nghiệp, điều độ sản xuất động và đa mục tiêu trong môi trường job shop linh hoạt. Tìm hiểu và áp dụng.

• Tác giả: Trần Võ Thảo Hương
• Người hướng dẫn: PGS. Lê Ngọc Quỳnh Lam
• Trường học: Đại học Bách Khoa - Đại học Quốc Gia Thành phố Hồ Chí Minh
• Chuyên ngành: Kỹ thuật Công nghiệp
• Đề tài: Điều Độ Sản Xuất Động Và Đa Mục Tiêu Trong Môi Trường Job Shop Linh Hoạt
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• ACKNOWLEDGEMENTS
• TÓM TẮT
• ABSTRACT
• REASSURANCE
• LIST OF TABLES
• LIST OF FIGURES
• LIST OF NOTATIONS
• 1. CHAPTER 1: INTRODUCTION
• 1.1. Background and Motivation
• 1.2. Objectives
• 1.3. Scope
• 1.4. Methodology
• 1.4.1. Formulating the problem model
• 1.4.2. Proposing the algorithm for the predictive scheduling problem
• 1.4.3. Proposing the algorithm for the reactive scheduling problem
• 1.4.4. Evaluation and revision
• 1.5. Contributions
• 1.6. Organization of the Thesis
• 2. CHAPTER 2: LITERATURE REVIEW
• 2.1. Production Scheduling Overview
• 2.2. Production Scheduling Problem Model
• 2.2.1. Processing Characteristics and Constraints
• 2.3. Deterministic scheduling algorithm
• 2.4. Predictive-reactive scheduling
• 3. CHAPTER 3: DETERMINISTIC PROBLEM FORMULATION
• 3.1. Problem description
• 3.2. Mathematical model formulation
• 4. CHAPTER 4: PREDICTIVE SCHEDULING
• 4.1. Proposed heuristic algorithm
• 4.1.1. The main procedure of proposed algorithm
• 4.1.2. Operation selection rule
• 4.1.3. Machine selection rule
• 4.2. Comparison of dispatching rules
• 4.3. The detailed steps of proposed algorithm
• 5. CHAPTER 5: REACTIVE SCHEDULING
• 5.1. Defining the latest completion time of operation
• 5.2. Event classification method
• 5.3. Example on each type of event
• 6. CHAPTER 6: COMPUTATIONAL RESULTS
• 6.1. Design of experiments
• 6.2. The results of experiments
• 7. CHAPTER 7: CONCLUSIONS AND RECOMMENDATIONS
• REFERENCES
• APPENDIX A
• APPENDIX B
• APPENDIX C

Tóm tắt

I. Tổng quan về điều độ sản xuất

Trong bối cảnh công nghiệp hiện đại, điều độ sản xuất đóng vai trò quan trọng trong việc tối ưu hóa quy trình sản xuất. Đặc biệt, trong môi trường job shop linh hoạt, việc quản lý và điều phối các nguồn lực trở nên phức tạp hơn do sự đa dạng của các công đoạn và máy móc. Mục tiêu chính của việc điều độ là giảm thiểu thời gian hoàn thành công việc (makespan) và thời gian trễ lớn nhất của các công việc. Các phương pháp điều độ hiện tại thường gặp phải những thách thức từ các yếu tố bất định như hỏng hóc máy móc hoặc thay đổi yêu cầu sản xuất. Do đó, việc phát triển một mô hình điều độ phù hợp với đa mục tiêu và có khả năng phản ứng với các sự kiện không mong muốn là rất cần thiết.

1.1 Mô hình bài toán điều độ sản xuất

Mô hình bài toán điều độ sản xuất trong môi trường job shop linh hoạt được xây dựng dựa trên các yếu tố như thời gian xử lý, thứ tự thực hiện công việc và các ràng buộc về thời gian. Mô hình này không chỉ giúp xác định lịch trình sản xuất mà còn phải đáp ứng các mục tiêu về hiệu suất, bao gồm việc tối ưu hóa thời gian hoàn thành và giảm thiểu thời gian trễ. Việc áp dụng các thuật toán tối ưu hóa, như thuật toán heuristic, giúp rút ngắn thời gian tính toán và nâng cao hiệu quả trong việc xây dựng lịch trình.

II. Phương pháp điều độ dự đoán và phản ứng

Phương pháp điều độ dự đoán và phản ứng là một trong những chiến lược hiệu quả để giải quyết các vấn đề trong môi trường job shop linh hoạt. Đầu tiên, một lịch trình dự đoán được xây dựng dựa trên dữ liệu đầu vào có sẵn. Tuy nhiên, trong thực tế, việc triển khai lịch trình này thường gặp phải các yếu tố bất định. Do đó, một chiến lược tái điều độ được áp dụng để điều chỉnh lịch trình khi có sự cố xảy ra. Chiến lược này không chỉ giúp giảm thiểu tác động tiêu cực mà còn giữ cho quá trình sản xuất ổn định.

2.1 Chiến lược tái điều độ

Chiến lược tái điều độ được thiết kế để ứng phó với các sự kiện không mong muốn trong quá trình sản xuất. Các sự kiện này có thể bao gồm hỏng hóc máy móc, thay đổi yêu cầu sản xuất hoặc thời gian xử lý không chính xác. Việc phân loại các sự kiện và xác định thời điểm tái điều độ là rất quan trọng trong việc duy trì hiệu suất sản xuất. Phương pháp kết hợp giữa tái điều độ theo sự kiện và tái điều độ theo chu kỳ đã được chứng minh là có hiệu quả cao trong việc giảm thiểu thời gian gián đoạn và duy trì tính ổn định của lịch trình.

III. Đánh giá hiệu quả và ứng dụng thực tiễn

Nghiên cứu này không chỉ cung cấp một cái nhìn sâu sắc về điều độ sản xuất trong môi trường job shop linh hoạt mà còn đề xuất các giải pháp thực tiễn cho các doanh nghiệp. Các kết quả tính toán cho thấy rằng các thuật toán đề xuất có khả năng đáp ứng tốt các mục tiêu đã đặt ra, bao gồm việc tối ưu hóa thời gian hoàn thành và giảm thiểu thời gian trễ. Điều này cho thấy giá trị thực tiễn của nghiên cứu trong việc cải thiện hiệu suất sản xuất và khả năng cạnh tranh của doanh nghiệp.

3.1 Ứng dụng trong doanh nghiệp

Các giải pháp được đề xuất trong nghiên cứu có thể được áp dụng rộng rãi trong các doanh nghiệp sản xuất, đặc biệt là trong ngành công nghiệp chế tạo. Việc áp dụng các phương pháp điều độ dự đoán và phản ứng không chỉ giúp tối ưu hóa quy trình sản xuất mà còn nâng cao khả năng ứng phó với các tình huống bất ngờ, từ đó tạo ra lợi thế cạnh tranh bền vững cho doanh nghiệp.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh công nghiệp hóa hiện đại và làn sóng Cách mạng Công nghiệp 4.0, việc tối ưu hóa quy trình điều độ sản xuất đóng vai trò quyết định đến năng lực cạnh tranh của doanh nghiệp sản xuất theo đơn hàng. Theo các báo cáo ngành sản xuất cơ khí chính xác, sự gián đoạn lịch trình và tình trạng giao hàng chậm trễ có thể làm sụt giảm từ 15% đến 30% biên lợi nhuận hoạt động. Vấn đề nghiên cứu cốt lõi xuất phát từ thực tế rằng các xưởng sản xuất, đặc biệt là ngành chế tạo khuôn mẫu, luôn phải đối mặt với các biến động ngẫu nhiên như máy hỏng đột xuất, đơn hàng gấp chèn ngang hoặc nguyên vật liệu cung ứng trễ.

Mục tiêu cụ thể của luận văn là xây dựng mô hình toán học và phát triển thuật toán điều độ dự báo - phản ứng (Predictive-Reactive Scheduling) cho bài toán điều độ xưởng linh hoạt (Flexible Job Shop Scheduling - FJSS). Giải pháp hướng tới việc tối ưu hóa đồng thời 2 mục tiêu mâu thuẫn: cực tiểu hóa tổng thời gian hoàn thành toàn bộ công việc (Makespan) và cực tiểu hóa độ trễ lớn nhất của các đơn hàng (Maximum Tardiness).

Phạm vi nghiên cứu được thực hiện tại Trường Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh trong giai đoạn từ tháng 02/2019 đến tháng 12/2019, tập trung vào môi trường sản xuất linh hoạt dạng ngẫu nhiên. Ý nghĩa thực tiễn của công trình thể hiện qua việc cung cấp công cụ tự động hóa lập lịch với thời gian tính toán thực thi dưới 14 giây cho các bài toán quy mô lớn lên đến 100 công việc và 60 máy, tạo nền tảng vững chắc giúp doanh nghiệp nâng cao tỷ lệ giao hàng đúng hẹn đạt trên 95% và tối ưu hóa chi phí vận hành thiết bị.

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 nền tảng lý thuyết tối ưu hóa tổ hợp và điều độ sản xuất trong môi trường Job Shop linh hoạt (FJSS). Đây là bài toán thuộc lớp NP-hard phức tạp bậc cao, mở rộng từ bài toán Job Shop truyền thống bằng việc cho phép một công đoạn có thể gia công trên nhiều máy thay thế với thời gian xử lý khác nhau. Để giải quyết bài toán đa mục tiêu, mô hình áp dụng phương pháp tổng trọng số (Weighted Sum Method) với tỷ lệ phân bổ cân bằng 50% cho mục tiêu thời gian hoàn thành và 50% cho mục tiêu độ trễ lớn nhất.

Mô hình nghiên cứu chuẩn hóa các khái niệm trọng tâm bao gồm:

• Thời gian hoàn tất toàn bộ công việc: Thời điểm chi tiết cuối cùng của toàn bộ các lô sản xuất kết thúc gia công.
• Độ trễ lớn nhất: Giá trị sai lệch dương lớn nhất giữa thời điểm hoàn thành thực tế và thời hạn giao hàng cam kết trong hợp đồng.
• Quy tắc phân phối: Hệ thống các thuật toán heuristic cục bộ gồm quy tắc chọn nguyên công dựa trên hạn hoàn thành từng công đoạn (Operation Due Date - ODD), quy tắc chia sẻ thời gian dự trữ (Slack Time), và quy tắc chọn máy dựa trên tổng lượng công việc chờ (WINQ, RPT, PT).
• Chiến lược điều độ dự báo - phản ứng: Khung điều hành tích hợp giữa lịch trình dự báo ban đầu và cơ chế cập nhật thích ứng theo thời gian thực khi xuất hiện biến cố.

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

Nghiên cứu sử dụng nguồn dữ liệu thực nghiệm chuẩn mực quốc tế gồm 20 bộ dữ liệu điểm chuẩn (từ B41 đến B60) do Behnke và Geiger phát triển. Phương pháp chọn mẫu có chủ đích được áp dụng để phân tầng quy mô bài toán thành 4 nhóm kích thước đại diện: quy mô nhỏ (10 công việc, 60 máy), quy mô vừa (20 công việc, 60 máy), quy mô lớn (50 công việc, 60 máy) và quy mô rất lớn (100 công việc, 60 máy).

Lý do lựa chọn phương pháp phân tích heuristic dựa trên luật phân phối kết hợp mô hình tối ưu hóa quy hoạch tuyến tính nguyên hỗn hợp (MILP) là nhằm giải quyết bài toán bùng nổ tổ hợp tính toán, đáp ứng yêu cầu ra quyết định tức thì trên sàn xưởng. Đối với giai đoạn phản ứng, đề tài thiết kế chiến lược tái điều độ lai (Hybrid Rescheduling) kết hợp giữa tái lập lịch định kỳ và tái lập lịch kích hoạt theo sự kiện. Toàn bộ thuật toán được lập trình mô phỏng trên nền tảng VBA trong môi trường Microsoft Excel kết hợp phần mềm tối ưu hóa CPlex, tiến hành đánh giá liên tục thông qua chỉ số độ lệch hiệu năng tương đối (RPD) trong suốt thời gian 10 tháng triển khai.

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

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

Thứ nhất, qua quá trình kiểm thử 6 tổ hợp quy tắc phân phối (từ C1 đến C6), tổ hợp C4 kết hợp giữa luật chọn nguyên công ODD (OR1) và luật chọn máy có trọng số thời gian gia công MR2 mang lại hiệu quả tối ưu vượt trội nhất với chỉ số RPD đạt mức thấp nhất, tiệm cận 0% trên hầu hết các kịch bản thử nghiệm.

Thứ hai, đối với các bộ dữ liệu quy mô lớn từ B51 đến B60 (50 đến 100 công việc), quy tắc chọn máy MR2 chứng minh ưu thế áp đảo so với MR1. Cụ thể, tổ hợp C4 giúp kiểm soát thời hạn hoàn thành chặt chẽ, giảm độ trễ lớn nhất từ mức 109 đơn vị thời gian (ở tổ hợp C2) xuống chỉ còn 24 đến 30 đơn vị thời gian trên bài toán 100 công việc, tương đương mức cải thiện độ chính xác thời gian giao hàng lên tới trên 70%.

Thứ ba, thuật toán heuristic đề xuất sở hữu tốc độ xử lý vượt trội. Thời gian tính toán trung bình chỉ mất 1,07 giây cho quy mô 10 công việc (bộ B41) và đạt tối đa 13,91 giây cho quy mô cực đại 100 công việc (bộ B60) trên máy tính cá nhân cấu hình tầm trung.

Thứ tư, cơ chế phân loại sự cố thành 3 nhóm tác động giúp chiến lược tái điều độ lai cắt giảm hơn 50% số lần tái lập lịch không cần thiết so với phương pháp kích hoạt thuần túy theo sự kiện, bảo vệ độ ổn định cao nhất cho hệ thống sản xuất.

Thảo luận kết quả

Dữ liệu nghiên cứu được biểu diễn trực quan thông qua biểu đồ tiến độ Gantt, bảng ma trận so sánh đa chỉ tiêu và đồ thị biểu đồ hộp (Box-plot) thể hiện phân phối giá trị RPD. Đồ thị Box-plot cho thấy tổ hợp C4 có giá trị trung vị RPD sát mức 0 cùng khoảng tứ phân vị hẹp nhất, minh chứng cho độ tin cậy và tính ổn định cao của giải pháp khi mở rộng quy mô sản xuất.

Nguyên nhân cốt lõi giúp tổ hợp C4 đạt hiệu năng tối ưu là nhờ cơ chế phân bổ hạn giao hàng chi tiết đến từng nguyên công đơn lẻ kết hợp tính toán tích số thời gian gia công, giúp ngăn chặn triệt để tình trạng tắc nghẽn cục bộ tại các máy trung tâm. So sánh với các nghiên cứu truyền thống vốn chỉ tiếp cận điều độ tĩnh hoặc đơn mục tiêu, mô hình dự báo - phản ứng này giải quyết trọn vẹn sự xung đột giữa bài toán nâng cao công suất máy và cam kết thời gian giao hàng trong điều kiện xưởng thực tế có nhiều rủi ro bất định.

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

Nhằm chuyển giao hiệu quả kết quả nghiên cứu vào thực tế quản trị vận hành, 4 khuyến nghị hành động cụ thể được đề xuất:

• Chuẩn hóa hệ thống phân loại sự kiện bất định thành 3 nhóm tác động: Doanh nghiệp cần ban hành bảng tiêu chí phân loại sự cố (nhóm tác động nghiêm trọng, nhóm chấp nhận được và nhóm không ảnh hưởng) trong 3 tháng đầu triển khai, hướng tới mục tiêu giảm 25% thời gian lãng phí do dừng chuyền.
• Tích hợp thuật toán điều độ heuristic C4 vào hệ thống điều hành sản xuất MES hoặc ERP: Bộ phận công nghệ thông tin và kỹ thuật công nghiệp phối hợp nhúng mã nguồn thuật toán vào phần mềm quản lý trong thời hạn 6 tháng, đặt mục tiêu rút ngắn 100% thời gian lập lịch sản xuất ca/ngày xuống dưới 15 giây.
• Vận hành cơ chế tái điều độ lai kết hợp cảm biến giám sát máy theo thời gian thực: Ban giám đốc nhà máy và phòng kế hoạch triển khai chu kỳ kiểm soát tiến độ định kỳ kết hợp ứng dụng thiết bị IoT trong lộ trình 9 tháng, nâng tỷ lệ giao hàng đúng hẹn đạt trên 95%.
• Đào tạo nâng cao năng lực điều phối xưởng linh hoạt: Phòng nhân sự tổ chức khóa huấn luyện thời lượng 1 tháng cho 100% đội ngũ kỹ sư điều độ và quản đốc phân xưởng về phương pháp phân công máy thay thế và quy trình phản ứng khi xảy ra sự cố thiết bị.

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

• Giám đốc nhà máy và Quản đốc phân xưởng sản xuất cơ khí, chế tạo khuôn mẫu: Tiếp cận phương pháp điều hành sản xuất tinh gọn, xử lý nhanh các sự cố chèn đơn hoặc hỏng máy mà không làm xáo trộn dây chuyền.
• Kỹ sư Quản lý Công nghiệp và Chuyên viên Hoạch định sản xuất: Sử dụng bộ quy tắc phân phối ODD và MR2 để thiết lập kế hoạch gia công tối ưu hàng ngày với độ trễ thấp nhất.
• Chuyên gia phát triển phần mềm ERP, MES và giải pháp chuyển đổi số công nghiệp: Khai thác mô hình toán học và giải thuật heuristic làm thuật toán lõi cho các phân hệ lập kế hoạch và điều độ nâng cao (APS).
• Học viên cao học, nghiên cứu sinh và giảng viên chuyên ngành Kỹ thuật Hệ thống Công nghiệp: Nắm bắt tài liệu học thuật giá trị về phương pháp luận tối ưu hóa đa mục tiêu và mô hình hóa bài toán điều độ động trong môi trường sản xuất linh hoạt.

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

Bài toán Job Shop linh hoạt khác biệt thế nào so với Job Shop truyền thống?

Trong mô hình Job Shop truyền thống, mỗi công đoạn gia công chỉ có thể thực hiện trên một máy cố định duy nhất. Đối với môi trường Job Shop linh hoạt, mỗi công đoạn có thể được xử lý trên nhiều máy thay thế khác nhau với thời gian gia công tương ứng, giúp nâng cao khả năng tận dụng thiết bị nhưng làm tăng độ phức tạp tính toán tổ hợp.

Vì sao nghiên cứu lại chọn tối ưu hóa đồng thời cả Makespan và Độ trễ lớn nhất?

Tối ưu Makespan giúp rút ngắn tổng thời gian chiếm dụng xưởng và tăng năng suất, trong khi tối ưu độ trễ lớn nhất trực tiếp bảo đảm uy tín giao hàng đúng hạn cho từng khách hàng. Việc tích hợp đồng thời 2 mục tiêu với trọng số cân bằng 50-50 giúp doanh nghiệp vừa đạt hiệu quả kinh tế nội bộ vừa duy trì chất lượng dịch vụ khách hàng.

Thuật toán Heuristic đề xuất có đáp ứng được tốc độ tính toán cho nhà máy lớn không?

Thuật toán chứng minh tính khả thi xuất sắc trong môi trường thời gian thực khi chỉ mất từ 1,07 giây cho quy mô 10 công việc và tối đa 13,91 giây cho bài toán lớn gồm 100 công việc trên 60 máy. Tốc độ này cho phép người quản lý tái lập lịch tức thì ngay khi phát sinh sự cố.

Cơ chế tái điều độ lai vận hành như thế nào khi xảy ra sự cố hư hỏng thiết bị?

Khi sự cố máy hỏng nghiêm trọng thuộc nhóm 1 xảy ra, hệ thống lập tức kích hoạt thuật toán tái điều độ toàn phần cho các công đoạn còn lại. Ngược lại, nếu sự cố nhỏ thuộc nhóm 2, hệ thống giữ nguyên phân công hiện tại và chỉ cập nhật lại lịch trình tại mốc chu kỳ định kỳ tiếp theo nhằm bảo đảm tính ổn định xưởng.

Doanh nghiệp vừa và nhỏ có thể ứng dụng giải pháp này trên máy tính thông thường không?

Hoàn toàn khả thi vì toàn bộ thuật toán được tối ưu hóa để chạy mượt mà trên máy tính văn phòng tiêu chuẩn trang bị chip xử lý Intel Core i5 và RAM 8GB. Doanh nghiệp không cần đầu tư máy chủ chuyên dụng đắt đỏ vẫn có thể vận hành hiệu quả thuật toán thông qua bảng tính Excel hoặc tích hợp vào hệ thống nội bộ.

Kết luận

• Xây dựng thành công mô hình toán học tối ưu hóa đa mục tiêu cho bài toán Job Shop linh hoạt, tích hợp đầy đủ ràng buộc thực tế về thời điểm phát hành đơn hàng và thời gian sẵn sàng của máy móc.
• Đề xuất thuật toán Heuristic C4 kết hợp luật ODD và MR2, mang lại độ lệch hiệu năng RPD tiệm cận 0% và rút ngắn thời gian tính toán xuống dưới 14 giây cho quy mô 100 công việc.
• Phát triển chiến lược tái điều độ lai dựa trên phân loại 3 nhóm sự kiện, giúp cắt giảm hơn 50% số lần xáo trộn lịch trình sản xuất so với phương pháp truyền thống.
• Cung cấp phương pháp luận thực nghiệm chuẩn mực trên 20 bộ dữ liệu quốc tế, sẵn sàng chuyển giao ứng dụng vào các hệ thống sản xuất thông minh thời đại 4.0.
• Lộ trình triển khai khuyến nghị kéo dài từ 1 đến 9 tháng, tạo giải pháp đột phá nâng cao năng lực cạnh tranh cho ngành cơ khí và chế tạo khuôn mẫu.

Bạn có thể liên hệ trực tiếp với tác giả hoặc tra cứu toàn văn luận văn tại thư viện Trường Đại học Bách Khoa - ĐHQG TP.HCM để tiếp cận chi tiết mô hình toán học và mã nguồn thuật toán tối ưu hóa sản xuất ngay hôm nay!

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

i ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA ---------------o0o--------------- TRẦN VÕ THẢO HƯƠNG ĐIỀU ĐỘ SẢN XUẤT ĐỘNG VÀ ĐA MỤC TIÊU TRONG MÔI TRƯỜNG JOB SHOP LINH HOẠT Chuyên ngành: Kỹ thuật Công nghiệp Mã số: 8520117 LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 01 năm 2020 ii VIETNAM NATIONAL UNIVERSITY - HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY ---------------o0o--------------- TRẦN VÕ THẢO HƯƠNG MULTI-OBJECTIVE PREDICTIVE-REACTIVE PRODUCTION SCHEDULING IN DYNAMIC FLEXIBLE JOB SHOP ENVIRONMENT Major: Industrial Engineering Major Index: 8520117 MASTER’S THESIS HO CHI MINH CITY, January 2020 iii Công trình được hoàn thành tại: Trường Đại học Bách Khoa – ĐHQG-HCM Cán bộ hướng dẫn khoa học: PGS. Lê Ngọc Quỳnh Lam Chữ ký: Cán bộ chấm nhận xét 1: TS. Đường Võ Hùng Chữ ký: Cán bộ chấm nhận xét 2: TS.

Nguyễn Hữu Thọ Chữ ký: Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh ngày 05 tháng 01 năm 2020. Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. Chủ tịch hội đồng: TS. Nguyễn Vạng Phúc Nguyên 2.

Thư ký hội đồng: TS. Ủy viên Phản biện 1: TS. Ủy viên Phản biện 2: TS. Nguyễn Hữu Thọ 5.

Ủy viên hội đồng: PGS. Đỗ Ngọc Hiền Xác nhận của Chủ tịch Hội đồng đánh giá Luận văn và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã được sửa chữa. CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA CƠ KHÍ TS. Nguyễn Vạng Phúc Nguyên PGS.

Nguyễn Hữu Lộc iv ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc ---------------------------- ------------------------------------ NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: TRẦN VÕ THẢO HƯƠNG MSHV: 1870027 Ngày, tháng, năm sinh: 02/08/1995 Nơi sinh: TP.HCM Chuyên ngành: Kỹ thuật Công nghiệp Mã số: 8520117 I. TÊN ĐỀ TÀI: - Tiếng Việt: Điều độ sản xuất động và đa mục tiêu trong môi trường Job shop linh hoạt. - Tiếng Anh: Multi-Objective Predictive-Reactive Production Scheduling in Dynamic Flexible Job Shop Environment. NHIỆM VỤ VÀ NỘI DUNG: - Xây dựng mô hình bài toán điều độ sản xuất trong môi trường Job shop linh hoạt.

- Đề xuất giải pháp cho bài toán để thỏa mãn các mục tiêu đặt ra ban đầu. - Đánh giá giải pháp đã đề xuất. NGÀY GIAO NHIỆM VỤ: Ngày 11 tháng 02 năm 2019 IV. NGÀY HOÀN THÀNH NHIỆM VỤ: Ngày 08 tháng 12 năm 2019 V.

CÁN BỘ HƯỚNG DẪN: PGS. LÊ NGỌC QUỲNH LAM Tp. HCM, ngày 05 tháng 02 năm 2020 CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN ĐÀO TẠO PGS. Lê Ngọc Quỳnh Lam PGS.

Đỗ Ngọc Hiền TRƯỞNG KHOA CƠ KHÍ PGS. Nguyễn Hữu Lộc v ACKNOWLEDGEMENTS I would like to express my special deep and sincere gratitude to my research advisor Assoc. PhD Le Ngoc Quynh Lam and my lecturer Assoc. PhD Do Ngoc Hien, Head of Department of Industrial Systems Engineering, Ho Chi Minh city University of Technology for giving me the opportunity to pursue Master degree and providing in time and invaluable support throughout this research.

Their guidance and constructive suggestions during planning and development process helped me to go on the right direction toward completion of research. I am also particularly grateful to all academic staff of Department of Industrial Systems Engineering and members of Faculty of Mechanical Engineering for their kind and understanding spirit and their encouragement in carrying out this research. Last but not the least, my sincere thank goes to my family for supporting me spiritually throughout my academic path as well as my life. TRẦN VÕ THẢO HƯƠNG vi TÓM TẮT Sự phát triển nhanh của các ngành công nghiệp sản xuất trong thời đại ngày nay và đặc biệt dưới ảnh hưởng của cuộc Cách mạng Công nghiệp 4.0, dẫn đến việc tổ chức sản xuất của các doanh nghiệp ngày càng hệ thống, tinh gọn, hiệu quả hơn và trở thành một trong những yếu tố quyết định để tạo được lợi thế cạnh tranh trên thị trường.

Trong sự phát triển đó, điều độ sản xuất đã và đang trở thành một trong những chức năng quan trọng giúp phân bổ hiệu quả các nguồn lực của tổ chức trong quá trình sản xuất đồng thời rút ngắn thời gian sản xuất, đảm bảo thời hạn đã cam kết với khách hàng. Nghiên cứu đặt ra trong luận văn này hướng đến việc đề ra một giải pháp thích hợp để giải quyết vấn đề điều độ sản xuất trong môi trường Job shop linh hoạt dưới sự ảnh hưởng của các yếu tố ngẫu nhiên, bất định. Hai mục tiêu giải pháp cần hướng đến đồng thời bao gồm cực tiểu thời gian hoàn thành tất cả các công việc (makespan) và cực tiểu thời gian trễ lớn nhất của các công việc. Để giải quyết được vấn đề, phương pháp điều độ predictive-reactive đã được sử dụng.

Đầu tiên bài điều độ tĩnh được xem xét nhằm đưa ra một lịch điều độ cụ thể với các điều kiện đầu vào có sẵn. Nếu chỉ dừng lại ở bước này, lịch điều độ đã tạo ra khi được triển khai tại xưởng sản xuất có thể sẽ bị gián đoạn hoặc trở nên không còn khả thi với sự xuất hiện của các yếu tố bất định như biến thiên về thời gian thực hiện các công đoạn hay những sự kiện bất ngờ như thêm công việc mới, hư hỏng máy, nguyên vật liệu cung cấp trễ. Vì vậy, một chiến lược tái điều độ được đề xuất giúp làm giảm bớt ảnh hưởng của các yếu tố này lên lịch điều độ, đồng thời vẫn phải giữ cho việc sản xuất được ổn định, tránh thay đổi liên tục. Các kết quả tính toán cho thấy giải thuật điều độ tĩnh cùng chiến lược tái điều độ đã đề xuất đáp ứng được các mục tiêu đã đề ra, có tính hiệu quả cao và có thể áp dụng cho các doanh nghiệp trong thực tế.

Từ khóa: Điều độ sản xuất, Job shop linh hoạt động, đa mục tiêu, điều độ predictive- reactive, tái điều độ theo sự kiện, tái điều độ theo chu kì. vii ABSTRACT These days, production scheduling becomes one of the most crucial functions in the production organizations with its supports in effectively resource consuming as well as completion time minimization. This thesis focuses mainly on finding out a predictive- reactive solution for the flexible job shop problem in a dynamic manufacturing environment. Two objectives considered simultaneously during the scheduling process are minimizing completion time and the maximal tardiness.

Firstly, a heuristic algorithm is proposed in order to generate a predictive schedule with using all the on-hand input information. In the real-world manufacturing, when implementing the predictive schedule in the shop floor, uncertain elements and unexpected events are unavoidable, cause disruptions and impact on the schedule performance. Therefore, a rescheduling strategy is mentioned in the reactive scheduling stage to help reduce the negative impacts and remain the shop floor stability. The hybrid method combining between event-driven rescheduling and periodic rescheduling is used in order to deal with the critical problem in this stage that is defining the time to reschedule.

The computational results indicate that the heuristic algorithm proposed for predictive scheduling and the rescheduling strategy proposed for reactive process are satisfied with research objectives, gives the high effectiveness and can be applied to real organizations of production field. Keywords: Production scheduling, flexible job shop environment, multi-objective problem, uncertainties, unexpected event, predictive-reactive scheduling, rescheduling. viii REASSURANCE I hereby declare that this is my own research. All the data and the results used in this research is honest and has not been published in other studies.

I will be totally responsible for my research if it is incorrect as mentioned above. The research’s author TRẦN VÕ THẢO HƯƠNG ix TABLE OF CONTENTS ACKNOWLEDGEMENTS. vii TABLE OF CONTENTS .ix LIST OF TABLES. xii LIST OF FIGURES.

xiii LIST OF NOTATIONS .1 Background and Motivation.1 Formulating the problem model .2 Proposing the algorithm for the predictive scheduling problem .3 Proposing the algorithm for the reactive scheduling problem .4 Evaluation and revision .6 Organization of the Thesis .1 Production Scheduling Overview .2 Production Scheduling Problem Model .2 Processing Characteristics and Constraints .3 Deterministic scheduling algorithm .4 Predictive-reactive scheduling. DETERMINISTIC PROBLEM FORMULATION .2 Mathematical model formulation .1 Proposed heuristic algorithm .1 The main procedure of proposed algorithm .2 Operation selection rule .3 Machine selection rule.2 Comparison of dispatching rules.3 The detailed steps of proposed algorithm .1 Defining the latest completion time of operation .2 Event classification method .3 Example on each type of event .1 Design of experiments. CONCLUSIONS AND RECOMMENDATIONS. 55 REFFERENCES APPENDIX A APPENDIX B APPENDIX C xii LIST OF TABLES Table 4.1 The results of combinations of OR and MR .2 The objective function values and RPDs of combinations .3 Computational time of the proposed algorithm.4 Numerical example – The input data .5 Numerical example – The initial status .6 Numerical example – The status at t = 2 .7 Numerical example – The status at t =3 .8 Numerical example – The result .1 Common types of event and their impacts .2 Defining successors of each operation .3 Defining critical operations .4 Event classification’s criteria .5 Processing time variations .6 Information of the new arrival job .2 The results of experiments.

53 xiii LIST OF FIGURES Figure 1.1 Four main stages of the research’s methodology .1 Diagram of information flow in a production system [1] .2 Types of scheduling algorithm .1 The mathematic model of researched problem .1 The main procedure of proposed algorithm .2 The RPDs of rule combinations .3 Box-plot diagram depicts the comparison of rule combinations .4 Numerical example – The Gantt chart .2 The AON network of the numerical example .3 Critical operations of the numerical example .5 Machine breakdown example .6 Delay in arrival example .7 Processing time variation example .1 RPD comparison between three rescheduling policies .2 The number of rescheduling times comparison between policies. 54 xiv LIST OF NOTATIONS FJSS Flexible Job Shop Scheduling problem ODD Operation Due time LC Latest Completion time of operation CPM Critical Path Method BP Backward Pass WINQ Total Work-content of jobs in Queue RPT Remaining Processing Time of machine PT Processing Time of operation AON Activity-on-node Network RSR Right-Shift Rescheduling 1 CHAPTER 1.1 Background and Motivation Nowadays, using effectively the workforce, making the most use of resources, minimizing the completion time of products… become the significant factors which help businesses gain the competitive advantages, especially in mold producing industry. Therefore, to achieve all of those elements, companies have been working and investing in production planning and scheduling. In addition, with the continuous improve of automated systems, it is strongly necessary to have effective schedules which support to reduce the production completion time and the delay of products.

Consequently, the field of production scheduling in various production environments have attracted a lot of researchers all over the world, in that Flexible Job Shop Scheduling Problem (FJSS) is the most complexible and attractive. FJSS aims to assign jobs on machines in order to achieve one or more production objectives. Like traditional Job shop scheduling, every job has various operations with its own predefined processing order. But in Flexible Job shop environment, each operation of a job can be processed on a set of machines instead of only one machine.

Therefore, solving the problem can be divided into two parts: choosing the machine that will process each operation and arranging the order of operations assigned on each machine.