基于搜索空间概率模型的启发算法

《基于搜索空间概率模型的启发算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于搜索空间概率模型的启发算法HeuristicAlgorithmBasedontheProbabilisticModelofSearchSpace西北工业大学机电工程学院杨宏安孙树栋西安理工大学王荪馨【摘要】针对一类典型的约束满足问题——J0b题领域的变量和各变量的值域，通过描述各变量之间shop调度，提出了搜索空间的概率模型，并以模型中的的约束，采用搜索算法来求得满足全局所有约束的一工序开工概率、工序对机床的独立需求概率和机床累个或多个可行解。计需求3个分析要素，构造了新的启发算法。仿真结果针对Jobshop调度这类典型的CSP，文献

2、『2]构建了表明该启发算法在较小的计算时间代价下，获得了基于CSP的Jobshop调度模型，并提出了求解该模型的FT06标准调度问题的最优解。CSP调度算法。该算法的求解思路是：在各搜索状态关键词：Jobshop调度约束满足问题搜索空下，利用变量排序启发对未调度工序集进行排序，并输间概率模型变量排序启发值排序启发出某一工序变量，采用值排序启发在该工序的开始时【ABSTRACT】Accordingtoakindoftypical间窗(即工序变量的值域)进行排序，并输出工序的某constraintsatisfactionproblem-Job

3、shopscheduling，the一开工时间；然后检测该工序赋值和调度中间结果的probabilisticmodelofthesearchspaceispresented．Ba—约束满足性，如果通过约束检测，则采用约束传播I3J方sedonthreeanalyticalflact0rs——theoperationstartpro—法对当前搜索空间进行修剪和过滤，算法接着进入下bability，individualdemandprobabilityofoperationfor一搜索状态；如果没有通过约束检测，即进行回溯处machinean

4、dmachineaggregatedemandinthemodel，a理，取消一个或几个更早工序的取值，重新为该工序安newheuristicalgorithmisbuilt．Thesimulationresult排一个开始时间。showsthatthisnewalgorithmobtainstheoptimalresult在CSP调度算法求解中，变量排序启发在搜索过of~3'06benchmarkschedulingproblematthesmaller程中控制各工序变量的优先次序，值排序启发控制工timecost．序开始时间窗的合理取

5、值，这样，整个搜索过程处于受Keywords：JobshopschedulingConstraintsa—控状态，从而可以避免盲目搜索，减少回溯发生次数，tisfactionproblemSearchspaceProbabilisticmo—降低后续搜索的复杂度和提高算法的搜索效率。delVariableorderingheuristicsValueordering文献[2]仅提出了CSP调度算法，没有对其中的变heuristics量和值排序启发进行深入研究，本文正是在文献『21的研究基础上，根据变量和值排序启发策略，建立了搜索Jobsh

6、op调度是一类复杂且极具代表性的生产调空间的概率分析模型，并在该模型的统一框架下，提出度问题。它可以描述为在m台机床(RES=fRR，⋯，了一种融合变量和值排序启发的新启发算法。R))上安排几个零件(．，=f，，⋯)的加工任务的过变量和值排序启发策略程。其中，每个零件(1≤2≤凡)包含一组工序{00，⋯，0}，已知各工序的加工时间，调度任务就是在机床(1)变量排序遵循困难工序变量优先的启发策略。上安排各工序的加工开始时间，并在满足工艺顺序、机即：通过首先选择困难工序变量，系统就容易移动到发床加工能力和零件交货期等约束的前提下．尽可能地生冲

7、突的状态，从而使约束冲突出现在搜索过程的初使目标函数达到最优或次优。期。通过在搜索进程的初期满足困难变量，就可以避免约束满足问题fConstraintSatisfactionProblem．搜索算法浪费在无效局部解的时间，从而减少回溯发CSP)是由一个变量集合、每个变量的值域和一个限制生次数，提高算法的搜索效率。变量取值的约束集合组成【1J。CSP的求解方法是定义问(2)值排序遵循相容性好的赋值优先启发策略。相国家863高技术研究发展计划(2003AA41110)、航空基金容性描述了工序变量的开工时间取值满足所有约束的(0lH53061)

8、资助项目。可能性的大小。相容性好的取值在与其他工序变量竞82航空镧造技术·2006年第6期争同一资源时具有生存概率大的特点。通过选择相容床的需求或占用情况。性好的取值，可以使变量的剩余开工时间