是指调度的优化随时间推移在一个接一个的时间段内动态进行生产调度。被动调度伍eactveicshdeuilns)则是指当生产过程发生变化,原来的调度不再可行时所进行的调度修正。
被动调度是在原有的静态调度的基础上进行的,因此它的调度目标是尽量维持原调度水平,性能指标下降越小越好。
滚动调度既可以在静态调度的基础上进行(leetal.,19%;徐晖等,1993)也可直接进行(方剑等,1997),其最终目的都是尽量在当前优化区域内得到最优或近优调度。
再调度问题最关心的要属在线计算能力问题。如果一个好的算法,能够得到调度问题的最优解,但却不能在有效的时间内完成,那么该算法对实际的调度来讲是无用的。为了能在有效的时间内得到一个较为合理的调度,完成当前的任务调度,人们希望将问题规模减小,在一个时间段较小的问题空间内得到一个较好的解答,因此大都采用启发式方法(sietal.,1996;Knak nredala
以
ai.,.1994;Esftathiou,1996;Shakhlevieh,19%)和基于预测的滚动优化方法毋keer,1977,1979;Rodri esal.,1996;方剑等,2997)。
大多数的动态调度是由于加工时间的变化引起的(sIhaetal.,1996),少数是由订单的变化和设备故障仪nakamadealaetal.,1994)等引起的。对于由加工时间变化引起的动态调度,由于其批量和加工顺序一般是根据最早的最优(或可行)调度设定好的,因此,在这种情况下,一般不再需要重新分配批量和加工顺序,只是调整各加工任务的加工起始时间,以便尽量得到一个近优的调度或保持原有调度的性能指标伍nakaamdealaetal.,1994)Oocttetal.(1989)研究了考虑加工时间变化的情况下,多产品批处理化工厂的被动调度的性能。他们通过检测实际调度和目标调度(相当于静态调度)之间的差别,前向或后向移动各未完成产品的加工任务的起始加工时间,以尽量减小加工时间变化对目标调度的影响。他们只处理了当前加工时间变化,并未考虑各任务间的等待时间约束,以及将来可能的加工时间变化。Ihsiiet.ai(l996)则考虑了将来可能的加工时间的变化,给出了两条时间修正策略,以处理各种不同的时间约束和未来瓶颈任务的处理。该调度调整算法的特点在于考虑了各任务间松驰时间的插入,以尽量吸收以后加工时间变化所引起的时间调度。调度修正算法只是作为一个子模块,受上一层调度系统控制。当现有的松驰
时间插入算法不能求得可行解时,由上层调度算法考虑批量调整或再排序问题。所以该调度修正算法的前提是上层调度算法能够在有效的时间内产生一个最优或近优甚至只是可行的调度方案。
由订单变化和设备故障引起的再调度问题,至少会引起部分加工顺序的变化,原有的加工批量一般保持不变,重点调整仍是加工任务的加工时间。
滚动调度的滚动优化区域的设定和预测模型是非常关键的。滚动优化区域的设定主要由优化算法的计算速度和调度的实时性所决定,既可以时间区域段(方剑等,1977)为划分标准,也可以加工任务数为划分标准（ashaetal.,1996)。预测输出一般为产品的完成时间仪（nakamadeala,1994)，决策变全则为一些加工任务的安排(起始加工时间和加工单元)扭（driugesatal.,1996)·滚动优化虽然不能得到全局最优调度,但由于实时性好,能适应动态的调度环境,所以更多地为生产实际所接受。滚动优化要以准确的预测模型为基础,然而有时在生产实际中难以得到这样一个模型,所以如何利用调度专家经验指导调度问题的解决(建模和求解),仍有待进一步研究。
1.3.4生产调度的柔性
在一个调度方案确定以前,人们总是希望了解这个方案能否顺利执行或者说它的抗干扰能力有多大,这主要是由于生产过程中存在着许多不确定因素。最常见的不确定因素有加工时间的变化,产品需求量的变化,交货期的改变及设备故障等(sIhaet)。
当生产过程中出现的干扰不是太大,如小的加工时间变化,短时间的原料供应变化和产品需求时间或需求量的变化等,决策者希望小改或不改变原有的调度。只牺牲一点性能指标,以保持生产的稳定性。此时我们可以说在这些不确定性因素的干扰下,生产调度仍然是稳定的,这种调度的稳定性直观地讲是取决于这个调度的初始的柔性似（Impetal.,1997)。
为了使调度具有一定的柔性,往往在各加工任务的各作业之间,加上一定的等待时间(或松弛时间),以消除作业加工时间变化给调度带来的影响(Ishaetai.,、19%;HmPetal.1997)。如登山法,若一个细微变动能改善质量,则沿该方向前进,否则取相反方向。然而复杂问题会使解空间中出现若干局部最优解,传统的方法很容易限于局部最优解而停滞不前,很多传统的优化算法往往是确定性的,从一个搜索
点到另一个搜索点的转移有确定的转移方法和转移关系,这种确定性往往可能使得搜索永远达不到最优点,因而限制了算法的应用范围。模拟退火算法(SA)以一种概率的方式来进行搜索,增加了搜索过程的灵活性。
1.3.5引进算法控制参数
引进类似于退火温度的算法控制参数,它将优化过程分成各个阶段,并决定各个阶段下随机状态的取舍标准,接受函数由Mert 算法给出一个简单的数学模型。模拟退火算法的两个重要步骤是:一是在每个控制参数下,由前迭代点出发,产生邻近的随机状态,由控制参数确定的接受准则决定此新状态的取舍,并由此形成一定长度的随机Markov链:二是缓慢降低控制参数,提高接收准则,直至控制参数趋于零,状态链稳定于优化问题的最优状态,提高模拟退火算法全局最优解的可靠性。
1.3.6使用对象函数值进行搜索
传统搜索算法不仅需要利用目标函数值,而且往往需要目标函数的导数值等其它一些辅助信息刁`能确定搜索方向,当这些信息不存在时,算法就失效了。而模拟退火算法仅使用由目标函数变换来的适应度函数值,就可确定进一步的搜索方向和搜索范围,无需其它的辅助信息。需要着重指出的是:模拟退火算法的适应度函数不仅不受连续可微的约束,而且其定义域可以任意设定,对适应度函数唯一的要求是对于输入可计算出加以比较的正的输出。这个特性对很多无法或很难求导数的函数,或导数不存在的函数的优化问题,以及组合优化问题等,应用模拟退火算法就比较方便。另外,直接利用目标函数值或个体适应度,也可以把搜索范围集中到适应度较高的部分搜索空间,从而提高搜索效率。
1.3.7隐含并行性
并行算法是60年代发展起来的,其发展速度相当快。有些专家甚至认为目前提高计算机系统性能的唯一方法是“选择大量的并行”。从目前情况看,并行算法的设计主要采用两种方法:一是对现有的串行算法加工改造,使之成为好的并行算法;二是结合所用并行计算机的结构特点,直接设计新的并行算法。
模拟退火算法(SA)的特点模拟退火算法(AS)源于统计物理学,是模拟熔化状态下物体由逐渐冷却至最终达到结晶状态的物理过程。模拟退火算法是利用问题
的求解过程与熔化物体退火过程的相似性,采用随机模拟物体退火过程来完成问题的求解,也就是在控制参数(温度)的作用下对参数的值进行调整,直到所选取的参数值最终使能量函数达到全局极小值。
模拟退火算法(SA)与其它搜索方法相比,具有如下的特点:
以一定的概率接受恶化解。模拟退火算法(SA)在搜索策略上与传统的随机搜索方法不同,它不仅引入了适当的随机因素,而且还引入了物理系统退火过程的自然机理。这种自然机理的引入使模拟退火算法在迭代过程中不仅接受使目标函数变“好”的试探点,而且还能以一定的概率接受使目标函数值变“差”的试探点,迭代中出现的状态是随机产生的,并不强求后一状态一定优于前一状态,接受概率随着温度的下降而逐渐增大。传统的方法往往是从解空间的一个初始点开始最优解的迭代搜索过程。
模拟退火算法改造为并行算法还是比较容易的。目前常见的有以下几种并行策略:
操作并行策略,试演并行策略,区域分裂策略和混乱松弛策略等。这儿种并行算法在不同程度上对解的质量,收敛速度上较模拟退火算法优,由此可预见,大规模的并行计算模式将成为研究全局优化问题的主流,即模拟退火算法隐含并行性,它是优于其它求解过程的关键所在。另外模拟退火算法的隐含并行性还有助于处理非线性问题。
就搜索复杂区域而言，模拟退火算法最善于搜索复杂地区,从中找出期望值高的区域,在求解简单问题上效率并不高。
就模拟退火算法(AS)的研究现状而言，模拟退火算法(SA)在理论上已得到证明,它可以达到全局极小值,所以它备受专家与学者的青睐。目前,关于模拟退火算法的研究通常分为两类。第一类是基于有限状态奇异马尔可夫链的有关理论,给出模拟退火算法的某些关于理想收敛模型的充分条件或充要条件,这些条件在理论上证明了当退火三原则(初始温度足够高、降温速度足够慢、终止温度足够低)满足时,模拟退火算法以概率1达到全局最优解;第二类是针对某些具体问题,给出了模拟退火算法的很多成功应用。
事实上,正是由于专家和学者对该算法的钻研,刁`让该算法从经典的模拟退火算法走到了今天的多样型的模拟退火算法,比如快速模拟退火算法,使得该算法
的速度和收敛性都得到较大提高,再比如适应性的模拟退火算法,使得该算法具有智能性;再比如现在有学者提到的遗传一模拟退火算法,就是将遗传算法和模拟退火算法二者的优越性结合起来。不能忽略的是,每种算法的提出都与其应用范围紧密结合,这样刁`使得改进的算法在其应用领域具有较好的适用性。由于模拟退火算法(SA)从理论上可以达到全局极小值,所以对该算法的研究刁`更有实际意义,众多学者正在努力钻研将其一般化,使其具有普遍适用性。
1.4研究内容
本论文主要研究的课题是基于模拟退火算法的基础上来分析生产调度现象。具体的研究内容如下所示：
第一章是绪论。简述选题的背景及其意义情况，综述对国内外在生产调度以及模拟退火算法领域的研究现状，陈述本论文的研究内容与相关的研究方法。
第二章概要地阐释了模拟退火算法理论。先阐述了VFSA相关理论，主要有模型扰动、接受概率与退火计划等3点。再解释VFSA的内在机理。最后是基于前2点的基础上提出了改进的模拟退火算法。
第三章分析生产调度的优化模型。首先分析的生产调度模型及其约束条件，并探讨其成本模型。再分析相关模型的求解方法。
第四章是对优化生产调度的过程实例展开描述。在提出了相关的问题以后，再条理化地开展相关因子的研究，包括编码、算法原理、交叉、变异与选择等，然后分析并行模拟退火遗传算法流程。最后从3个方面来具体地描述模拟退火算法，主要包括物理退火过程、Metropolis准则以及模拟退火算法。
第五章是优化生产调度的实现及其仿真分析。第一步，分析的是解空间的确定；第二步，分析的初始解的挑选；第三步，阐释新解的产生及其接受机理情况；第四步研究的是补充停止准则；最后探讨的是仿真结果。
第六章是全文的结论。
1.5研究方法
第一，文献综述法。即尽可能地搜集与本课题相关的国内外文献资料，包括发表在学术期刊杂志上的研究性论文、硕士博士的等学位研究论文等，在搜集这些论文资料时，搜集的渠道不一而足，主要上图书馆查阅纸质文件已经通过知网