【作者】 胡燕海；

【导师】 严隽琪； 马登哲；

【作者基本信息】 上海交通大学 ， 机械制造及其自动化， 2008， 博士

【摘要】 通过对若干造船企业的调研发现,其室内加工阶段多个车间之间存在密切的工艺联系。室内加工阶段的特点为工件流动,设备、人员不流动,造船企业的室内加工阶段主要包括钢板预处理中心、切割中心、平直分段生产中心(平直中心)、曲面分段生产中心(曲面中心)的加工车间。期间,工件在多个生产中心之间混杂流动,如钢板经预处理后,可能一部分流入切割中心,另一部分流入平直中心,还有一部分流入曲面中心。而进入曲面中心的工件可能一部分来自预处理中心,另一部分来自切割中心,还有一部分来自平直中心。又由于船舶制造为订单式单件生产,并且在船舶制造过程中存在工件紧急订单等动态作业的特性。由于船舶制造中工件流动的混杂性、生产批量的单件性、作业过程的动态性,各车间之间必须紧密合作,才能实施造船精细化管理。但我国传统的造船企业生产管理模式属于单个车间各自为政的经验式管理,每个车间制定作业计划的周期从十余天到数十天不等。后续车间对某个工件的加工必须等到前一车间在一个生产周期结束后将其送至后续车间才能开始。因此造成了我国企业造船周期远远高于韩国、日本等生产管理水平先进的国家,并进一步导致了我国造船企业中间产品库存量大、设备利用率低等问题。为了提高我国造船企业的生产管理水平,本文作业计划方面进行了一些理论与方法研究,主要包括:1)提出了跨车间集成作业计划的学术观点,并提出多层次作业分析法将造船企业的作业情况分解为单元作业层、车间作业层和跨车间作业层进行分析。单元作业层主要包括平行流水作业、含多功能机床的混杂流水作业这两种在造船企业比较常见的作业方式。而车间作业层中将包含多种单元作业层作业,本文分析了造船企业中常见的网状流水车间和多作业车间。跨车间作业层为对多个车间进行整体作业计划。通过国内某大型造船企业一批工件的工程应用发现,与传统方法相比,跨车间集成作业计划可缩短加工流程时间45%。2)采用网络理论对所研究问题构建多级非连接图模型进行表达。对于经过多层次作业分析的IS-ISP问题,很适合采用网络理论建立多级非连接图模型。模型各节点的连通关系可有效表达制造系统中设备、工件等要素的约束关系;各连通关系上的赋权值可以表达设备、工件的优先级,可用时间、完成时间等约束;利用网络理论中的最短路径问题等反映制造系统作业计划的优化指标。制定作业计划就是在满足约束的条件下寻找使某一项或几项指标最优化的工件排序,并确定每个工件在各加工阶段的开始加工时间、加工完成时间。对应制造系统跨车间集成作业的多层阶结构,可用多级非连接图模型表达。多级非连接图模型不仅可以表达数学规划所能表达的约束条件,而且非常适合于蚁群算法等基于路径搜索的优化方法。算法的分级寻优过程不仅可以大大减少搜索路径数量,降低计算复杂度,还可充分利用下一级路径的搜索方法、以及信息更新策略。因此,其有助于缩短这类路径搜索算法每次循环的时间,提高其寻优效率。本文以平行流水作业计划为例,证明了多级非连接图模型有利于显著降低问题的计算复杂度。3)将遗传算法中的交叉、变异算子引入蚁群算法中,构成混杂蚁群算法进行跨车间集成作业计划问题求解。对于建立了非连接图建模的组合优化问题,很适合采用蚁群算法等基于路径搜索的算法。但蚁群算法尚存在易于陷入局部收敛的风险,而遗传算法的交叉、变异算子可使运算过程跳出局部收敛,因此本文将其引入蚁群算法中,构成混杂蚁群算法。蚁群算法和遗传算法是两种近年发展起来的性能较好,且具有良好互补性的智能算法。混杂蚁群算法能充分利用遗传算法进化速度快和蚁群算法收敛性好的特点。将混杂蚁群算法通过多种规模的算例与其它算法进行性能对比,发现其应用于大规模问题时,寻优速度、收敛性方面都有一定优势。然后将该算法应用于造船企业生产实例。4)针对造船企业制造系统中经常出现紧急订单等扰动情况,研究跨车间动态集成作业计划问题。当紧急订单出现时,原有工件一般都有一部分已进入系统进行加工。需要在这种前提下,对加工工件重新制定作业计划,以使紧急订单得到尽快加工,而原有工件的加工速度尽量少受影响。工程研究表明,在一批原有工件中插入一个紧急订单工件后,原有工件平均流程时间延迟少于1%;而紧急订单平均流程时间与他们在设备上的加工时间和之比为1,即紧急订单已最快速度得到了加工。其它生产扰动情况也可建立相应的非连接图模型进行求解。更多还原

【Abstract】 After the investigation on the manufacturing system in some typical shipyards, it is found that the manufacturing in the shops has the close procedure relationship. The feature of manufacturing in shops is that the jobs flow among fixed equipments. The manufacturing in shops for jobs of a shipyard mainly is taken in steel sheet pre-treating center, cutting center, flat subsection manufacturing center and curve subsection manufacturing center. During this period, jobs are processed in several shops hybridly. For example, after the steel sheets are pre-treated, some of them flow to the cutting center, some of them flow to the flat subsection manufacturing center, and the other flow to the curve subsection manufacturing center. On the other hand, the jobs flowing into the curve subsection manufacturing center may come from the pre-treating center, the cutting center, and the flat subsection manufacturing center. Besides, the batch size of shipmaking is usually one basing on order. And there is usually rush order jobs in the manufacturing. Because of these features in the shipmaking, the precision management may be achieved only with the tight cooperation among shops.But traditionally, the production management in a shipyard in our country is that each shop is managed by person’s experience separately. The period to make scheduling for each shop is changing from about two weeks to tens of days. The manufacturing of one job in the following shop can’t start until it is finished in the previous shop and sent to the following shop at the end of scheduling period in the previous shop. This is the reason that makes much longer lead time for ship building in our country than that in Korea or Japan where the production management is more advanced. It further results in the large in-process inventory and the low equipment utility.In order to improve the production management, some studies on theory and method about scheduling are conducted in this paper, which include following aspects.1) The academic idea of inter-shop integrated scheduling problem (IS-ISP) is proposed according to the production practice in the shipyard. And the inter-shop is discomposed into three layers, which are cell layer, shop layer and inter-shop layer, with hierarchy analysis method. The cell layer concerns identical parallel flow shop scheduling problem (IPFSP) and hybrid flow shop containing multi-functional machines (HFSP-MFM) that can be often found in the shipyard. In the shop layer, there often exists more than one cell layer shop. Crossed flow shop scheduling problem and multi-shop scheduling problems that are often seen in the shipyard are studied. Inter-shop layer refers to make schedule for several shops. By the industrial application in a domestic big shipyard, it was found that the makespan would be shortened by 45% with IS-ISP comparing the traditional scheduling method.2) The network theory is employed to establish multi-level disjunctive graph model for the IS-ISP. For the IS-ISP, which is analyzed by hierarchy analysis method, it is very suitable to establish a multi-level disjunctive graph model by employing the network theory. The link situation between nodes in the models will represent the constraints of the machines, jobs in the manufacturing system; The values related with the links will represent the constraints such as the precedence of jobs and machines, as well as the constraints such as ready time or due time of jobs and machines; The shortest path will represent the optimization criterion for the scheduling problem. The scheduling problem is to queue the jobs so that one or several objectives for the manufacturing system will be optimized under some constraints. Then the beginning time and completing time of each job on every processing stage will be determined. The hierarchy structure of the inter-shop scheduling problem will be described by multi-level disjunctive graph model. The multi-level disjunctive graph model not only can express all constraints that the mathematic programming is able to describe, but also is extremely suitable for the algorithms based on path searching such as ACO algorithm. The searching procedure level by level can not only reduce the number of path to be searched, but also make use of the searching methods and information renewing methods used at the lower levels. So the multi-level disjunctive graph model is helpful to shorten the time for each computation generation, and to improve the searching efficiency.3) A new hybrid ant colony optimization (HACO) algorithm is produced by introducing the crossover and mutation oparators in the genetic algorithm (GA) into the ACO algorithm. For the combined optimization problem that is described with disjunctive model, it is extremely suitable for apply ant colony optimizaiton (ACO) algorith, which is based on path searching. But the ACO has the shortage to fall in the local convergency, while the crossover, mutation operators in the GA is able to jump out of the local convergency during the optimizaiton. So crossover, mutation operators in the GA are introduced in the ACO. And the HACO is conducted. GA and ACO are both newly developped meta-heuristic algorithms that not only have good performance, but they can cooperate each other very well. The HACO algorithm makes use of the advantages of the GA which is rapid at evolution and the ACO which is good at convergency. The HACO is compared with other algorithms by applying to kinds of instances of different scales. It is found that the HACO has advantages on both optimizaiton speed and solution convengency especially for large scale instances. Then the algorithm with the best feature is apply to the real scheduling in the shop floor.4) The disturbance of rush order often occur in the real proction. When the rush order comes, some of the original jobs have already been processed in some stages. In such situation, the original schedule needs to be reworked so that the rush order would be processed as soon as possible, and the original jobs would not be delayed too much. Industrial application shows that after a rush order job is inserted into a batch of jobs, the postponed time for original jobs is less than 1%, but the ratio of makespan of the rush order job and the sum of the processing time on all stages is 1, which means it will be produced on time. Other production disturbance can also be solved by establishing the corresponding disjunctive model.更多还原