实际中生产排程问题有以下特点-永凯软件技术（上海）有限公司

生产计划管理知识

返回列表

实际中生产排程问题有以下特点

发表时间： 2012年10月12日　　　　　来源：永凯软件技术(上海)有限公司

实际中生产排程问题有以下特点

　　(1)基于排序的方法

　　该方法是先有可行性加工顺序,然后才确定每个操作的开工时间,并对这个顺序进行优化,它虽然属于_____近似算法,但有可能达到最优的排程方案。它主要包括邻近搜索法,它在生产排程领域得到了相当广泛的应用,在探索解空间时,仅对选定的成本函数值的变化做出响应,因而通用性强。这类方法包括局部探索(Local Search)、模拟退火法(Simulated Annealing)、列表寻优法(Table Search),遗传算法(Genetic Algorithms)。邻近搜索虽然可能得到最优的排程方案,但也存在各自的不足,很多学者采取混合算法来弥补单一方法的不足。

　　(2)启发式图搜索法

　　对于表述为整数规划的排程问题,最初采用分枝定界法来解决,而后其他的启发式图搜索法也被应用于解决排程问题。Balas将排程排序问题用一个disjunctive图来表示,首先构造一个可行解,采用基于隐枚举的搜索方法不断提高解的次优性;采用束搜索法(beam search)来识别瓶颈机器,进行排程;为了解决搜索空间太大的问题,通过对分枝定界法和束搜索法进行系统的分析,提出了一种过滤束搜索法(filter beam search),用来解决单台机器提前/延期问题和加权延期的FlowShop问题;研究了基于A*的优先树搜索法的优化作业排序问题:针对基于树搜索的优先A*算法需要大量内存的问题,提出了一个图搜索法,并对两种方法作了比较;为解决Job Shop排程问题对A*算法作了两点改进:1) 在搜索过程中只展开有限节点;2) 采用加权的评价函数。对于图搜索算法,如何提高搜索效率并减少内存使用以解决规模较大的问题,还需要进一步探索。

　　(3)模拟退火法

　　模拟退火算法(SA)将组合优化问题与统计力学中的热平衡问题类比,另辟了求解组合优化问题的新途径。它通过模拟退火过程,可找到全局(或近似)最优解。其基本思想为:把每种组合状态Si看成某一物质系统的微观状态,而将其对应的目标函数C(Si)看成该物质系统在状态Si下的内能;用控制参数T类比温度,让T从一个足够高的值慢慢下降,对每个T,用Metropolis抽样法在计算机上模拟该体系在此T下的热平衡态,即对当前状态Si作随机扰动以产生一个新状态s’,如果______C(s’)模拟退火法的几个重要部分为:生成函数(generation)、容忍函数(acceptance function)、Markov链长、降温过程和结束准则。模拟退火法的改进算法有加温退火法、有记忆的模拟退火法等。为Flow Shop问题求解构造了一类模拟退火法,并通过六种不同的随机抽样方式分析了算法渐近收敛于全局最优解,分别解决了具有最小Makespan指标且具有无限中间存储(UIS)、有限中间存储(FIS)和无中间存储(NIS)的Flow Shop排序问题;提出了一种改进的模拟退火法,用来解决具有最小Makespan指标的Flow Shop排序问题,并与禁忌搜索法等进行了比较;用模拟退火法进行机器分组;用模拟退火法求解有资源约束的排程问题。另外,模拟退火法也可与其他方法相结合进行求解,先用贪心法(greedy法)搜索,将得到的作业序列作为初始解,再用模拟退火法求解单机排程问题,其结果表明这种方法比单纯用模拟退火法和贪心法要好;提出了将模拟退火法与启发式算法相结合的方法,求解具有交货期约束的Job Shop排程问题。由于模拟退火法能以一定的概率接受差的能量值,因而有可能跳出局部极小,但它的收敛速度较慢,很难用于实时动态排程环境。

　　(4)禁忌搜索法

　　对于复杂的组合优化问题,禁忌搜索也是一种通过领域搜索以获取最优解的方法Glover叙述了它的基本原理。禁忌搜索是一种迭代方法,它开始于一个初始可行解S,然后移动到领域N(S)中最好的解s’,即s’对于目标函数F(S)在领域N(S)中是最优的。然后,从新的开始点重复此法。为了避免死循环,禁忌搜索把最近进行的T个移动(T可固定也可变化)放在一个称作tabu list的表中(也称短期记忆),在目前的迭代中这些移动是被禁止的,在一定数目的迭代之后它们又被释放出来。这样的tabu list是一个循环表,它被循环地修改,其长度T称作Tabu size。最后,还须定义一个停止准则来终止整个算法。由于tabu list的限制,使其在搜索中有可能跳出局部极小。分别提出了解决flow shop排程问题的禁忌搜索算法。为了更有效地搜索解空间,引入了插入和移动相结合的机制提高了搜索效率。采用了并行禁忌搜索法以加快搜索速度。针对求解公共交货期下带有等待时间惩罚的提前/拖期单机排程问题,提出了一种禁忌搜索法。

标签：

上一篇：使用APS的流程与需求计划的决策支持利润APS

下一篇：活性潜力的APS的目的是支持潜在的好处

新闻推荐

热门标签更多

探索

浏览

永凯APS系统

所有产品

全球领先的APS生产管理与物料控制解决方案

咨询：400-076-7600

永凯APS执行监控

所有产品

全球领先的APS生产管理与物料控制解决方案

咨询：400-076-7600

永凯供应链计划管理

所有产品

全球领先的APS生产管理与物料控制解决方案

咨询：400-076-7600

浏览

解决方案

以下为永凯APS生产管理与物料控制解决方案行业实践饼状图：

汽配行业解决方案

以下为永凯APS生产管理与物料控制解决方案行业实践饼状图：

机械行业解决方案

以下为永凯APS生产管理与物料控制解决方案行业实践饼状图：

注塑行业解决方案

以下为永凯APS生产管理与物料控制解决方案行业实践饼状图：

家电行业解决方案

以下为永凯APS生产管理与物料控制解决方案行业实践饼状图：

电子行业解决方案

以下为永凯APS生产管理与物料控制解决方案行业实践饼状图：

更多行业解决方案

以下为永凯APS生产管理与物料控制解决方案行业实践饼状图：

探索

浏览

导入业绩

以下是各行业类型的导入业绩比率表：

汽配行业

所有客户

以下是各行业类型的导入业绩比率表：

轮胎行业

所有客户

以下是各行业类型的导入业绩比率表：

机械行业

所有客户

以下是各行业类型的导入业绩比率表：

电子行业

所有客户

以下是各行业类型的导入业绩比率表：

其它行业

所有客户

以下是各行业类型的导入业绩比率表：

新闻详情

生产计划管理知识

实际中生产排程问题有以下特点

微信扫码关注

可以实时查看最新动态

登录

客户案例

产品推荐

解决方案

提供业务咨询：