Approaches and algorithms to solve generalized crane scheduling problems at cargo terminals

Multi-modal cargo container ports and trans-shipment terminals serve as the back-bone of major transportation networks by fulfilling several requirements of cargo handling. Terminal management systems (stevedores) ensure an efficient utilization of resources at the port so that the intended cargo is handled within time and the overall cost is minimized. The demands on throughput of these terminals are increasing in conjunction with the the complexity of cargo operations. Such factors necessitate the development of suitable models, algorithms and techniques to decide the allocation, scheduling or sequencing of operations at cargo terminals. The motivation behind the current research is to optimise the scheduling of operations at cargo terminals, resulting in economical, sustainable and profitable transportation of cargo. A typical cargo terminal is expected to handle around 100-500 containers on a single day utilizing several (non-uniform) resources. The availability of the required resources and/or the movement of containers is often restricted by time window bounds. Then, suitable resources must be allocated via a plan, time-table or roster so as to execute the required activities. The allocation of any resource to any task(s) entails many different types of variable costs. The objective of minimizing the overall costs (while accomplishing all prescribed activities) leads to several interesting optimization problems. While some of these problems have been studied earlier in the operations-research literature, several novel interesting questions are as yet unanswered. The current research identifies and formally defines these new problems, establishes their computational complexity and thereafter presents suitable mathematical models and algorithms to solve them. We focus on the utilization of resources (machines,cranes or personnel) that shall facilitate any required internal rearrangement of cargo containers within the terminal itself. Apart from the primary motivation of optimising the cargo handling within terminals, many techniques developed within this research are equally applicable in the broader context of resource planning and task allocation for routing and scheduling applications. Consider the routes taken by cranes as they traverse the specific identified locations within the terminal to pick up and deliver containers. Mathematically, this sequence dependence leads to an NP-hard problem that overlaps the well studied domains of vehicle routing problems (VRP) and job scheduling problems (JSP). Determination of routes with immediate sequence dependence is just one of the many considerations at container terminals. The stacking of containers in several different columns or heaps adds a very novel dimension to our discussion. The trans-location of any specific container (which is within some stack) requires rearrangement of other containers in the origin stack at the pickup location of the desired container. The effort involved in such a rearrangement depends on the complete history of all related containers that have been moved until that time. The resulting costs differ substantially from the immediate sequence dependent efforts in crane routing. Even if we neglect the horizontal movement costs (on routes), disregard the time window restrictions and relax all other side constraints, the remaining (reduced) problem is still NP-hard. Conversely, if we neglect the horizontal movement costs (on routes) and also the stack rearrangement efforts, the allocation of fixed interval operations to a set of non-uniform resources constitutes another NP-hard allocation problem. Thus, the crane scheduling problem is a combination of the following constituent problems: 1. Container stack rearrangement problem based on general precedence 2. Crane route minimization problem based on immediate precedence 3. Interval scheduling problem for multiple resources 4. Routing problem (or job scheduling) with time windows In conjunction with each other, these diverse features present an interesting computational challenge. Our approach to solving the overall scheduling problem is to initially model every individual sub-problem separately. Building upon our understanding of these separate constituents, we design integer programming formulations to solve the overall (combined) problem. Our primary hypothesis in these formulations is: any decisions made based on one model (say stacking) impose strong constraints on some other model (say routing). So we design algorithms that effectively integrate or synthesize multiple loosely interconnected models. We begin by exclusively analyzing the stack rearrangement efforts required when containers are piled up over each other in columns. To model the general (history dependent) precedence of container stack rearrangement, we introduce a new decision variable. This new variable captures decisions of whether or not a pair of tasks may be executed in a particular sequential order by any resource. While immediate precedence (path traversal) variables have been commonly used in routing problem, our general precedence variable does not seem to have been used earlier in relevant literature. Based on this new decision variable, we propose several new techniques (exact and heuristic) to model and optimize the stack rearrangement efforts. We also construct new families of problem data instances to capture the practical scenario expected in cargo terminals and hence demonstrate the applicability of our techniques. Combination of the immediate precedence sequence effects (from crane routing) along with the general history dependence effects (from stack rearrangement) leads to a more interesting problem. Even neglecting time window restrictions and the heterogeneity of multiple cranes, the resulting problem still involves several critical issues regarding crane operations at container terminals. We develop many new integer programming formulations to solve this problem, but find that the standard approaches are incapable of handling larger sized problem data instances. Hence we design a new approach: we employ two separate integer programming formulations for the representing the crane routing and the container stacking. Thereafter, we interconnect the two formulations to yield crane routes that optimize the total costs. A rigorous computational comparison of this approach allows us to finalize the best formulation and the tightest constraints for use in subsequent procedures which also address some side constraints. Efficient utilization of heterogeneous resources for executing several time-bound tasks is studied in the domain of ’Interval scheduling problems’. Fixed interval scheduling problems concern the allocation and assignment of non-uniform resources to execute tasks of fixed time intervals. The current research develops new cuts and a decomposition scheme that solves larger sized fixed interval scheduling problems. This decomposition scheme involves deduction of an initial minimal set of resources expected to be necessary (but possibly not sufficient) for all the prescribed tasks. In the next stage, we attempt to find the sub-sets of tasks which could not be executed within the selected minimal set of resources. This enables the discovery of new feasibility cuts which are subsequently used to find a corrected set of sufficient resources. The recursive application of this procedure leads to an improved minimal set of resources which is proved to be necessary and sufficient (i.e. optimal) for the given tasks. This decomposition scheme forms the basis of the solution procedure that we shall eventually propose for the overall crane scheduling problem. Our decomposition scheme also applies to several other problems in the interval scheduling domain. We demonstrate the efficacy of our procedures by solving standard problem data instances in the interval scheduling literature and also design new (more complex) problems with inter-task variability factors. The overall problem to be solved for efficient scheduling of cranes at cargo container terminals involves a combination of multiple resources, time-bound tasks, immediate precedence based costs and general (history) precedence based efforts. We address the unified problem by combining the formulations, algorithms and approaches developed for all the sub-problems discussed earlier. We use the precedence governing decision variables of history dependent scheduling. We continue to employ an aggregation of loosely inter-connected integer programming formulations. We rely upon the decomposition scheme designed for time restricted routing problems that we used in interval scheduling. The overall procedure presented here is robust enough to solve the entire range of crane scheduling problems within the scope of our research within reasonable computational efforts. Thesis submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy at the Indian Institute of Technology Bombay, India and Monash University, Australia.