造船厂钢板入库作业优化及钢板管理信息系统开发 毕业论文.doc

摘 要摘 要随着全球造船市场环境的变化，国内造船企业钢板堆场管理问题愈来愈突出，钢板堆场是船厂不可缺少的一部分，它是全厂钢材原材料的进料、分类堆放、保管和供应的场地。企业迫切需要完善的钢板堆场管理理论与技术。因此要振兴我国造船行业，提高钢板堆场管理水平和作业效率势在必行。本文以造船厂钢板堆场为研究对象，结合造船企业钢板入出库作业特点及钢板堆放原则，对钢板堆场的入库作业进行优化，开发了钢板堆场管理信息系统，旨在从整体上提高钢板堆场作业效率。本文针对钢板堆场优化问题，对国内外研究现状进行了分析，并将优化钢板入库作业及提高钢板堆场管理水平确定为本文的研究重点。钢板堆场作业包括入库作业、在库作业和出库作业三个阶段。批次钢板入库时，为每块钢板选择合适的堆放位置将直接影响钢板堆场作业效率。本文对钢板堆场的入出作业过程进行深入分析，提出了一个以最大化堆场空间利用率及最小化吊机运行时间为目标的数学优化模型。同时，设计了遗传模拟退火算法对该问题进行求解。根据实际算例的求解结果及分析，找出了最优入库方案。在此基础上，对造船厂钢板堆场管理需求进行了分析、使用面向对象业务建模方法建模、设计了一套钢板堆场信息化建设的解决方案，开发了钢板堆场管理信息系统，实现了钢板信息化管理。综上，本文对造船厂钢板入库优化的研究成果，以及钢板堆场管理信息系统的开发，取得了明显的效果，具有较好的应用价值和指导意义。并对相关作业的研究具有较为有益的借鉴意义。关键词 钢板入库；堆场管理；遗传模拟退火算法；管理信息系统IXAbstractAbstractAs the global shipping market environment changes, the steel stacking yard management problem of the domestic shipyard becomes increasingly highlight, the steel stacking yard is the storage center of important production material, so enterprises need the theory and technology of steel stacking yard management. Therefore, to revitalize China shipbuilding industry, improve the management and the opration efficiency in the steel stacking yard has become a top priority.Took the shipyard as research object, the steel stacking input operation was optimized with the stacking constraint, and a warehouse management information system was developed in this paper, in order to improve the overall operation efficiency in the steel stacking yard.Considering the stacking yard management problem, this paper analyzes the research status in warehouse input and management of steel plate stacking yard in home and abroad. And much more attention is paid to the steel plate stacking yard input operation optimization and warehouse management in this paper. The warehouse operation included input, storage and output such three stages in steel stacking yard. A stack choise for each plate as input was very important for operation efficiency in the steel stacking yard. The flow of steel plate management was proposed at first in this paper. And then, a mathematical optimization model with the aim of maximum space utilization and minimum crane traveling time was proposed, after a deep analysis on the input and output operation in the steel stacking yard. Meanwhile, a genetic simulated annealing algorithm was designed to solve this problem in this pater. And then the optimal solution was gained, with the analysis on the result of an instance data.On the basis of the work referred in the previous section, with the deep analysis on the requirement of steel plate management, we design a storage management information system for the steel plate stacking yard. This storage management information system could implement steel plate informatization. In conclusion, the research on the warhouse input operation in the steel stacking yard, and the warehouse management information system development in this paper, had made profound effects, and it was instructive and had good application value. And it also had good beneficial reference to the related research work.Key words steel plate storage； stockyard Management； genetic simulated annealing algorithm； management information system；目 录目 录摘 要IAbstractII第1章 绪论11.1 课题的研究背景及意义11.1.1 课题的研究背景11.1.2 课题的研究意义21.2 国内外研究现状31.2.1 造船厂钢板堆场管理研究现状31.2.2 钢板管理信息系统研究现状51.3 研究内容及技术路线61.4 本文创新点7第2章 论文研究的理论及方法82.1 堆场作业优化方法82.2 遗传算法及其主要特点102.2.1 遗传算法的基本原理102.2.2 遗传算法的优点和不足102.2.3 遗传算法的操作流程112.2.4 遗传算法参数选择与操作设计122.3 模拟退火算法的基本理论122.3.1 模拟退火算法的参数控制问题132.3.2 模拟退火算法的流程132.3.3 模拟退火算法的优缺点142.3.4 遗传模拟退火算法概述142.4 UML、RUP与体系结构建模152.4.1 面向对象业务建模方法152.4.2 UML、RUP162.5 本章小节17第3章 造船厂钢板堆场作业流程分析183.1 问题描述183.2 钢板管理流程分析193.2.1 钢板管理界限193.2.2 钢板接收193.2.3 报验203.2.4 钢板集配和出库213.2.5 盘点213.2.6 钢配库现场施工运作213.3 入库作业分析223.3.1 在途材料清单223.3.2 物料(钢板)接货任务表233.3.3 现场接货反馈243.3.4 现场盘点管理263.4 出库作业分析273.4.1 分段下料计划273.4.2 周材料需求计划273.4.3 日配任务计划283.5 本章小结31第4章 钢板堆场入库作业建模324.1钢板入库描述324.1.1 入库作业优化问题的数学描述324.1.2 钢板堆场堆放原则334.2 钢板入库作业决策模型的建立344.2.1 堆场空间利用率最大344.2.2 电磁吊行驶总时间最短354.2.3 约束条件364.3 钢板入库作业优化问题的遗传模拟退火算法364.3.1 算法设计364.3.2 算法关键技术384.4 仿真算例394.5 本章小结41第5章 钢板管理信息系统分析与设计425.1 系统需求分析425.2 系统业务建模435.2.1 系统业务模型435.2.2 系统静态模型465.2.3 系统动态模型465.3 系统设计475.3.1 系统框架设计475.3.2 系统功能模块设计485.3.3 数据库设计495.4 本章小结50第6章 钢板管理信息系统开发与实现516.1 系统开发环境516.2 系统实现的关键技术526.2.1 Matlab连接数据库526.2.2 PowerBuilder程序调用Matlab536.3 系统实现546.3.1 系统操作流程546.3.2 程序运行界面实例556.4 本章小结61结 论62参考文献63附 录66攻读学位期间发表的学术论文68致 谢68Contents ContentsAbstract (Chinese)IAbstract (English)IIChapter 1 Introduction11.1 Background and Significant11.1.1 Research Background11.1.2 Research Significant21.2 International and Internal Current Research Situation31.2.1 Current Research Situation of Steel Plate Stockyard in Shipyard31.2.2 Current Research Situation of Management Information System51.3 Research Contents and Structure61.4 This Innovations7Chapter 2 Research Theory and Method82.1 Research Technique82.2 Genetic Algorithm and Its Main Features102.2.1 The Basic Principle of Genetic Algorithms102.2.2 Strengths and Weaknesses of Genetic Algorithms102.2.3 Operational Processes of Genetic Algorithm112.2.4 Genetic Algorithm Parameter Selection Design and Operation122.3 The Basic Theory of Simulated Annealing Algorithm122.3.1 Parameter Control of Simulated Annealing Algorithm132.3.2 Process of Simulated Annealing Algorithm132.3.3 Strengths and Weaknesses of Simulated Annealing Algorithm142.3.4 Outline of Genetic Simulated Annealing Algorithm142.4 The Basic Theory of UML、RUP and System Architecture Modeling152.4.1 Object-Oriented Business Modeling Method152.4.2 UML、RUP162.5 Chapter Summary17Chapter 3 Analysis of Steel Plate Management Process183.1 Questions Description183.2 Analysis of Steel Plate Management Process193.2.1 Boundary of Plate Management193.2.2 Plate Reception193.2.3 Plate Examine203.2.4 Plate Output213.2.5 Inventory213.2.6 Plate Construction213.3 Analysis of Plate Input223.3.1 Bills of Materials on Way223.3.2 Bills of Reception Materials233.3.3 Bills of Reception Materials Backfeed243.3.4 Inventory263.4 Analysis of Plate Output273.4.1 Partition Blanking Planning273.4.2 Week Material Requirement Planning273.4.3 Day Material Requirement Planning283.5 Chapter Summary31Chapter 4 Modeling of Stockyard Input324.1 Plate Input Description324.1.1 Input Question Mathematics Description324.1.2 Principle of Plate Stacking334.2 Model of Plate Input Decision344.2.1 Maximum Space Utilization344.2.2 Minimum CraneTtraveling Time354.2.3 Constraint Condition364.3 Genetic Simulated Annealing Algorithm364.3.1 Algorithm Design364.3.2 Key Technology384.4 Simulate Instance394.5 Chapter Summary41Chapter 5 Management Information System Analysis and Design425.1 System Requirements Analysis425.2 System Business Modeling435.2.1 System Business Model435.2.2 System Static Model465.2.3 System Dynamic Model465.3 Management Information System Design475.3.1 System Frame Design475.3.2 System Features Modular Design485.3.3 System Database Design495.4 Chapter Summary50Chapter 6 Management Information System Development and Implementation516.1 System Development Environment516.2 The Key Technologies of System Development526.2.1 Matlab Connect to The Database526.2.2 PowerBuilder Procedure Call Matlab536.3 System Implementation546.3.1 System Operation Flow546.3.2 Interface Instance556.4 Chapter Summary61Conclusion62Reference63Appendix66Papers Published in The Peried of Master Degree Education68Acknowledgement68第1章 绪论第1章 绪论本章介绍了论文研究的背景与意义，对国内外研究现状进行了综述，说明了造船厂钢板堆场管理领域的基本概况，及钢板库堆场信息化管理研究水平，最后给出了论文的主要研究内容和结构框架。1.1 课题的研究背景及意义1.1.1 课题的研究背景船舶工业是现代大工业的缩影，是与国民经济发展及国防安全建设息息相关的战略性产业1，具有劳动、资金、技术密集型、产业链长、涉及面广、产业关联度高、容纳就业人数多、单位产品价值大、出口创汇能力强等特点。我国船舶工业自建国以来共经历了以下几个发展阶段：以军为主到军民结合、寓军于民、军民融合2, 3，逐渐走出了一条从小到大的成长之路。改革开放以来，中国船舶工业积极贯彻邓小平同志关于“中国的船舶要出口，要打进国际市场”的重要指示，成为我国重工业领域的领跑者，率先进入国际市场，积极参与国际竞争，经二十多年孜孜不懈的努力，使此产业得以迅猛发展，现已成为我国为数不多的几个具备较强国际竞争能力的外向型产业之一，并已成为世界船舶工业的一支重要力量。近年，虽受全球金融危机影响，国际航运市场和造船市场遭遇寒冬，但国务院制定的十大行业振兴规划政策将积极有效地应对此次金融危机对我国船舶行业的影响。再者，与日韩等造船业发达国家相比，我国船舶制造业整体技术水平仍存在较大差距。“先进造船能力不足、自主研发能力弱、船舶配套对外依存度高、造船生产效率低”是制约我国造船业进一步发展的四大瓶颈。尤其在生产效率方面，我国与日本、韩国等造船强国的差距更大4，只有日本的1/10，韩国的1/6-1/8。因此提高船舶行业的生产效率，降低生产成本，对促进我国经济发展有着重大的意义。堆场是船舶制造企业物流缓冲和中转，用于各生产环节中原材料和中间产品的堆放5。钢板堆场是船厂不可或缺的一部分，是全厂钢材原材料的进料、分类堆放、保管和供应的场地。钢板堆场管理活动包括入库作业管理、在库作业管理和出库作业管理。钢板入库作业6是钢厂根据船厂的采购合同，分批次将钢板送达堆场，装卸中心将钢板搬运到垛位的作业过程。船厂钢板堆场具有钢板数量大，规格多的特点，加之场地有限，各种规格的钢板混合放置，顺序混乱，管理难度大。钢板入库作业直接影响了钢板出库效率，进而影响了船厂的生产效率。然而，国内船厂钢板堆场管理模式落后、作业粗放，无法适应新时期生产需求的增加和造船能力的扩大。迄今，国内大多数船厂钢板堆场管理仍处于凭经验管理为主，根据调度人员的经验及场地现状安排堆位，随意性很大，堆放顺序混乱，需要花费大量时间进行查找，由于缺乏数字优化的管理，倒垛工作量大，增加了堆场吊机的负荷，降低了钢板堆场周转率，其作业效率低下已成为制约船厂进一步发展的瓶颈。为了提升我国船厂的生产能力和企业效益，除了采用先进的作业设备、扩大船厂规模来提高作业能力外，还应该对钢板堆场作业进行合理安排，优化钢板入库作业，解决问题源头，提高堆场利用率及钢板堆场入出库作业效率。此外，还应该建立钢板库堆场管理信息系统来提高对钢板堆场的管理水平，为船舶建造部门提供有力保障。1.1.2 课题的研究意义钢板是造船工业最基本的生产原材料，其能否合理有效地流通将直接影响造船企业生产活动能否顺利进行并按时完成。钢板堆场链接物料采购和各生产环节，担负着钢板的进料、发料、保存等重要职责，因此，钢板堆场对于保证钢板顺畅流通、企业生产顺利进行有着重大影响。本课题的研究意义表现为：1) 提高钢板堆场利用率及作业效率能有效降低成本和提高生产效率。长期以来，我国造船企业普遍存在重生产、轻流通的问题。改进生产工艺、提高生产能力只是企业制造的一部分，如果同时提高供应部门管理水平及作业效率，将很大程度提高生产能力水平。随着船舶工业的发展，钢板堆场已日渐成为造船企业物料流通的瓶颈，所以提高钢板堆场管理水平能有效降低人工、设备等成本、缩短造船周期，保证按时、按质完成任务，从而提高船厂竞争力。2) 钢板堆场入库作业优化是一个复杂问题，具有较高的研究理论价值和实际意义。船厂钢板堆放需遵循诸多原则，并且钢板规格多、数量大，人力、设备、堆场空间资源有限，所以，为批次入库钢板选择合适堆位成为一个复杂的组合优化问题，属于NP-hard问题。目前，相关领域对板坯入库作业优化问题研究较多，但对造船厂钢板入库作业优化问题的研究较少，因此，全面、合理、有效的船厂钢板入库作业优化问题研究具有一定的理论意义和较高的实用价值。3) 钢板堆场优化管理信息系统能有效提高钢板堆场管理水平。目前，国内许多船舶企业为提高生产管理水平与竞争力，将目光纷纷投向企业信息化建设。其中有不少成功案例，但现存钢板管理信息系统仍有诸多不足，不能完全满足船厂堆场信息化要求，只实现了简单的数据存储与查询，没有上升到决策层。所以，一套利用船舶生产信息及钢板堆场信息，进行优化作业决策、提高作业效率、降低作业成本的钢板堆场管理信息系统将更加有效地提升钢板堆场管理水平和作业能力。1.2 国内外研究现状1.2.1 造船厂钢板堆场管理研究现状钢板堆场作为全厂钢材原材料的进料、分类堆放、保管和供应的场地，在船厂生产系统中起到不可或缺的作用，是船舶建造生产系统的物流和信息流源头，其管理水平的高低对船舶建造进度和企业经济效益产生直接影响。此外，船用钢板的采购成本7和物流成本在船舶建造成本中占有较大比重。因此，对钢板堆场进行优化管理是船厂进行生产管理和成本控制活动的重要内容。随着国内造船工艺技术的逐步成熟和市场竞争的进一步加剧，造船行业的利润空间在不断压缩。许多企业开始吸取国外船厂的先进管理思想，进行生产成本控制，并将优化生产物流作为降低成本、提高市场竞争力的重要手段。近年来，对钢板堆场管理的研究已引起人们的重视。目前，国内外专家学者主要从以下几方面对此类问题进行研究：1) 堆场管理信息化随着计算机技术在社会管理和生产工程等领域的成功应用，人们开始尝试将先进的管理思想和管理手段，如自动化技术、条码技术8、射频识别、激光定位等应用到钢板堆场的管理中，以提高堆场管理水平。上世纪90年代，Yoon 9等人主要对钢板搬运设备(桥吊等)进行自动化控制研究；Hong Ju Kim10，Sang Y Park11等人以造船厂钢板堆场的自动化技术应用为实例，研究了桥吊与计算机控制中心、终端设备的数据实时交互技术，和钢板识别技术两大核心问题；D.stroo12, 13等人研究并实现了钢厂板材库的自动化作业系统，并通过优化算法控制车辆和桥吊进行协同作业，提高钢板的出库效率，节约作业成本。随着网络和通信技术的发展，“数字造船”成为世界各国船舶工业追求的目标。信息化正在改变着造船工业的设计手段、运营模式和管理方式。国外较大的船厂己经具备成熟的ERP管理经验，实现了信息化程度较高的企业生产运作管理模式。目前国内船厂的制造设备、工厂条件与国际先进水平差距不大，但信息化技术和管理技术依然落后。加大信息化建设，大力提高船舶行业的信息化水平14，以信息化推动造船现代化是中国造船工业追赶国际先进水平的良好机遇。2) 设备改良优化许多研究者针对钢板装卸工具进行研究，研究对象包括吊钳、吊钩，并申报诸多专利。唐燕琪15针对钢板入库所使用的吊具钢丝绳、起重钳在吊运过程中造成钢板吊伤、吊弯现象，设计出特质层钳吊具；自从国内学者周康有16等人提出新型钢板吊具电控永磁吸头以来，不少学者在此基础上对电控永磁吊具进行了研究和改进；侯晓光17等人对电控永磁吊起重多层钢板的磁路进行研究，得出起重数量与钢板厚度的关系及使用范围，为钢板起重设备的选型提供了依据；沈红宾18通过对比电控永磁吊具与普通电磁吊具的特点得出电控永磁吊具更适合钢板装卸等。3) 堆场作业优化随着计算机技术、运筹学和管理科学的发展，人们开始从微观层面研究钢板堆场的作业活动，根据钢板堆场作业要求的特殊性和堆场内外部因素的客观要求，对作业流程进行优化和规范，以达到充分利用生产要素(场地、设备、作业人员)，降低作业强度，提高作业效率的目的。钢板堆场作业主要包括入库作业、钢板出库作业以及由此产生的钢板倒垛作业。钢板入库需要为钢板指定放板垛位，钢板出库需要选择满足生产需求的钢板，同时发生翻板倒垛。以上问题可以抽象为复杂的组合优化问题，利用计算机技术和数学规划方法进行优化，实现较好的解决方案。船厂钢板入库管理方面，廖尧19等人提出了造船厂钢板库批量摆放的布局方案，建立了一个以最小垛位数需求为目标的数学优化模型，找出最优入库批量计划，以提高堆场利用率和作业效率；蒋宏如20等人将数字化仿真技术应用于国内船厂的堆场管理中，使作业调度人员能够在计算机上模拟堆场作业过程，并得到优化方案，改善了钢板入库时根据调度人员的经验和现场状况随意堆放的混乱局面。目前国内此类研究较为少见，在相近领域，一些学者对钢厂板坯入库作业优化问题进行了探索。李苏剑21等人以现场管理人员经验为基础，研究了宝钢钢板库入库作业优化模型，为入库钢板选择最佳垛位，避免了出入库作业干涉，加快了钢板入库作业速度；李耀华22以保证钢板出库顺利进行，减少倒垛次数为目标研究了钢厂热轧生产计划中的钢板入库计划编制优化问题；文献23提出了基于混沌遗传算法的板坯入库作业优化优化方法，可快速为板坯选择最优的库位和垛位；王敏24等人提出求解入库堆垛问题的改进约束满足算法，该算法对于求解复杂约束下的大规模堆场问题有很大改善；徐俊驰25等人以提高板坯库空间利用率为目标，构建了一种混合WBF和遗传算法的板坯入库优化算法；文献26通过优化钢板库堆放和提高钢板库利用率来实现钢板库的自动化管理，最终达到提高宽中厚板(卷)生产线自动化管理水平；陈小文27-29等人将钢坯入库归结为装箱问题并建立数学模型进行求解，模型具有一定合理性及算法可行性，为钢板入库管理提供很好的方法；王小明30等通过设计一种离线算法解决了钢卷入库问题；刁磊31等提出一种新的入库垛位选择优化模型，该模型综合考虑了订货合同、钢种等约束条件，为钢卷入库选择合理垛位提供了一种有效方法。该领域的优化研究对船厂钢板堆场管理有很好的指导与借鉴意义。船厂钢板出库管理方面，文献32根据船厂钢板堆场的系统结构特征及其堆放规则，应用数据库和计算机仿真技术建立堆场数字化仿真模型，设计并实现了钢板堆场出库管理专家系统，根据生产部门的需求选择出库钢板，指导桥吊作业；丹麦科技大学的J.Hansen33-35等人在一系列针对Odense造船厂钢板堆场作业调度优化的研究报告中讨论了出库钢板和倒垛钢板作业顺序确定的情况下，两台桥吊协同作业的调度优化问题，并利用禁忌搜索算法实现方案优化；王广民36提出了以出库作业时间最短作为优化目标，最终求解出合理的出库顺序以及最优的倒垛方案，以减少钢板倒垛的次数。在相关领域，唐立新37等人在轧制板坯顺序确定的情况下，把板坯库倒垛优化问题归结为0-1规划问题，并多回路启发式算法对该问题进行优化；王伟38等人在此基础上，提出了将板坯库出库计划分解为板坯出库优化决策和板坯最优倒垛决策组合优化问题，分别建立了板坯出库优化决策模型和板坯最优倒垛决策模型，利用两个模型分层协作完成出库计划编制；降低倒垛次数最直接有效的方法是降低钢板堆放高度，减少钢板混合规格数量，文献39借鉴ABC分析原理，按照钢板占在库钢板总数量的比例和占在库钢板总规格数的比值这两个指标，提出钢板分类管理方法，在堆场垛位数和库存钢板数量不变的情况下，降低钢板混合程度，减小堆场内物流作业量。1.2.2 钢板管理信息系统研究现状国内关于仓库管理信息系统的研究较晚，主要于20世纪90年代才真正起步，尤其我国船厂，其仓库管理信息化水平和国外发达国家相比，还有较大差距。在钢板堆场管理方面，董绍华40借鉴企业物流管理的理论和经验，在常规仓库管理模型的基础上，引入人工智能的方法以提高管理的灵活性和应变能力，开发仓库管理专家决策系统，以解决钢板堆场入库、倒垛、出库和搬运设备调度等决策问题；李苏剑41等人以系统性、实时性和可扩展性为原则，采用结构化方法设计钢板堆场生产物流管理系统，确保了物流与信息流的真正统一；杨翠蓉42等人介绍了在企业ERP环境下的仓库管理信息系统的实现方案，详细的论述了仓库管理系统在ERP中与其他企业的联系，以及系统的设计方案；廖尧19等人提出了一套钢板库信息化建设的解决方案，采用条目技术、无线网络技术、web service 架构、移动终端等信息技术开发了钢板库管理信息系统，实现了对钢板进行实时的监控，对钢板库信息化管理；李雪43等人采用系统工程建模语言SysML建立钢板堆场作业系统模型，并进行仿真实现，为船厂实现SysML物流作业系统建模研究具有重要意义；张军强44等人采用面向对象的程序设计方法设计开发了热轧板坯库优化管理系统，该系统可使板坯库生产物流作业更加合理化；文献45研究了单元货格式自动化立体仓库中的货位实时分配问题，依次构建了三个优化目标函数，该算法可减少堆垛机的平均行程时间；张燕46研究了上钢一厂热轧板坯库计算机系统构成及应用软件的基本功能，并对入库管理功能中的堆放策略进行了详细描述。以上钢板仓库管理信息系统的开发侧重点各不相同，很多船厂虽然已具备一套钢板管理系统，但只是简单地实现录入与查询功能，并没有优化功能。针对这一问题，本文研究重点放在基于钢板库作业优化算法的钢板管理信息系统的开发，将微观层面的优化与宏观层面的信息系统集成。1.3 研究内容及技术路线本文依托 “A船厂钢板管理信息系统”项目，对造船厂钢板库堆场入库问题进行了研究。本文在对优化算法等理论研究的基础上，分析船厂钢板入库作业流程，建立钢板堆场入库作业优化模型，并通过算法求解及案例仿真，证明该方案的可行性及最优性。并且结合现有研究成果，就当前钢板堆场管理进行了信息化改造，实现钢板入库堆位预排，建立了钢板管理信息系统以提高钢板堆成管理水平。本文主要研究的内容如下：l) 分析造船厂钢板入、出库的作业过程，建立优化模型：(1) 给定钢板堆场堆放原则；(2) 分析入库、出库作业过程，结合该两个阶段的特点，建立优化模型；2) 通过遗传模拟退火算法对模型进行求解，并结合数据实例，进行结论分析：(1) 根据模型特点，设计算法，并进行求解；(2) 给出数据实例，并对其计算结果，对该模型的最优方案进行分析；3) 结合钢板堆场实际情况，建立钢板堆场管理信息系统，对钢板堆场进行信息化改造，实现钢板堆场的信息化管理。研究的技术路线如图1.1所示。图1. 1 研究技术路线Fig.1. 1 The flow charts of paper1.4 本文创新点l) 理论研究：在考虑造船厂堆场堆放原则的约束下，同时考虑堆场入库优化及堆场吊机入出库使用效率两大优化目标，对钢板入库作业进行了建模和求解，提出了钢板入库优化方案；2) 系统开发：将算法优化和钢板堆场管理结合在一起，采用RUP建模方法，开发了钢板堆场管理系统。69第2章 论文研究的理论及方法第2章 论文研究的理论及方法本章说明了论文研究的理论基础与方法，主要介绍了堆场作业优化的方法、遗传模拟退火算法，提供本研究的理论基础。2.1 堆场作业优化方法由于堆场作业优化问题的复杂性，导致不同的研究者从不同的角度研究某一方面的问题，产生了许多作业优化问题的类型和方法，并随着对各类优化问题研究的深入及各种交叉学科的发展，涌现出了许多新的作业优化理论与方法。可以将堆场作业优化的研究方法分为两大类：最优化方法和近似/启发式方法。最优化方法主要包括混合整数线性规划(Mixed Integer Linear Programming, MILP)、分枝定界(Branch and Bound, B&B)法以及拉氏松弛法等；近似/启发式最初是由于计算量小并且算法易实现而引入堆场作业优化的，主要包括优先分派规则(PDRs)、人工智能(Artificial Intelligence, AI)、神经网络(Neural Networks, NN)及局域搜索法(NS)，局域搜索法又包括禁忌搜索(Tabu Search, TS)、遗传算法(Genetic Algorithms, GA)和模拟退火(Simulated Annealing, SA)等可以称之为亚启发式(Metaheuristic)的近似优化方法。1) 最优化方法最优化方法是能够产生一个精确最优解的方法，主要用来解决整数规划问题，在20世纪60年代，针对整数规划问题的求解，提出利用更加复杂的数学结构消除隐含非最优解的搜索空间以提高搜索效率的枚举算法，分枝定界法(B&B)在理论研究上有很大成果。由于分枝定界法是一种枚举技术。尽管有效的定界和剪枝过程可以提高搜索速度，但对于较大的调度问题，它要花费较多的时间。分枝定界法的主要问题是整数约束，为了克服这个问题，产生了拉格朗日松弛法(Lagrangian relaxation)，它删除了整数约束而加入了相应的代价和惩罚因子。2) 近似/启发式方法(1) 优先分配规则优先分派规则的近似优化方法，关键在于如何针对给定问题的性能，选择最好的规则。从各规则的优化效果看，SPT能够减小所有作业的平均流程时间，EDD用于优化最大延期相关的目标。对规则之间的切换及由此产生的问题(如出错修复)是近期活跃的研究领域。(2) 人工智能技术80年代出现的人工智能和专家系统在调度研究中占据重要地位，可以产生比优先规则更复杂的基于对整个堆场作业系统的启发式，并能从特殊数据结构中获取大量信息，缺点是计算比较耗时。(3) 神经网络方法神经网络应用于优化问题已有十几年的历史，神经网络模仿了人类学习和对事物的预测能力，是一种并行处理模型。这种模型根据网络拓扑结构、节点特征和训练或学习规则的不同而变化。(4) 局域搜索方法下面是三种有代表性的亚启发式： 模拟退火(SA)SA模仿金属中结晶体冷切的物理过程。在堆场作业优化问题中，当前的优化结果类似热动能系统中的当前状态；目标方程类似热动能系统中的能量方程；全局最优解类似基态。模拟退火也能有效地解决作业优化问题。它是基于Mente Carlo迭代求解的一种全局概率型搜索算法，是一种串行优化算法，其收敛性要求初温应足够高，使解空间各状态能以几乎相同的概率出现。近期在堆场作业优化问题研究领域的大趋势之一是将不同的局域搜索法结合形成混合启发式。 禁忌搜索(TS)TS是Glover47提出的模拟智能过程的一种具有记忆功能的全局逐步优化算法，它是用于获取组合最优化难题近似解的一种高级启发式方法，用这种方法，搜索从一个可行解开始逐步移向一个最优或次优解。在每次移动前，需要依据某种与问题有关的规则确定在现行解周围的相邻解集。然后评估每个相邻解，并移动该相邻解集中的一个最好解。有些移动是禁忌的(禁止的)，因为他们会陷入局部最优或导致循环。这些禁忌的移动被加入禁忌表，一般地，禁忌表的长度越长，则搜索陷入局部最优的可能性越小。但是，长禁忌表需要更多的计算扫描时间，并且在每次迭代中限制了搜索空间。最合适的长度与问题有关，但到目前为止还没有确定的长度的规则可循。 遗传算法(GA)遗传算法是Holland基于自然遗传进化的绝对模型提出的并行搜索机制，GA的5个要素是编码、适应值函数、初始种群、遗传算子和参数设置。由于对钢板堆场入库作业要考虑诸多约束，使得染色体的编码表示非常重要。如果编码不当，会在遗传算子操作时产生不可行解，失去了交叉或变异算子的有效性。GA对初始种群很敏感，交叉算子和编码表示对算法结果会产生不利影响。研究表明，随机产生的初始种群不如用其他启发式(如SA)产生的初始种群好，而修复非法染色体相对容易些，需要对遗传算法进行改进。调度问题中使用的GA技术，大多只强调了遗传算法的独立使用，限制了问题的复杂性。但遗传算法的应用中存在的缺点是：容易产生早熟现象、局部寻优能力较差，且无法避免多次搜索同一个可行解。由于存在的这些问题，通常遗传算法和其他的搜索方法混合使用，可以达到好的效果。2.2 遗传算法及其主要特点2.2.1 遗传算法的基本原理遗传算法和传统的搜索算法不同，它从一组随机产生的初始解，称为“种群(Population)”开始搜索过程。种群中的每个个体是问题的一个解，称为“染色体(Chromosome)”。在遗传算法中最重要的概念是染色体，染色体通常是一串数据(或数组)，用来作为优化问题的解的代码，其本身不一定是解。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用“适值(Fitness)”来测量染色体的好坏。生成的下一代染色体称为后代(Offspring)。后代是由前一代染色体通过交叉(Crossover)或者变异(Mutation)运算形成的。遗传操作过程中，根据适值的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适值高的染色体被选中的概率较高。据此，经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。遗传算法是一个迭代过程，在每次迭代中都保留一组候选解按其解的质量优劣进行排序并按某种指标从中选出一些解，利用一些遗传算子或遗传操作如交叉和变异等对其进行运算产生新一代的一组候选解，重复此过程直至满足某种收敛指标为止。2.2.2 遗传算法的优点和不足遗传算法具有十分顽强的鲁棒性，它采用了许多独特的方法和技术，主要有以下几个方面特点48：1) 自组织、自适应和自学习性。当编码方案与适应度函数确定后，算法将利用进化过程中获得的信息自行组织搜索，这种自组织、自适应的特性，使它能够根据环境变化自动地发现环境的特性和规律，在设计算法时就无需事先描述问题的全部特点。2) 遗传算法的并行性。遗传算法按并行方式对种群进行搜索，而不是按单点进行搜索。它的并行性表现在两个方面，其一是内在并行性，即可让几百甚至数千台计算机进行独立种群的演化计算，待所有机器都运算结束时再通信比较，选取最佳个体。其二是内含并行性，由于采用种群的方式搜索，可同时搜索解空间内的多个区域，并相互交流信息。3) 遗传算法不需要其他辅助知识，只需影响搜索的目标函数和适应度函数。4) 遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。遗传算法采用概率作为一种工具引导其搜索过程朝搜索空间的更优化解区域移动。因此虽然看起来它是一种盲目搜索方法，但实际上有明确的搜索方向。5) 遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。对此编码操作，使得遗传算法可直接对结构对象进行操作。所谓结构对象泛指集合、序列、矩阵、树、图、链和表等各种一维或二维甚至三维结构形式的对象。这一特点，使得遗传算法具有广泛的应用领域。遗传算法本身暗含并行性，随机多样性的种群和交叉操作的作用，使遗传算法倾向于扩大搜索空间以在大范围内搜索。但其局部搜索能力差，容易过早收敛，精度不高，同时有收敛准则和参数选择困难等缺陷。2.2.3 遗传算法的操作流程GA是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体或个体或串的评价和对染色体及其基因的作用49，有效地利用已有信息来指导搜索有希望改善优化质量的状态。图2. 1 标准遗传算法的流程图Fig.2. 1 Standard genetic algorithm flowchart步骤如下：步骤1：令k=0，随机产生N个初始个体构成初始种群P(0)。步骤2：评价P(k)中各个体的适配值(fitness value)。步骤3：判断算法收敛准则。若满足则输出搜索结果；否则执行以下步骤。步骤4：令m=0。步骤5：根据适应度大小执行复制操作来从P(k)中选取两个个体。步骤6：若交叉概率Pc0，1，则对选中个体执行交叉操作来产生两