job+shop+scheduling问题的算法研究

《job+shop+scheduling问题的算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、工程硕士学位论文第l章序论计算能力，求解优化调度，以克服调度的NP难问题；2)利用其学习能力，从优化轨迹中提取调度知识；3)用NN来描述调度约束或调度策略，以实现对生产过程的可行或次优调度。Hopfield神经网络模型的提出为求解各种有约束优化问题开辟了一条新途径，有学者运用该网络来处理生产车间调度问题，但这些方法计算效率较低，并且常产生不可行解，因此不能运用于解决实际调度问题。禁忌搜索(TabuSearch)是一个为优化组合问题寻求近似最优解的启发式算法。它由Glover提出并形式化“2““““”，是求解优化组合问题的广泛得到应用的方法““”1。禁忌搜索是在20世纪70年代后期被最先运用

2、在非线性覆盖的优化组合问题中，从那个时候开始，禁忌搜索被用于各种不同的问题中，如计算机调频问题、空间布局问题。最新的研究包括货郎问题、图着色问题、电路板布局问题，这些问题用禁忌搜索可以得到问题较好的解“””。在用禁忌搜索来求解JobShopScheduling问题的时候，必须要给算法提出一个初始调度。然后通过交换初始调度中工序的位置来产生这个调度的领域，领域中的每个元素都是一个合法的调度。计算出领域中每个调度的时间跨度，选取时间跨度最小的那个调度作为下一次迭代的初始解，并从当前解跳到这个时间跨度最小的解。这种从一个解跳到另一个解称为一个“动作”。为了避免在搜索的过程中形成环路，这个“动作”

3、被规定为“禁忌动作”，并且在后面规定的次数内不能重复这个动作。在进行了算法所规定迭代次数后，禁忌搜索结束。禁忌搜索是一个效率较好的启发式算法，它能找到调度问题不少算例的最优解。但禁忌搜索要面对很多的问题，如初始解问题、领域结构问题、搜索策略问题等等。只有很好地解决了这些问题，禁忌搜索算法才能表现得更好。模拟退火SA(simulatedannealing)是基于MenteCarlo迭代求解的一种全局概率型搜索算法，是一种串行优化算法，其收敛性要求初温应足够高，使解空间各状态能以几乎相同的概率出现。VanLaarhooven等啪1提出对于JobShopScheduling问题，邻域函数的重要标

4、志是相邻关键操作工序处理顺序的改变，且必须服从在同一机器上处理的工序条件。Kolonko明标准的JobShopScheduling问题的邻域具有非对称性，且由于sA的弱收敛性，提出了在sA基础上结合GA的混合启发式。“。模拟退火法模仿晶体结晶的冷却过程，在较高温度Ts下，系统状态为s，能量(即目标函数)为E，选择的一个邻域s’，工程硕士学位论文第1章序论如果，E(S’)

5、法有加温退火法、有记忆的模拟退火法等。由于模拟退火法能以一定的概率接受差的能量，因而有可能跳出局部极小，但它的收敛速度较慢，很难用于实时动态调度环境。遗传算法GA(geneticalgorithms)的基本思想来源于分子遗传学和生物进化论，是Holland基于自然遗传进化的绝对模型提出的并行搜索机制。1，其基本原理是，产生若干代表问题候选解的成员，并组成一个群体，按照某一评价函数或算法对群体中的每个成员进行评估，评估结果代表解的良好性。按照适者生存、优胜劣汰的原则，群体中的某一成员愈适合，则愈有可能产生后代。利用遗传操作符对群体中的成员进行遗传操作，产生新的后代，这种后代能继承双亲的特征。

6、对后代进行评估，并将其放入群体，代替上一代中较弱的成员(非良好解)。此过程反复执行，这构成一代一代的群体。随着遗传过程的不断进行，越来越良好的解就可以得到。遗传算法(GA)的5个要素是编码、适应值函数、初始种群、遗传算子和参数设置“”。由于对JSSP问题要考虑工序的前后约束和非堵塞约束，使得染色体的编码表示非常重要。如果编码不当，会在遗传算子操作时产生不可行解，失去了交叉或变异算子的有效性。Cheng等把编码表示分为两类共9种，分别是直接的方法(基于工序、基于工件、基于工件对关系、基于完成时间和基于随机键表示法)和间接的方法(基于优先规则、基于优先表、基于非连接图和基于机器的表示法)。Da

7、vis∞1首先基于优先表的间接编码表示求解JobShopScheduling问题∞1，Falkenauer等则利用把工序编码为字符串的方法。Tamaki嘶1基于非连接图的间接编码，其染色体用非连接边顺序表的二进制串表示哺1。Bean咖采用随机键表示法，每个基因由两部分组成：整数部分表示机器的分配，分数部分以非减顺序排列的(0，1)之间的随机数来确定每个机器上的工序。曹承煜等提出结合拉氏松弛法的遗传算法，能够克服震荡并减小