Date of Award

12-15-2014

Document Type

Open Access Dissertation

Department

Civil and Environmental Engineering

First Advisor

Nathan Huynh

Abstract

To improve the competitiveness of marine container terminals, it is critical to minimize the makespan of a container vessel. The makespan is defined as the latest completion time among all handling tasks of the container vessel. Lower makespan (i.e. lower vessel turn time) can be achieved through better scheduling of the container handling equipment during vessel operations. The scheduling of terminal equipment is an operational problem, and a detailed schedule for each type of equipment operating in the terminal is necessary. Several studies have applied operations research techniques to optimize the processes of equipment in a terminal. This dissertation investigates three main operations in a marine container terminal, namely: quay crane scheduling, yard truck scheduling and yard crane scheduling. The first study in this dissertation addresses the quay crane scheduling problem (QCSP), which is known to be NP-hard. A genetic algorithm (GA) was developed and tested on several benchmark instances. An initial solution based on the S-LOAD rule, a new approach for defining the chromosomes, and new procedures for calculating tighter lower and upper bounds for the decision variables were used to improve the efficiency of the GA search. In comparison with best available solutions, our method was able to find optimal or near-optimal solution in significantly shorter time for larger problems. The second study of this dissertation addresses the quay crane scheduling problem with time windows (QCSPTW). A GA was developed to solve the problem. Unlike other works, the proposed solution approach allows quay cranes (QCs) to move in directions independent of one another, and in certain situations, the QCs are allowed to change their directions. Using benchmark instances, it was shown that the developed GA can provide near optimal solutions in a faster time for medium and large-sized instances and provides an improvement in the solution quality for instances with fragmented time windows. The equipment involved in each of three main operations of a container terminal are highly interrelated, and therefore, it is necessary to consider the operations of QCs, yard trucks (YTs), and yard cranes (YCs) in a holistic manner. The third study of this dissertation addresses the scheduling of QCs and YTs jointly. The integrated problem can be seen as an extension of the classical flow shop with parallel machines at each stage, which has been proved to be NP-hard. A mixed integer programming model was developed based on hybrid flow shop scheduling problem with precedence relationship between tasks, QC interference, QC safety margin, and blocking constraints. A GA combined with a greedy algorithm was developed to solve the problem. The GA solutions demonstrated that the developed integrated model is solvable within reasonable time for an operational problem. The fourth study of this dissertation developed a robust optimization model that considers all three equipment jointly. The unique difference between the fourth study and the existing literature is that it accounts for the non-deterministic nature of container processing times by the QCs, YTs, and YCs. To deal with the uncertainty in processing times, a model was formulated based on a recent robust optimization approach (p-robust). The objective function of the proposed model seeks to minimize the nominal scenario makespan, while bounding the makespan of all possible scenarios using the p-robustness constraints. To solve the robust integrated optimization model, a GA was developed. The experimental results demonstrated that the developed robust integrated model is solvable within reasonable time for an operational problem.

Rights

© 2014, Narges Kaveshgar

Download

Share

COinS