- 上一篇：残余应力状态的影响刀具寿命英文文献和中文翻译
- 下一篇：噪音工程齿轮模型英文文献和中文翻译
We ran 110 instances in group 1 but could only obtain results for the smallest 20 instances from the solver. The remaining 90 larger instances caused CPLEX to be out of memory.All running times were measured in seconds and we found that both CPLEX and heuristic algorithms were fast. All algorithms achieved optimal solutions in most of the instances and SWO+L obtained optimal solution for all 20 cases.
We generated a second group 2 of 20 instances whose sizes were between 10 × 30 and 30 × 40. These instances were used to observe how running time increased with size as well as to compare the quality of solutions.
CPLEX found 17 optimal solutions out of 20 instances. However, the running times for CPLEX increased significantly when the instances became larger, and it ran out of memory for the last three cases. On the other hand, the four heuristic algorithms continued to obtain solutions in very short times although HC, PTS and SWO did not perform very well on larger cases. SWO+L, however, continued to perform well in time and quality of solutions. For group 2, it obtained 14 out of 17 optimal solutions and found good solutions for the last three cases for which CPLEX ran out of memory. These were achieved in very short times, all under five seconds.
As the constraints are tight in this problem, that is, for a given crane there were only a few jobs that were compatible, solutions neighborhood search can generate are restricted. HC is easily trapped at local optima and the quality of results confirm this. Similarly, PTS is based on the neighborhood search and is easily trapped in regions of the search space which can explain its poor performance. On the other hand, the SWO and SWO+L use both the solution space and priority space where a small change in the priority space can cause large changes in the solution space. SWO+L is the best of the four algorithms. The difference in performance between SWO and SWO+L is significant, and is attributable entirely to the local search component which is able to generate a perse range of solutions. This is significant when compared to the purely greedy solution created by the Constructor used in SWO. Further, since all elements are assigned equal blame, there is a higher chance that local optima can be avoided. SWO+L , however, has the longest run times among the heuristics due to its local search component.
In any computation study, it is desirable to scale data up to test the effectiveness of algorithms. In view of this, we ran a second set of tests where the number of cranes ranged up to one hundred and the jobs up to two thousand. Results for these were similar to those obtained for small cases where the SWO+L algorithm outperformed the other heuristics.
7．Conclusion
In this work, we studied a new crane scheduling model which included commonly-found spatial constraints. For the Non-crossing and Neighborhood constraint problems, we proposed dynamic programming algorithms. For the more difficult Job Separation constraint problem, we showed it to be NP-complete and used PTS and SWO with Local Search. We proposed a new framework which improves the SWO technique by including a local search component. Experiments were conducted on industry-size test cases as well as large cases. For the smaller test cases, the quality and speed of the heuristics was compared with results obtained from CPLEX. These showed that SWO with Local Search performed best and can give good results for both small and large problems in very short running times which allows its use in practical situations.
In practice, more complex situations could occur and it would be interesting and useful to study crane scheduling with spatial and time considerations although this would be the subject of further research.
References
[1] Ebru K. Bish, Thin-Yin Leong, Chung-Lun Li, Jonanthan W.C.Ng, and David Simchi-Levi. Analysis of a new vehicle scheduling and location problem.
-
会计师事务所任期与审计...
-
ADO.NET结构与概述英文文献和中文翻译
-
信息系统开发与数据库开...
-
机器人学入门力学与控制英文文献和中文翻译
-
园林植物景观的园林绿化...
-
桥式起重机智能防摆控制英文文献和中文翻译
-
起重机升降传感器系统英文文献和中文翻译
NFC协议物理层的软件实现+文献综述
江苏省某高中学生体质现状的调查研究
现代简约美式风格在室内家装中的运用
g-C3N4光催化剂的制备和光催化性能研究
高警觉工作人群的元情绪...
浅析中国古代宗法制度
巴金《激流三部曲》高觉新的悲剧命运
上市公司股权结构对经营绩效的影响研究
中国传统元素在游戏角色...
C++最短路径算法研究和程序设计