发表时间： 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排程问题的禁忌搜索算法。为了更有效地搜索解空间,引入了插入和移动相结合的机制提高了搜索效率。采用了并行禁忌搜索法以加快搜索速度。针对求解公共交货期下带有等待时间惩罚的提前/拖期单机排程问题,提出了一种禁忌搜索法。