可添加/去除机器的动态布局优化研究

作     者：吴畅 

作者单位：上海交通大学 

学位级别：硕士

导师姓名：董明

授予年度：2008年

学科分类：120202[管理学-企业管理（含：财务管理、市场营销、人力资源管理）] 12[管理学] 1202[管理学-工商管理] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：动态布局 添加/去除机器 模拟退火算法 动态规划 最短路 仿真优化 

摘      要：动态布局问题(Dynamic Layout Problem: DLP)对于动态商业环境下的制造企业有着重要的意义。根据产品需求是否确定,该问题可分为两种情况:(1)基于确定性需求;(2)基于随机需求。本文针对一类可添加和去除机器,且基于不等面积机器和连续布局空间表达的DLP问题,结合国内外研究现状对上述两种情况分别进行深入研究。 首先,作为研究的基础,对该问题进行定义,建立了布局评价体系,将总成本分为物料搬运成本、机器重置成本、空间利用成本和产能损失成本。提出了一个空闲空间搜索算法实现对可用空闲空间的搜索,结合添加机器和去除机器的特点,提出了添加机器和去除机器的启发式规则。 接着,针对确定性需求的情况,不考虑生产中的随机因素,将问题抽象成基于动态规划的混合整数规划模型和基于最短路的图论模型。提出相应的基于动态规划的模拟退火算法(Dynamic Programming based Simulated Annealing: DPSA)和基于Auction最短路算法的模拟退火算法(Shortest Path based Simulated Annealing: SPSA),并且对算法进行了参数设计。针对不同算例间可比性较弱的缺点,建立了算例对比指标体系。通过多个算例对两个算法进行比较分析,结果表明两个算法都要优于普通的SA。一般说来,SPSA求解的结果要好于DPSA,而DPSA则具有更快的求解速度。 然后,针对随机需求的情况,根据产出等于需求的生产均衡原则,分析得到了随机需求下考虑产能损失约束的批次到达速率公式,建立了基于随机需求的数学模型。讨论了系统中的两类随机事件和三种调度准则。在此基础上,建立了可添加和去除机器的生产仿真系统,允许在生产进行的同时调整设备。设计了优化模块,并通过接口将其与仿真模块结合,实现了仿真优化算法结构。最后通过算例验证了仿真优化算法的有效性以及仿真系统的可信性。