Abstract ：In this work, we examine port crane scheduling with spatial and separation constraints. Although common to most port operations, these constraints have not been previously studied. We assume that cranes cannot cross, there is a minimum distance between cranes and jobs cannot be done simultaneously. The objective is to find a crane-to-job matching which maximizes throughput under these constraints. We provide dynamic programming algorithms, a probabilistic tabu search and a squeaky wheel optimization heuristic for solution. Experiments show the heuristics perform well compared with optimal solutions obtained by CPLEX for small scale instances where a squeaky wheel optimization with local search approach gives good results within short times.48805

Key words : crane ， schedule ， spatial ， constraint

1  Introduction

The Port of Singapore Authority (PSA) is a large port operator located in Singapore, one of the busiest ports in the world. PSA handles 17.04 million TEU’s annually or nine percent of global container traffic in Singapore, the world’s largest transshipment hub. PSA is concerned with maximizing throughput at its port due to limited port size, high cargo transshipment volumes and limited physical facilities and equipment . Crane scheduling and work schedules are critical in port management since cranes are at the interface between land and water sections of any port, each with its own traffic lanes, intersections, and vehicle flow control systems. In this multi-channel interface we are likely to find bottlenecks where cranes and other cargo-handling equipment (forklifts, conveyors etc.) converge.

Sabria and Daganzo studied port operations which focused on berthing and cargo-handling systems. In berthing, which is a widely-analyzed port activity, queuing theory has been used widely. Traffic and vehicle-flow scheduling on land in ports has also been well studied. Danganzo studied a static crane scheduling case where cranes could move freely from hold to hold and only one crane is allowed to work on one hold at any one time.The objective was to minimize the aggregate cost of delay. In [13], container handling is modelled as “work” which cranes perform at constant rates and cranes can interrupt work without loss of efficiency. This constituted an “open shop” parallel and identical machines problem, where jobs consist of independent, single-stage and pre-emptable tasks. A branch- and-bound method was used to minimize delay costs for this problem. Crane scheduling has also been studied in the manufacturing environment context .

Commonly-found constraints affecting crane operations are absent in studies available on the subject. Such constraints affect crane work scheduling and need to be factored into operational models. These include the basic requirement that operating cranes do not cross over each other. Also, a minimum separating distance between cranes is necessary since cranes require some spatial flexibility in performing jobs. Finally, there is a need for jobs arriving for stacking at yards to be separated in arrival time to avoid congestion.

We found that operational decision-making at PSA was based largely on experience and simulation techniques. While the latter is of value, analytic models are an advantage and are not limited by experience-generated rules-of-thumbs or simulation. The object of this work is to address the need for such models which take into account common spatial and separation requirements in the scheduling cranes. This work augments Peterkofsky and Daganzo study .

2  Problem Description

During the time ships are berthed, various cargo-handling equipment is used to unload cargo, mostly in the form of containers. Different types of cargo require different handling and many ports have bulk, container, dry and liquid-bulk terminals. Cargo that is containerized can be loaded and unloaded in a fewer number of moves by cranes operating directly over ship holds or by crane arms moving over holds or deck areas. 起重机调度与空间限制英文文献和中文翻译:http://www.751com.cn/fanyi/lunwen_51516.html