TAILIEUCHUNG - Thuật Toán Và Thuật Giải part 1

Bài toán phân việc – ứng dụng của nguyên lý thứ tự Một công ty nhận được hợp đồng gia công m chi tiết máy J1, J2, Jm. Công ty có n máy gia công lần lượt là P1, P2, Pn. Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy, công việ sẽ tiếp tục cho đến lúc hoàn thành | - Bài toán phân việc - ứng dụng của nguyên lý thứ tự Một công ty nhận được hợp đồng gia công m chi tiết máy J1 J2 . Jm. Công ty có n máy gia công lần lượt là Pb P2 . Pn. Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy công việ sẽ tiếp tục cho đến lúc hoàn thành không thể bị cắt ngang. Để gia công một việc J1 trên một máy bất kỳ ta cần dùng một thời gian tương ứng là t1. Nhiệm vụ của công ty là phải làm sao gia công xong toàn bộ n chi tiết trong thời gian sớm nhất. Chúng ta xét bài toán trong trường hợp có 3 máy P1 P2 P3 và 6 công việc với thời gian là t1 2 t2 5 t3 8 t4 1 t5 5 t6 1. ta có một phương án phân công L như hình sau Theo hình này tại thời điểm t 0 ta tiến hành gia công chi tiết J2 trên máy P1 J5 trên P2 và J1 tại P3. Tại thời điểm t 2 công việc J1 được hoàn thành trên máy P3 ta gia công tiếp chi tiết J4. Trong lúc đó hai máy P1 và P2 vẫn đang thực hiện công việc đầu tiên mình . Sơ đồ phân việc theo hình ở trên được gọi là lược đồ GANTT. Theo lược đồ này ta thấy thời gian để hoàn thành toàn bộ 6 công việc là 12. Nhận xét một cách cảm tính ta thấy rằng phương án L vừa thực hiện là một phương án không tốt. Các máy P1 và P2 có quá nhiều thời gian rãnh. Thuật toán tìm phương án tối ưu L0 cho bài toán này theo kiểu vét cạn có độ phức tạp cỡ O mn với m là số máy và n là số công việc . Bây giờ ta xét đến một thuật giải Heuristic rất đơn giản độ phức tạp O n để giải bài toán này. Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công. Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời gian nhất. Với tư tưởng như vậy ta sẽ có một phương án L như sau Rõ ràng phương án L vừa thực hiện cũng chính là phương án tối ưu của trường hợp này vì thời gian hoàn thành là 8 đúng bằng thời gian của công việc J3. Ta hy vọng rằng một giải Heuristic đơn giản như vậy sẽ là một thuật giải tối ưu. Nhưng tiếc thay ta dễ dàng đưa ra được một trường hợp mà thuật giải Heuristic không đưa ra được kết quả tối

• Kỹ thuật lập trình
• máy tính
• mạng máy tính
• internet
• phần mềm
• ứng dụng
• lập trình
• dữ liệu
• SQL
• PHP
• AutoIT
• Phần cứng máy tính
• lắp ráp máy tính
• sửa chữa máy tính
• lỗi máy tính
• hệ thống mạch máy tính
• điện máy tính
• Tài liệu máy tính