Scheduling — Lập lịch sản xuất
Một trong số ít bài toán lập lịch có lời giải tối ưu chứng minh được. Nhập thời gian gia công, nhận thứ tự tối ưu và mức tiết kiệm so với thứ tự bạn đang chạy.
Trục ngang là vị trí trong hàng đợi, không phải tên việc — hai đường xếp cùng số việc theo hai thứ tự khác nhau. Điểm cuối của mỗi đường là makespan.
Cùng bộ việc, cùng máy móc, chỉ đổi thứ tự. Đây là mức cải thiện không tốn một đồng đầu tư nào.
Cận dưới là tổng thời gian của máy bận nhất. Không lịch nào ngắn hơn được; khoảng cách còn lại là thời gian máy 2 buộc phải chờ ở đầu và máy 1 nghỉ ở cuối.
Muốn giảm tiếp phải rút ngắn việc đầu tiên trên máy 1 hoặc cho phép chen việc — cả hai đều nằm ngoài mô hình hai máy này.
Thêm máy thứ ba là bài toán NP-khó và quy tắc Johnson không còn đảm bảo tối ưu. Đừng suy rộng kết quả này cho chuyền dài.
| Thứ tự tối ưu | B → F → D → C → E → A |
| Máy 1 tổng | 30.00 |
| Máy 2 tổng | 32.00 |
| Thời gian máy 2 chờ | 1.00 |
| Quy tắc | Việc có min ở máy 1 → xếp đầu; min ở máy 2 → xếp cuối |
Trục ngang là vị trí trong hàng đợi, không phải tên việc — hai đường xếp cùng số việc theo hai thứ tự khác nhau. Điểm cuối của mỗi đường là makespan.
Quy tắc xếp việc nhanh ở máy 1 lên đầu để máy 2 có hàng sớm, và để việc nhanh ở máy 2 xuống cuối để máy 1 không phải chờ ở đoạn kết.
Tổng chờ 1.00 đơn vị, gần hết dồn vào việc đầu tiên vì máy 2 không thể bắt đầu trước khi máy 1 xong việc đó. Đó là phần không thể loại bỏ bằng cách xếp lại thứ tự.
| Việc | Máy 1 bắt đầu | Máy 1 xong | Máy 2 bắt đầu | Máy 2 xong | Máy 2 chờ |
|---|---|---|---|---|---|
| B | 0.00 | 1.00 | 1.00 | 7.00 | 1.00 |
| F | 1.00 | 3.00 | 7.00 | 12.00 | 0.00 |
| D | 3.00 | 6.00 | 12.00 | 20.00 | 0.00 |
| C | 6.00 | 15.00 | 20.00 | 27.00 | 0.00 |
| E | 15.00 | 25.00 | 27.00 | 31.00 | 0.00 |
| A | 25.00 | 30.00 | 31.00 | 33.00 | 0.00 |
| Thứ tự tối ưu | B → F → D → C → E → A |
| Máy 1 tổng | 30.00 |
| Máy 2 tổng | 32.00 |
| Thời gian máy 2 chờ | 1.00 |
| Quy tắc | Việc có min ở máy 1 → xếp đầu; min ở máy 2 → xếp cuối |
Johnson (1954): min ở máy 1 → xếp đầu, min ở máy 2 → xếp cuối
Đây là công thức thật mà mã nguồn chạy, không phải mô tả gần đúng.
API tại /api/v1/tools/johnson-schedule gọi đúng hàm
này, nên kết quả trên trang và qua API không thể lệch nhau.
1.234.567 lẫn 1.234,56.Lập lịch sản xuất quyết định đơn hàng nào chạy trên máy nào vào lúc nào. Đây là lớp bài toán NP-khó, nên thực tế dùng heuristic tốt hơn là đợi lời giải tối ưu tuyệt đối.
| Makespan | tổng thời gian hoàn thành toàn bộ |
| Tardiness | tổng số ngày trễ hạn |
| Số lần chuyển đổi | chi phí ẩn lớn nhất |
Phần quan trọng nhất của trang này. Một phương pháp được mô tả mà không nói chỗ nó hỏng là phiên bản quảng cáo của phương pháp đó.
Chưa có mô hình nào gắn riêng cho chủ đề này. Đây là những mô hình của cả ngành — liên quan ở cấp ngành, không phải cấp chủ đề.
Lập lịch sản xuất quyết định đơn hàng nào chạy trên máy nào vào lúc nào. Đây là lớp bài toán NP-khó, nên thực tế dùng heuristic tốt hơn là đợi lời giải tối ưu tuyệt đối.
1. Chọn quy tắc ưu tiên phù hợp mục tiêu: EDD cho đúng hạn, SPT cho giảm thời gian chờ trung bình. 2. Nhóm các đơn cùng loại để giảm số lần chuyển đổi. 3. Chừa đệm thời gian cho biến động thay vì lập lịch kín 100%. 4. Lập lịch lại theo sự kiện, không theo chu kỳ cố định.
L ị c h t ố i ư u l ý t h u y ế t v ỡ n g a y k h i c ó m ộ t m á y h ỏ n g ; l ị c h b ề n v ữ n g q u a n t r ọ n g h ơ n l ị c h t ố i ư u .
Makespan — tổng thời gian hoàn thành toàn bộ; Tardiness — tổng số ngày trễ hạn; Số lần chuyển đổi — chi phí ẩn lớn nhất.
Chưa xây dựng. Mục này hiện là điều hướng và tài liệu tham chiếu; chúng tôi không gắn nhãn 'live' cho thứ chưa chạy.