菜单
  

    Because of the range of local search solutions, we can select neighbors based on different 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 sacrificed 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 profit 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 affects the solution. In this problem, the blame value of a crane depends on how much the assignment contributes to the total profit, 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 modifies 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 first by the Constructor in the next iteration.

    6  Experimental Results

    We implemented the four different 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 reflect 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 configuration of each ship and on how jobs are defined. A ship with four holds and a number of deck areas could well have nine different jobs, for example. Since, typically, a job parcel will not exceed five ships, we tested the algorithms on data representing not more than thirty cranes and forty jobs in the first instance. 

  1. 上一篇:残余应力状态的影响刀具寿命英文文献和中文翻译
  2. 下一篇:噪音工程齿轮模型英文文献和中文翻译
  1. 会计师事务所任期与审计...

  2. ADO.NET结构与概述英文文献和中文翻译

  3. 信息系统开发与数据库开...

  4. 机器人学入门力学与控制英文文献和中文翻译

  5. 园林植物景观的园林绿化...

  6. 桥式起重机智能防摆控制英文文献和中文翻译

  7. 起重机升降传感器系统英文文献和中文翻译

  8. NFC协议物理层的软件实现+文献综述

  9. 江苏省某高中学生体质现状的调查研究

  10. 现代简约美式风格在室内家装中的运用

  11. g-C3N4光催化剂的制备和光催化性能研究

  12. 高警觉工作人群的元情绪...

  13. 浅析中国古代宗法制度

  14. 巴金《激流三部曲》高觉新的悲剧命运

  15. 上市公司股权结构对经营绩效的影响研究

  16. 中国传统元素在游戏角色...

  17. C++最短路径算法研究和程序设计

  

About

优尔论文网手机版...

主页:http://www.youerw.com

关闭返回