起重机调度与空间限制英文文献和中文翻译(9)

菜单

• Because of the range of local search solutions, we can select neighbors based on diﬀerent criteria so that the chance of getting trapped in a cycle is reduced greatly. We can also combine randomization techniques in local search.

• In many cases, local search can identify tasks that can be sacriﬁced to obtain a higher evaluation solutions. .

To illustrate the SWO with local search heuristic when applied to the crane scheduling problem, the following describes the four components of the heuristic, i.e., the Constructor, Local Search, the Analyzer and the Prioritizer.

The Constructor:The Constructor generates a solution using a greedy algorithm which assigns priorities to problem elements. We regard the cranes as the problem elements and try to assign a job to a crane one at a time in the order they occur in the priority sequence. Instead of assigning a job to a crane greedily each time, we use an alternative strategy which involves more randomness. For each crane, we have a selection threshold probability p1and for each selected crane, we have two means of assignment, one is a greedy assignment which selects a compatible job with the largest weight; the other is random assignment which randomly picks one job from compatible jobs. Here “compatible job” means we assign the job to the crane satisfying all the constraints. Which scheme is chosen depends on another probability p2.

Local Search:In the local search component, we perform neighborhood search and enhance it by using meta-heuristic techniques. For neighborhood search, we continue to use the same scheme described in section 5.3.1. Here, after creating neighbors of the current greedy solution, we choose the one with the highest proﬁt as the next solution and move to it. This will continue until a local optimum is reached or the number of steps stipulated is exceeded.

The Analyzer:The Analyzer assigns blame to each crane. How large the blame value is depends on how the current assignment aﬀects the solution. In this problem, the blame value of a crane depends on how much the assignment contributes to the total proﬁt, and also, how many jobs are “banned” by the assignment because of the spatial constraints. In the blame value calculation, both of the factors should be considered.

The Prioritizer: Once blame has been assigned, the Prioritizer modiﬁes the previous sequence of cranes. Cranes with higher blame values will move forward in the priority sequence while ones with smaller blame values will remain at the back of the sequence. Troublesome cranes will then be handled ﬁrst by the Constructor in the next iteration.

6 Experimental Results

We implemented the four diﬀerent algorithms – Hill Climbing with 100-restarts (HC), Probabilistic Tabu Search (PTS), Squeaky Wheel Optimization (SWO) and SWO with Local Search (SWO+L) – using C++ and ran on a P4 2.52 GHZ CPU with 1GB memory. The pa－rameters used were: PTS - max iterations: 20000, tabu add tenure: 10, tabu delete tenure: 10, Delete Penalty Unit (DP U): 100, Add Penalty Unit (AP U ): 50, Aspiration Threshold (AST ): 300, Transition Penalty Unit (T P U ): 10, Residence Penalty Unit (RP U ): 10, α: 2, β: 4, γ: 4, K: 50 (see Appendix B) Candidate selection probability (p): 0.3, SWO/SWO+L- max iterations: 2000, Restarts: 10, hill climbing iterations: 10. These were a result of parameter tuning obtained from running extensive experiments on small test cases.

For test sizes, we provide results here to reﬂect actual situations at the port. As stated, a job parcel can include a number of jobs to be processed in a given time interval, and these jobs can come from a number of ships and involve a number of cranes. Typically, depending on the size of the ship, between 4 to 7 cranes are assigned to a ship. The number of jobs required by any one ship can vary depending on the size and conﬁguration of each ship and on how jobs are deﬁned. A ship with four holds and a number of deck areas could well have nine diﬀerent jobs, for example. Since, typically, a job parcel will not exceed ﬁve ships, we tested the algorithms on data representing not more than thirty cranes and forty jobs in the ﬁrst instance.