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

Transportation Science - Tập 36 Số 1 - Trang 63-78 - 2002
Ananthapadmanabhan Narasimhan1, Udatta S. Palekar1
1Department of Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801

Tóm tắt

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ỉ.

Từ khóa

#transtainer #lập lịch #NP-Complete #nhánh và ranh giới #xấp xỉ #thuật toán.

Tài liệu tham khảo

Aslidis A. H. Management of technological change in the shipbuilding industry. (1987) . Unpublished Master's thesis, Center for Transportation Studies, MIT, Cambridge, MA

10.1016/S0166-218X(99)00245-0

10.1023/A:1018956823693

Botter R. C., 1991, Proc. IFIP 7th Internat. Conf. Comput. Appl. Automation of Shipyard Oper. and Ship Design VII, 217

10.1016/0360-8352(88)90020-4

Garey M. R., 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness

Imakita J., 1978, A Techno-Economic Analysis of the Port Transportation System

10.1016/S0360-8352(97)00219-2

10.1016/0360-8352(88)90045-9

Sabria F. Analysis of Potential Improvements in Port Operations. (1986) . Ph.D. thesis, University of California, Berkeley, CA

Shields J. J., 1984, Marine Tech., 4, 370

Thông tin
Thông tin xuất bản

Transportation Science

Tập 36 Số 1

63-78

Thông tin tác giả