Mô phỏng điều phối công việc

Điều phối công việc là gì?

Quy tắc điều độ là các thuật giải kinh nghiệm (heuristic) dựa trên độ ưu tiên để sắp xếp thứ tự gia công các công việc trên máy theo thời gian thực. Khác với các thuật toán lập lịch tối ưu vốn đòi hỏi phải biết trước toàn bộ thông tin của mọi công việc, quy tắc điều độ đưa ra quyết định cục bộ ngay khi mỗi máy trở nên sẵn sàng, nhờ đó rất thiết thực cho môi trường xưởng sản xuất luôn biến động.

Các quy tắc thông dụng gồm SPT (thời gian gia công ngắn nhất) giúp tối thiểu hóa thời gian lưu trình trung bình, EDD (ngày đến hạn sớm nhất) giúp tối thiểu hóa độ trễ hạn lớn nhất, và WSPT (thời gian gia công ngắn nhất có trọng số) giúp tối thiểu hóa thời gian lưu trình có trọng số. Không một quy tắc đơn lẻ nào vượt trội trên mọi tiêu chí hiệu năng — quy tắc tốt nhất phụ thuộc vào mục tiêu lập lịch.

Biểu đồ Gantt trực quan hóa dòng thời gian của lịch trình thu được, trong khi các chỉ số hiệu năng như makespan (tổng thời gian hoàn thành), tổng độ trễ hạn (tổng mức giao hàng trễ) và thời gian lưu trình trung bình lượng hóa chất lượng của lịch trình. So sánh nhiều quy tắc trên cùng một tập công việc sẽ cho thấy quy tắc nào phù hợp nhất với mục tiêu hiện tại.

Formula: SPT: Sort by processing time (ascending) LPT: Sort by processing time (descending) EDD: Sort by due date (ascending) CR: Sort by (Due Date - Now) / Processing Time WSPT: Sort by Weight / Processing Time (descending) Tardiness = max(0, Completion Time - Due Date)

Ví dụ tính toán

3 công việc: A(p=4, d=10), B(p=2, d=8), C(p=6, d=12). Thứ tự SPT: B→A→C, thời điểm hoàn thành: 2, 6, 12, độ trễ hạn: 0+0+0=0. Thứ tự EDD: B→A→C (giống như trên), độ trễ hạn=0. Thứ tự LPT: C→A→B, thời điểm hoàn thành: 6, 10, 12, độ trễ hạn: 0+0+4=4. Ở đây SPT là tối ưu.

Khi nào sử dụng máy tính này

• Khi đánh giá quy tắc điều phối nào giảm thiểu tổng trễ cho hỗn hợp công việc hiện tại trước khi triển khai trên xưởng
• Trong cuộc họp lập kế hoạch sản xuất để mô phỏng các quy tắc ưu tiên khác nhau sẽ sắp xếp hàng đợi công việc hiện tại như thế nào
• Khi đào tạo giám sát xưởng về đánh đổi giữa các chiến lược điều phối khác nhau và tác động đến hiệu suất giao hàng
• Sau gián đoạn lịch trình (hỏng máy, đơn hàng gấp) để sắp xếp lại công việc còn lại và giảm thiểu tác động giao hàng
• Khi so sánh các quy tắc lập lịch heuristic để chọn quy tắc tốt nhất cho đặc điểm job shop lặp lại

Những sai lầm thường gặp

• Sử dụng SPT để giảm thiểu trễ — SPT giảm thiểu thời gian lưu trung bình, không phải trễ; sử dụng EDD cho giảm thiểu trễ tối đa hoặc quy tắc trễ có trọng số cho mục tiêu tập trung ngày đến hạn
• Mặc định áp dụng FCFS vì nó có vẻ 'công bằng' — FCFS thường tạo hiệu suất tệ nhất trên hầu hết mọi chỉ số; chỉ nên sử dụng khi ưu tiên công việc thực sự bằng nhau và thứ tự quan trọng
• Không cập nhật quyết định điều phối khi điều kiện thay đổi — quy tắc điều phối nên được đánh giá lại khi có công việc mới, hủy công việc hoặc hỏng máy
• Bỏ qua trọng số công việc khi ưu tiên khác nhau — nếu một số công việc quan trọng hơn (khách hàng giá trị cao, điều khoản phạt), sử dụng WSPT hoặc CR thay vì SPT hoặc EDD đơn giản

Cách diễn giải kết quả

• Trên một máy đơn với tất cả công việc được giải phóng tại thời điểm 0, makespan là như nhau với mọi quy tắc (máy không bao giờ nhàn rỗi) — hãy đánh giá quy tắc bằng Tổng trễ, không phải makespan; makespan chỉ khác nhau khi thời gian đến tạo ra các khoảng nhàn rỗi
• Tổng trễ bằng 0 nghĩa là mọi công việc đều đúng hạn giao theo quy tắc đó — kiểm tra biểu đồ Gantt xem còn bao nhiêu dư địa trước hạn giao để đánh giá độ bền vững trước gián đoạn
• Trong chế độ So sánh tất cả quy tắc, chọn quy tắc có tổng trễ thấp nhất cho tổ hợp công việc của bạn — khi nhiều quy tắc bằng nhau, ưu tiên quy tắc đơn giản hơn (ví dụ EDD thay vì CR) để thực thi tại xưởng
• Dùng cột trễ theo từng công việc để tìm các đơn hàng cụ thể bị trễ — nếu một công việc trễ chiếm phần lớn tổng số, đàm phán lại một hạn giao duy nhất có thể hiệu quả hơn việc đổi quy tắc điều phối
• WSPT chỉ khác SPT khi trọng số công việc khác nhau, và CR chỉ khác EDD khi thời gian xử lý biến thiên tương đối so với dư địa hạn giao — nếu kết quả giống hệt nhau giữa các quy tắc, dữ liệu công việc của bạn có thể chưa khai thác các đầu vào đó

Tiêu chuẩn & Tài liệu tham khảo liên quan

• APICS CPIM Body of Knowledge — Mô-đun kiểm soát hoạt động sản xuất bao gồm quy tắc điều phối và lập lịch xưởng
• ISA-95 (IEC 62264) — Tiêu chuẩn tích hợp hệ thống doanh nghiệp-kiểm soát định nghĩa phân cấp chức năng lập lịch và điều phối

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

Tôi nên sử dụng quy tắc điều độ nào?

Điều đó phụ thuộc vào mục tiêu của bạn. SPT tối thiểu hóa thời gian lưu trình trung bình và lượng bán thành phẩm tồn trên chuyền. EDD tối thiểu hóa độ trễ lớn nhất (tốt nhất khi cần đáp ứng thời hạn gấp nhất). WSPT là tối ưu để tối thiểu hóa thời gian hoàn thành có trọng số khi các công việc có mức ưu tiên khác nhau. CR (tỷ số tới hạn) thích ứng linh hoạt theo thời điểm hiện tại. Với hầu hết các xưởng, hãy thử nhiều quy tắc rồi so sánh các chỉ số.

Tại sao không dùng thuật toán lập lịch tối ưu thay cho quy tắc điều độ?

Lập lịch tối ưu (ví dụ nhánh cận, quy hoạch nguyên hỗn hợp MIP) là NP-khó với hầu hết bài toán thực tế — thời gian tính toán tăng theo cấp số mũ khi số lượng công việc tăng. Quy tắc điều độ chạy trong thời gian O(n log n) và có thể xử lý công việc đến bất chợt, sự cố máy móc cũng như thay đổi ưu tiên ngay trong thời gian thực. Trên thực tế, các quy tắc điều độ tinh vi cho kết quả chỉ cách lời giải tối ưu khoảng 5-15% với phần lớn bài toán.