传统优化方法求解job-shop调度问题的特征分析及改进策略研究

《传统优化方法求解job-shop调度问题的特征分析及改进策略研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉理工大学硕士学位论文调度问题的改进策略及其求解特征。(2)罚函数法在求解约束问题的具体流程分析，以及结合了变量轮换法的罚函数法在Job．shop调度问题求解过程中的求解特征研究；(3)基于拓扑排序的算法在Job?shop调度问题中的求解特征；(4)满足基本约束的Job．shop调度系统软件的开发及实例研究分析。1．5论文的组织结构论文的第一章为绪论，主要介绍Job．shop调度问题的研究现状，提出本文的研究内容。第二章主要是对Job．shop调度问题模型进行分析，并阐述复合形法求解思想及其在Job—shop调度问题中的求解步骤。第三章主要是分析罚函数法解决约束问题的

2、基本思路，并结合变量轮换法对Job．Shop调度问题的求解进行研究。第四章主要是介绍图论及拓扑排序的基本理论，并提出基于拓扑排序的Job．shop调度问题求解算法。第五章主要介绍Job．shop调度系统的开发，及三种方法在求解Job．shop调度问题中的比较研究。第六章是对全文的总结与展望。／2始胨触ssP碱＼5Job-shop6I-绪论。陲一3罚函数法求解JSSP研究．．．．j调度总结7系统与展’开发＼＼、4基于拓扑排序算法求解JssP研究r／及实望例研究图1-1论文组织结构4武汉理工大学硕士学位论文第2章复合形法在Job．shop调度问题中的应用研究2．1复合形法的

3、基本思想复合形法是求解约束最优化问题的直接方法之--[371，它的基本思想是先在可行域内产生n．个可行解作为初始复合形的顶点，经过对复合形顶点的函数值进行比较，不断确定复合形中的坏点，并通过计算，以较好的新点代替原先的坏点，形成新的复合形，从而逐步使复合形顶点函数值逼近目标函数的最优解。2．2复合形法在一般约束问题中的应用2．2．1一般约束问题的表达约束问题的一般形式可以表示为rainf(X)(2-1)满足于，giCr)≤0G=1，2，⋯rn)(2-2)hj似)=0D=1，2⋯，)(2-3)其中，X表示约束问题的约束变量，通常约束变量都是由向量表示；式(2-2)表示约束

4、问题的不等式约束条件；式(2-3)表示约束问题的等式约束条件；式(2-1)表示约束问题的目标函数。以上的式子就可以反映包括m个不等式约束和，个等式约束，求目标函数极小化的约束问题。在约束问题中，凡是满足约束条件的向量X称为问题的可行解，全体可行解的集合称为可行域，使目标函数值达到最小的可行解称为最优解。．2．2．2复合形法的一般求解步骤在求解一般的只有不等式约束的最优化问题时，复合形法的主要求解步骤如下：1、初始化，即产生复合形的仇个顶点，如果优化问题的变量个数为刀，一般按式(2-4)取n．的值。，n+l≤刀l≤2n(2-4)初始顶点可以通过随机函数产生。首先，输入一个

5、可行的初始点Xo；然后，5武汉理工大学硕士学位论文产生其余的(码一1)个点，其中以+。点利用式(2—5)的方式产生。工l+l』=ai+rlI)i一口f)(2—5)式中，Xk+l,i是t+，的第i个分量，ai和包分别是而下限和上限，，7为0'---'1之间的随机数。如果五+，满足条件，继续产生下一个顶点；否则，求前k个点的形心五=三k∑t=1置‘2·6’将t+。沿t+。与以的连线向形心点t缩小一半，即五+l=t+o．5似¨-X。)(2-7)然后，再验证五+。是否满足约束条件。如果仍然不满足，再按上式计算，再验证五+，是否满足约束条件，重复计算，直到五+，满足约束条件为止。

6、2、计算复合形各顶点的函数值Z---f(x,)(f=1,2⋯，％)(2．8)3、求最坏点如和最好点‘，最坏点是使目标函数值最大的点，最好点是使目标函数值最小的解。厂∽""max{fI，正⋯^。>(2．9)厂似口)=rain侦，^⋯五．，(2-10)4、判断迭代的终止条件。给定迭代终止收敛精度g，以目标函数值的标准差作为判断的基准，当标准差小于s时，迭代完成。终止条件的判断式子为：b鼽7弘协⋯式中厂为刀。个点的平均目标函数值，即7：÷艺石(2-12)儿：f5、求去掉最坏点以外的点的形心tt：击艺置(2．13)111一li五二H6、求映射点X膏Xl=Xc+a哒c—xH、)(

7、2-14)其中，口k>o)是映射系数，一般取1．3。6武汉理工大学硕士学位论文7、验证x鼻是否是可行点，若不是可行点，令口=a／2，转步骤6。8、计算厂伍置)，如果厂似矗)