永凯软件是行业前沿的供应链计划协同（SCP）和生产计划与排程（APS）管理系统的美资供应商，涵盖需求计划、产销协同和生产计划排程。助力实现生产、供给、销售协同，准时交货、降低库存、提升利润，已在一千多家工厂及众多世界500强企业中成功应用。
模拟排程中退火法的几个重要组成部分
发表时间： 2012年11月30日 来源：永凯软件技术(上海)有限公司
模拟排程退火法的几个重要部分为:生成函数(generation)、容忍函数(acceptance function)、 Markov链长、降温过程和结束准则。模拟退火法的改进算法有加温退火法、有记忆的模拟退火法等。文中为Flow Shop问题求解构造了一类模拟退火法,并通过六种不同的随机抽样方式分析了算法渐近收敛于全局最优解,分别解决了具有最小Makespan指标且具有无限中间存储(UIS)、有限中间存储(FIS)和无中间存储(NIS)的 Flow Shop排序问题;文提出了一种改进的模拟退火法,用来解决具有最小Makespan指标的Flow Shop排序问题,并与禁忌搜索法等进行了比较;文用模拟退火法进行机器分组;文用模拟退火法求解有资源约束的排程问题。另外,模拟退火法也可与其他方法相结合进行求解,如文中先用贪心法(greedy法)搜索,将得到的作业序列作为初始解,再用模拟退火法求解单机排程问题,其结果表明这种方法比单纯用模拟退火法和贪心法要好;文中提出了将模拟退火法与启发式算法相结合的方法,求解具有交货期约束的Job Shop排程问题。由于模拟退火法能以一定的概率接受差的能量值,因而有可能跳出局部极小,但它的收敛速度较慢,很难用于实时动态排程环境。
(8)禁忌搜索法
对于复杂的组合优化问题,禁忌搜索也是一种通过领域搜索以获取最优解的方法,Glover曾在文中叙述了它的基本原理。禁忌搜索是一种迭代方法,它开始于一个初始可行解S,然后移动到领域N(S)中最好的解s’,即s’对于目标函数F(S)在领域N(S)中是最优的。然后,从新的开始点重复此法。为了避免死循环,禁忌搜索把最近进行的T个移动(T可固定也可变化)放在一个称作tabu list的表中(也称短期记忆),在目前的迭代中这些移动是被禁止的,在一定数目的迭代之后它们又被释放出来。这样的tabu list是一个循环表,它被循环地修改,其长度T称作Tabu size。最后,还须定义一个停止准则来终止整个算法。由于tabu list的限制,使其在搜索中有可能跳出局部极小。文分别提出了解决flow shop排程问题的禁忌搜索算法。在文中为了更有效地搜索解空间,引入了插入和移动相结合的机制提高了搜索效率。文中采用了并行禁忌搜索法以加快搜索速度。文中针对求解公共交货期下带有等待时间惩罚的提前/拖期单机排程问题,提出了一种禁忌搜索法。
标签：
新闻推荐
生产管理与生产计划的目标
供应链管理软件
生产管理中的高级计划与排程优化
2018年12月7日 强强联手，共同推进电子器件领域APS应用典范 风华高科生产自动化工业互联网应用项目-APS项目启动会
生产管理软件系统基于信息化的解决方案
热门标签更多
联系 客服
联系客服电话：021-68886010
客服 热线
关注 微信
永凯APS微信公众号