Phân tích và Thuật toán cho Vấn đề Lập Lịch Transtainer trong Hoạt động Cảng Container

Vấn đề tối thiểu hóa thời gian dỡ hàng từ bãi chứa container lên tàu được gọi là vấn đề lập lịch transtainer. Chúng tôi trước tiên tiến hành điều tra lý thuyết về vấn đề này để hiểu rõ các tính chất cấu trúc của nó. Sau đó, chúng tôi sử dụng các kết quả này để chứng minh rằng vấn đề là NP-Complete. Vấn đề được định dạng thành một chương trình số nguyên. Một phương pháp liệt kê dựa trên nhánh và ranh giới được phát triển nhằm tìm ra một giải pháp chính xác cho vấn đề. Một thuật toán để giải quyết vấn đề ghép cặp trên một đường thẳng tại nút gốc của cây nhánh và ranh giới cũng được phát triển. Nhiều ranh giới thấp cũng được phát triển nhằm cắt giảm kích thước của cây. Một kết quả cho thấy không thể tồn tại một thuật toán xấp xỉ thời gian đa thức với trường hợp tồi tệ bị giới hạn trừ khi P = NP đã được chứng minh. Dựa trên kết quả này, một thuật toán xấp xỉ liệt kê với tỷ lệ hiệu suất trường hợp tồi tệ là 1.5 đã được thiết kế. Các bài kiểm tra tính toán trên các bài toán được tạo ngẫu nhiên được thực hiện để đánh giá các thuật toán chính xác và xấp xỉ.