A quadratic assignment/linear programming approach to ship scheduling for the U.S. Coast Guard.
Loading...
Authors
Sibre, Charles Edwin
Subjects
Ship Scheduling
Quadratic Assignment
Linear Programming
Optimization (large scale)
Quadratic Assignment
Linear Programming
Optimization (large scale)
Advisors
Brown, Gerald G.
Bradley, Gordon Hoover
Graves, G.W.
Date of Issue
1977-06
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
As part of the management planning and control function, the U.S. Coast Guard's Pacific Area Commander schedules the operational missions for all High Endurance Cutters in the Pacific Area. To provide a powerful management tool to assist this scheduling process, an analytic model for this large scale problem has been developed and implemented. It contains mission requirements, restricted sequencing of missions, ships' physical limitations and crews' morale-related considerations. The modeling approach is based on the Geoffrion-Graves model for parallel production lines with significant changeover costs. The implementation solves a large (860 row) Koopmans-Beckmann fixed charge Quadratic Assignment model using a new method with an advanced, feasible starting solution provided by an imbedded network (with 1,720 nodes and 739,600 arcs). Many linear programming problems (200 row, 450 variable) are then solved with a linear programming subroutine of advanced design. The resulting model and these implementation techniques produce excellent quality working schedules with very reasonable execution time and memory requirements. Alternative solutions are easily generated
Type
Thesis
Description
Series/Report No
Department
Computer Science
Operations Research
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.