1、 1 附录 英文原文 Crane Scheduling with Spatial Constraints Andrew Lim, Brian Rodrigues, Fei Xiao, and Yi Zhu 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 assu
2、me that cranes cannot cross, there is a minimum distance between cranes and jobs cannot be done simultaneously. The objective is to nd a crane-to-job matching which maximizes throughput under these constraints. We provide dynamic programming algorithms, a probabilistic tabu search and a squeaky whee
3、l 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. 1 Introduction The Port of Singapore Au
4、thority (PSA) is a large port operator located in Singapore, one of the busiest ports in the world. PSA handles 17.04 million TEUs annually or nine percent of global container trac in Singapore, the worlds largest transshipment hub. PSA is concerned with maximizing throughput at its port due to limi
5、ted 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 trac lanes, intersections, and vehicle
6、ow control systems. In this multi-channel interface we are likely to nd 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-an
7、alyzed port activity, queuing theory has been used widely. Trac and vehicle-ow 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.Th
8、e 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 eciency. This constituted an open shop parallel and identical machines problem, where jobs consist of independen
9、t, 2 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 aecting crane operations are absent in studies available on the subject
10、. Such constraints aect 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 exibility in perfor
11、ming 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
12、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 Descript
13、ion During the time ships are berthed, various cargo-handling equipment is used to unload cargo, mostly in the form of containers. Dierent types of cargo require dierent handling and many ports have bulk, container, dry and liquid-bulk terminals. Cargo that is containerized can be loaded and unloade
14、d in a fewer number of moves by cranes operating directly over ship holds or by crane arms moving over holds or deck areas. Cargo stacked in yards is moved by cranes onto movers and transported for loading onto ships. Cargo here comprises containers of dierent capacities, which, whether in ships or
15、in yards, are parcelled into xed areas for access to cranes. For example, cargo placed in specic holds or deck sections on ships, or in sections within yards. Containers are unloaded from ships by quay cranes onto movers or trailers which carry them to assigned yard locations where they are loaded o
16、nto stacks by yard cranes. Containers destined for import are set aside, and restacking, if required, is carried out. In the movement of containers, sequencing is crucial because containers are stored in stacks in the ship and on the yard and lanes may be designated to specic trailers at certain tim
17、es. In addition, the movement of containers involves routing and crane operations where timings may be uncertain. In fact, crane scheduling is one activity among many that determine the movement of containers. Other such activities include 3 berthing, yard storage, ship stowage and vehicle allocatio
18、n and routing, all of which can be uncertain. Because of the uncertainty present over all activities, it is almost impossible to implement a plan over any length of time. This diculty is present in scheduling cranes. For example, although a set of jobs may be assigned to a certain crane, it may not
19、be possible for the crane to complete processing a job in this set onto movers once it was known that the route these movers are to take was congested. As another example, although we can specify that jobs bound for the same yard space are not unloaded from ships simultaneously, we cannot expect suc
20、h containers to be unloaded at a time other than the allotted time interval, since a required resource to complete the job may become unavailable after this time, as for example, if the yard crane becomes unavailable. In view of the dynamically changing environment, a central control devises and mai
21、ntains a job assignment plan that is periodically updated in order to coordinate operations, including crane scheduling. The system will allocate all jobs and resources periodically. In the port we studied, a job parcel can include a number of ships and a number of cranes together with jobs. Typical
22、ly, there can be up to ve ships with four to seven cranes per ship and a number of jobs depending on the size and conguration of ships. Jobs have a prot value assigned to them and resources, e.g., cranes, movers, lanes etc., are assigned to each of the jobs depending on their value to the overall op
23、erations plan which aims to optimize total throughput. When an assignment plan is updated, the central system reassesses the current state of operations to regroup and reassign job parcels. Because of this, time is accommodated by constant adjustments of job parcels and assignments based on the curr
24、ent state of all operations. Hence, once jobs and resources are assigned for the time period no update is necessary. Jobs come in dierent sizes, and cranes have dierent handling capacities. Since we make the assumption that any crane assigned to a job completes it, the throughput or prot, for a give
25、n crane-to-job assignment, is a xed value independent of other crane-to-job assignments. The problem is naturally represented by a bipartite graph matching problem when we take cranes and jobs to be the vertices and dene the weights of connecting edges to be crane-to-job throughput. This representation is shown in Figure 1.
