NGHIÊN CỨU LẬP LỊCH SẢN XUẤT LINH HOẠT CHO NGÀNH SƠN: ỨNG DỤNG MÔ HÌNH MILP VÀ THUẬT TOÁN HEURISTICS

Tóm tắt

Trong sản xuất công nghiệp hiện đại, lập lịch sản xuất là công cụ trung tâm để đảm bảo đơn hàng giao đúng hạn, giảm chi phí và nâng cao hiệu quả sử dụng nguồn lực. Ngành sơn bột tĩnh điện, với đặc thù quy trình nhiều công đoạn, nhiều máy song song và thời gian setup phụ thuộc trình tự, là một ví dụ điển hình của môi trường Flexible Flow Shop (FFS). Nếu lập lịch thủ công, doanh nghiệp thường phải đối diện với tỷ lệ giao trễ cao, máy móc hoạt động không đồng đều và chi phí setup lớn. Bài báo này đề xuất khung giải pháp hai tầng. Trước hết, mô hình toán Mixed Integer Linear Programming (MILP) được xây dựng để tìm nghiệm tối ưu cho bộ dữ liệu nhỏ và kiểm chứng mô hình. Tiếp đó, một thuật toán heuristics được thiết kế để xử lý dữ liệu lớn hơn, với mục tiêu rút ngắn thời gian tính toán và tạo lịch khả thi. Kết quả thực nghiệm tại Công ty AkzoNobel cho thấy MILP đạt makespan tối ưu với bộ dữ liệu nhỏ (5 công việc, 8 máy, 3 công đoạn), trong khi heuristics giải quyết thành công bộ dữ liệu lớn (41 công việc, 19 máy, 7 công đoạn) chỉ trong 14,6 giây. Kết quả nghiên cứu khẳng định sự bổ sung giữa hai phương pháp: MILP mang tính chuẩn mực, trong khi heuristics phù hợp ứng dụng thực tiễn. Hướng nghiên cứu tiếp theo gồm metaheuristics, tối ưu đa mục tiêu và lập lịch động theo dữ liệu thời gian thực

Title

A STUDY ON FLEXIBLE FLOW SHOP SCHEDULING IN THE PAINT INDUSTRY:APPLICATION OF MILP MODEL AND HEURISTICS ALGORITHM

Abstract

In modern manufacturing, scheduling is central to ensuring on-time delivery, reducing costs, and improving resource utilization. Powder coating production, characterized by multiple stages, parallel machines, and sequence-dependent setup times, represents a typical Flexible Flow Shop (FFS) environment. Manual scheduling often results in high tardiness rates, unbalanced machine loads, and excessive setup costs.
This paper proposes a two-layer solution framework. First, a Mixed Integer Linear Programming (MILP) model is developed to provide optimal solutions for small datasets and validate the model’s correctness. Then, a heuristics algorithm is designed to handle large-scale datasets, aiming to reduce computation time while generating feasible schedules. Experimental results from AkzoNobel show that MILP achieves optimal makespan on a small dataset (5 jobs, 8 machines, 3 stages), while the heuristics algorithm successfully schedules a large dataset (41 jobs, 19 machines, 7 stages) in only 14.6 seconds.
The findings highlight the complementary roles of MILP and heuristics: MILP provides optimal benchmarks, while heuristics ensures practical feasibility. Future research directions include hybrid metaheuristics, multi-objective optimization, and dynamic scheduling with real-time data.