论文总字数：20803字

目 录

1 引言 1

1.1 研究背景和意义 1

1.2 国内外研究现状 1

2 遗传算法 2

2.1 遗传算法介绍 2

2.1.1 遗传算法思路 2

2.1.2 遗传算法步骤 3

2.1.3 遗传算法伪代码 3

2.2 多目标优化问题 4

2.2.1 多目标优化问题描述 4

2.2.2 Pareto最优解 5

2.2.3 多目标问题的两个关键问题 5

2.2.4 快速非支配排序 5

2.3 NSGA-II算法 6

2.3.1 NSGA-II算法介绍 6

2.3.2 NSGA-II算法步骤 6

2.3.3 NSGA-II算法流程 7

3 基于多目标优化的设施动态布局算法 8

3.1 问题的描述 8

3.2 问题的转化 8

3.2.1 符号的定义 8

3.2.2 优化目标及数学模型 8

3.3 算法描述 10

3.3.1 NSGA-II算法描述 10

3.3.2 NSGA-II算法改进 10

3.3.3 算法实现的核心代码 12

4计算结果与分析比较 15

4.1 算例与计算结果 15

4.2 结果分析 20

4.3 运行结果坐标与截图 20

5 总结与展望 22

5.1 本文所做的主要工作 22

5.2 主要创新点 23

5.3 研究展望 23

参考文献 24

致谢 25

基于多目标优化的设施动态布局算法研究与实现

刘昕玥

ABSTRACT: Rapid changes in market demand lead to gradual inadaptation of original layout of enterprises to the current production,which requires companies to develop production plans in line with real-timemarketdemand and lay out the workshop production facilities according to production plans.In this paper,a continuous model of unequal area facilitiesin multi-planned workshop is established and solved by NSGA-II genetic algorithm,based on the variation of the constraints such as the logistics matrix in each subprogram schedule as well as the reuse cost、non-logistics relation and area utilization rate are optimized,and the mutation operation in the genetic algorithm is improved. In addition, the recent farthest method of non-dominated solution is proposed.Using java language to achieve the algorithm and complete the system design.The experiment finally obtains the set of solutions which can optimize the objective function.

Key word: dynamic layout of facilities; continuous model; NSGA-II; genetic algorithm

1 引言

在不断剧烈的竞争和一直变化的市场需求下，企业必须不断提高生产力，减少产品的生产成本，提高企业效益，以提高自身在市场中的竞争力。动态设备布局问题就是在多个计划期内确定每个设备的最优位置，它要求各个计划期内的物料搬运成本和下一个计划期重布局成本最小，所以本课题的研究对于企业的生产比较重要。本章主要介绍了动态设施布局问题的研究背景和意义，以及国内外的研究近况。

1.1 研究背景和意义

对企业生产系统来说，一个高效的车间设施布局（Facility Layout, FL）显得尤为重要。研究表明^[1]：产品生产过程中，原料的搬运费用占了生产成本的20%~50%，然而，合理的设备布局却能够降低10%~20%的原料搬运费用。而市场需求的快速变化，使企业原有的布局，逐渐不适应现阶段的生产需求，这就要求企业根据实时的市场需求制定生产计划，并根据生产计划对车间的生产设备进行布局。动态设施布局问题就是确定每个设备在多个规划期间的最佳位置，要求每个规划期间的物料处理成本以及下一次计划重新布局的成本最小。

本课题的研究目的在于建立动态设施布局问题的数学模型，并用多种方法对其求解，获取各个计划期的最优布局，以减少生产过程中的物料搬运成本和计划期更替时的设备重置费用，从而增加商品的最终利润。

1.2 国内外研究现状

布局问题由高斯自1831年开始研究，至今已有上百年的历史。布局问题有动态和静态之分。在研究静态布局问题时，各设备之间的物流量不会随时间而变化，当物流量随时间变化时，会变成动态布局问题。

过去，大多数人都对静态设施布局问题进行研究，忽视了动态设施布局问题，但随着市场经济的快速发展，市场需求不断变化，要求企业能够根据需求来布置生产设备，人们对动态设施布局问题的研究也开始变得越来越多。

动态设备布局是由连续的多个静态设备布局构成，是一个在车间或者被称为容器中的二维坐标下，放置设备的问题。由于车间大小有限制而每个设备有长宽且没有弹性，所以此类问题有两个主要限制：（1）各个设备之间不能互相重叠；（2）整个布局不超出车间的范围。

Reimert和Gambrell于1966最早对动态设备布局问题进行了研究。一般来说，动态设备布局问题的研究一般也可分割为建立数学模型和应用算法进行求解两个步骤。Balakrishnan^[2]、李波^[3]的分析，指出了将确定最小化时间轴上的物料传输费用和相邻计划期的设备重置费用之和作为优化目标是动态布局问题的本质。物料传输费用可参考静态设施布局问题，设施重置费用成为动态设备布局问题的核心，所以Baykasoglu与Urban^[4]研究了重布局费用的递归模型。连续模型大多被用在解决静态设施的精确定位上，很少用来解决动设备布局问题，但Dunker^[5]在2005年用连续模型研究了不等面积动态设施布局问题。MingDong^[6]等于2009年，建立了以物料搬运费用、区域利用成本、设备重置费用、产能损耗之和为优化目标的模型。郭爽、徐克林^[7]等于2011年提出了以物料搬运费用、设备重置费用、停产的产能损耗之和为优化目标的数学模型，平衡了物料搬运费用、设备重置费用、停产的产能损耗之间的关系。黄君政^[8]等于2014年也提出了以物料搬运费用与设备重置费用为优化目标的动态设备布局问题的函数模型。

在对数学模型的算法解决方案中，人工神经网络方法、模拟退火算法、遗传算法、启发式移动策略和梯度法等被用来解决动态设施布局问题，其中，模拟退火算法、遗传算法和粒子群算法等全局搜索方法搜索效率较低，而梯度法、共轭梯度法等局部搜索方法易于陷入局部最优，因此一般将两者结合使用。

Tate和Smith^[9]于1995年将遗传算法应用于设备布局问题，Heragua和Alfa^[10]使用模拟退火算法来求解最佳布局。在国内郭爽^[7]等于2011年将引入自适应策略的改进遗传算法用于动态设施布局问题的求解，黄君政^[8]等于2014年以带精英策略的非支配遗传算法对该问题进行求解，将传统加权方法用于解决多目标问题时，弥补了难以确定加权系数以及多目标无法同时优化的不足，求出非支配解集，再按照实际状况选出最好的结果。

本文以动态设施布局问题为背景，从实际出发，将车间与设备假设成有形状规则的矩形。在二维平面内，将动态设施布局问题抽象为在矩形容器内矩形设备的摆放问题。本文采用NSGA-II算法对问题进行求解。

2 遗传算法

2.1 遗传算法介绍

遗传算法（Genetic Algorithm，GA）是Holland于1975年提出的计算模型，它通过模拟自然进化过程来搜索最优解。它将问题的求解表示为“染色体”进化过程，一直进行选择交叉变异操作，最终得到最优的个体，以此得到最优解。

2.1.1遗传算法思路

1. 初始化：令进化代数计数器t=0，最大进化代数为T，随机生成一个数量为M的初始种群。

（2）个体评价：算出种群中每个个体的适应度。

（3）选择操作:选择生存概率更高的个体，减小有效基因的损失。选择操作以种群中个体的适应度为基础。

（4）交叉操作：交叉算子对于遗传算法作用重大。

（5）变异操作：改变种群中的个体基因遗传价值。种群执行选择、交叉、变异操作之后得到下一代种群。

（6）终止条件判断:若t=T,则输出在进化过程中适应度最大的个体，并把它作为最优解，停止计算。

2.1.2 遗传算法步骤

（1）随机产生一个初始种群，计算种群中每个个体的适配值。

（2）如果算法满足收敛准则，就输出搜索结果，否则继续以下步骤。

剩余内容已隐藏，请支付后下载全文，论文总字数：20803字

相关图片展示：