《基于启发式算法的坞位配置系统研究与应用》由会员分享，可在线阅读，更多相关《基于启发式算法的坞位配置系统研究与应用（60页珍藏版）》请在金锄头文库上搜索。
1、上海交通大学硕士学位论文基于启发式算法的坞位配置系统研究与应用姓名：邬文尧申请学位级别：硕士专业：软件工程指导教师：蔡鸿明;姜丽红20090101V 基于启发式算法的坞位配置系统研究与应用 基于启发式算法的坞位配置系统研究与应用 摘 要 随着国内外船舶需求的不断增大和造船行业竞争的日益加剧，造船业的制造方式已经从靠廉价劳动力获得成本优势的粗放型制造逐渐转向以船坞为核心的总装化精益制造模式。在这一过程中，船坞作为造船厂生产调度的核心资源和设备，对其合理的利用和调度就显得格外重要。本文根据船坞调度问题的特点，在对该问题深入分析的基础上建立数学模型，然后采用针对该问题设计的遗传算法进行问题空间的映射
2、，进而通过遗传进化过程全局搜索最优的调度解，最后通过实例的应用验证了该系统的可行性与有效性，满足了造船行业的需求。 首先，本文概述了造船行业的现状及趋势，指出了该问题对于造船业的重要性。阐述了坞位配置问题的基本研究现状和目前存在的问题，以及将要用到的启发式算法的概念、种类、方法和优劣等基本理论，指明了启发式算法在坞位配置问题中的优势和可行性，为本文的论述奠定了一定的理论基础。 然后，在列举了一个船坞调度问题实例的基础上，对该问题涉及到的因变量、目标函数、各类约束做了深入的分析。针对分析中提到的各类因素映射为数学描述，并建立对应的数学模型。接着，在阐述和分析了一种模拟优化算法的原理和优劣之后，提
3、出启发式算法中的组合遗传算法，并阐明了遗传算法中的编解码、种群初始化、选择、交叉、变异等关键步骤在坞位调度问题中的具体实现原理，完成从坞位调度问题到遗传算法的解空间映射问题。这样坞位调度问题就转变成了遗传算法中种群不断进化搜索最优解的过程。之后，在模型和算法的基础上，先从系统需求的角度分析了系统的功能、非功能需求以及合适的体系架构，再分别描述了系统的数据访问、订单管理、船坞管理和坞位调度等模块的设计与实现。 最后，在某造船基地为未来 5 年制定船坞计划的实例中，应用该系统VI 生成调度结果。将应用的结果与手工生成的进行比较分析，在最大出坞时间、船坞负载率等方面得到了较好的效果，验证了该系统是可
4、行有效的。 关键词： 船坞计划，精益化生产，遗传算法， 坞位调度系统 VII Dock Arrangement System Research and Application Based on Heuristic Algorithm ABSTRACT With the augment of international requirements on ships and aggravation of ship building industrys competitions, many ship building factories production models have gradually
5、 transferred from extensive manufacture, which establishes its advantages based on low-price labors, to intensive final assembly manufacture. So, its really important to make good use of docks, which are the most valuable resources and devices in the ship building factory. The thesis establishes a m
6、ath model based on the dock arrangement problem, and then adopt genetic algorithm to search for the best solution in all possible combinations. At last we apply an actual problem to validate the systems feasibility and availability. First, we state the ship building industrys current situations and
7、future trends, in order to show dock arrangements importance. Then we represent previous researches on the problem and their deficiencies. After expounding heuristic algorithms concepts, categories, methods, merits and demerits, we show that genetic algorithm adapts to solving this problem. Then, wi
8、th an instance of dock arrangement, we analysis all parts of the problem, include dependent variables, goals, constraints, and so on. We build a math model based on these factors. We state and analysis a simulation optimizing algorithm and find that genetic algorithm will do better. We elaborate all
9、 details of encodes, decodes, initialization, selections, crossovers, mutations in dock scheduling problem. We follow up with functional/non-functional requirement analysis and system architecture, then we describe specific designs and implements of data accessing, order management, dock management,
10、 dock scheduling models, etc. Finally, we describe a 5-year dock scheduling problem of some ship building corporation. We input the problem into system, and compare the output with other solutions made by hand. The result shows our solution has a better performance on maximum out-of-dock time and do
11、ck load rates, which means our system is feasible and effective. KEY WORDS：Dock Planning, Intensive Production, Genetic Algorithm, Dock Arrangement System III 上海交通大学 学位论文原创性声明 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文
12、中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名: 邬 文 尧 日期： 2009年1月16日 IV 上海交通大学 学位论文版权使用授权书 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密，保密，在 年解密后适用本授权书 本学位论文属于 不保密 不保密 （请在以上方框内打“”） 学位论文作者签名： 邬 文
13、 尧 指导教师签名：蔡 鸿 明 日期：2009年1月16日 日期：2009年1月16日 上海交通大学工学硕士论文 基于启发式算法的坞位配置系统研究与应用基于启发式算法的坞位配置系统研究与应用 1 第一章 绪论第一章 绪论 1.1 船舶制造业的现状及趋势 自从七十年代末中国造船业走向国际市场以来，到现在三十多年，我国造船业已经取得了长足的进步，年造船产量从世界排名第 17 位跃升为稳居世界第 3 位(连续 12 年居世界第 3 位)，形成了韩、日、中三足鼎立的局面。 新世纪以来的国际造船市场持续兴旺，为造船业发展提供了良好的机遇。中国船舶工业抓住这一机遇，产业规模迅速扩大，已经在油船和集装箱船的
14、市场中超过日本，成为世界第二大造船国。 中国船舶工业行业协会的统计数据表明， 2006 年中国造船产量达到 1452 万载重吨，比 2000 年翻了两番，占世界份额从 6%提高到近 20%，已连续 12 年位居世界第三，与韩日的差距进一步缩小；此外，2006 年我国新承接船舶订单也实现了跨越式增长，达 4251 万载重吨，同比增长 150%，占世界市场份额的近 31%，再次超过日本，位居世界第二；据国防科工委船舶行业管理办公室统计，手持船舶订单则达到了 6872 万载重吨，同比增长 73%，比 2000 年增长了 5.5 倍，占世界市场份额的近 25%。在三大主流船型（油船、集装箱船、散货船）
15、市场中，油船首次超过日本，集装箱船大幅超过日本，均位列世界第二。 自 2006 年下半年以来，造船市场持续火爆，船东争着下订单，订单量和船价持续刷新历史记录。随着全球范围的新造船订单快速上升，很多地区出现了几十年未遇的造船产能不足现象。从英国克拉克松公司统计出的表 1- 1 中可以看出，中国的订单量将在 2010 年跃居世界第一位，这对我国的造船实力提出了新的要求。 表 1- 1 世界各国手持订单分布 单位：(万载重吨) 2007 年 2008 年 2009 年 2010 年 2011 年 日本 775.2 2853.4 2835.5 2244 1423 韩国 537.8 3455.5 5654.6 5186.9 2078.1 中国 638.2 2527.5 4588.7 5853.1 2581.9 世界 2558 10082 14207 14198 6427 然而，虽然我国的生产量和订货量增长迅速，已达到世界造船大国的水平，但我国的技术水平却与国际先进水平有着很大差距。这不仅制约着我国造船业的持续上海交通大学工学硕士论文 基于启发式算法的坞位配置系统研究与应用基于启发式算法的坞位配置系统研究与应用 2 增长能力，也无法满足日益增长的造船需求，并且也是制约我国成为世界第一造船强国关键所在。 与造船强国韩、日相比，我们的差距主要体现
