下面介绍本章参考文献[27]分支定界算法的案例,并且论述如何运用运筹学方法优化集束型装备的晶圆排序和机械手搬运作业排序,FBMH2012HM121-T以获取混流调度问题的最优调度方案。

   本节分支定界算法由三个嵌套的分支定界树组成,分别称为分支定界树A、树B和树C。分支定界树A负责隐枚举一个周期内所有可能的初始工件(晶圆)分布G、=(co,cl,・・・,瓴l,CⅣ)o由前所述,由于集束型装备采用循环生产模式且一个周期内每种类型的工件只

有一个进入和离开生产线,因此从鲕中可得知工件的加工顺序。例如,对于Ⅳ吒,R=5的此类调度问题,假设C:=(l,0,0,2,0,0,3,0,0),则由其仅可知其中三种工件的加工顺序为:工件1-工件3→工件2,而并不知道工件4和工件5相互之间的加工顺序;假设C:(1,0,0,2,0,5,3,0,4),则由其可知所有5个工件的加工顺序。综上分析可知:若从A树生成的初始工件分布(鲕)可得知所有工件的加工顺序,则直接激活分支定界树C;反之,则激活分支定界B树并且接着A树的枚举工作继续枚举剩余工件的加工顺序。当B树枚举完剩余工件的加工顺序后,再激活分支定界树C。在此,不难理解,A树和B树实质上都是在枚举工件的加工顺序,设计它们的目的是首先删除不可能的初始工件分布和确保所有工件的加工顺序己知。其次是在A树或B树枚举完所有工件的加工顺序之后,再由分支定界树C负责隐枚举保存下来的可能的初始工件分布和可能的所有工件的加工顺序所对应的机械手搬运作业顺序,这样做可以缩小搜索空间和节省搜索时间。