NGHIÊN CỨU BÀI TOÁN PHÂN CÔNG LỊCH TRÌNH TÁC VỤ, CÔNG NHÂN VÀ TRẠM TRÊN DÂY CHUYỀN LẮP RÁP ĐA CÔNG NHÂN

Tóm tắt

Bài báo tập trung nghiên cứu giải quyết bài toán lập lịch dây chuyền lắp ráp đa công nhân với mục tiêu cải thiện hiệu suất của dây chuyền. Bài toán được tiếp cận bằng mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) nhằm thể hiện các quan hệ thứ tự ưu tiên, khả năng của các trạm, và tính khả thi giữa công nhân và tác vụ. Do MILP trở nên tốn kém về mặt tính toán đối với các trường hợp có quy mô vừa và lớn nên thuật toán di truyền (GA) được đề xuất để có được các giải pháp gần tối ưu với thời gian chạy ngắn hơn đáng kể. Xác thực trên các tập dữ liệu chuẩn nhỏ cho thấy cả MILP và GA đều tạo ra các lịch trình khả thi đáp ứng tất cả các ràng buộc, chứng minh tính chính xác của các công thức và toán tử. Các thí nghiệm tính toán tiếp theo chỉ ra rằng trong khi MILP đạt được tính tối ưu cho các trường hợp nhỏ, GA cung cấp các giải pháp chất lượng cao và hiệu suất có thể mở rộng cho các trường hợp thử nghiệm lớn hơn. Kết quả nhấn mạnh tính hiệu quả của việc kết hợp tối ưu hóa chính xác và heuristic để giải quyết các vấn đề lập lịch trình phức tạp cho dây chuyền lắp ráp nhiều người nhằm giảm thiểu thời gian hoàn thành.

 

Title

TASK-WORKER-STATION ASSIGNMENT AND SCHEDULING ON MULTIMANNED ASSEMBLY LINES

Abstract

The paper investigates the Multi-Manned Assembly Line Scheduling Problem (MALSP), where multiple workers operate concurrently at each station with the goal of improving the productivity of the line. The problem is approached by a mixed integer linear programming (MILP) model to capture the relations of precedence, station capabilities, and feasibility between workers and tasks. Since MILP becomes computationally expensive for medium and large-scale instances, Genetic Algorithm (GA) is proposed as a heuristic approach to obtain near optimal solutions with signifcantly shorter running time. Validation on small benchmark datasets shows that both the MILP and GA produce feasible schedules that satisfy all constraints, demonstrating the correctness of the formulations and operators. Further computational experiments indicate that while the MILP achieves optimality for small instances, the GA provides high-quality solutions and scalable performance for larger tests. The results underscore the effectiveness of combining exact optimization and metaheuristics to solve complex multi-manned assembly line scheduling problems aimed at minimizing makespan.