适合的问题:约束条件中至少有一个是“≥”,相应的右边常数为非负,目标函FBMH1608HL300-T数系数全部为非负。例如: 求解步骤如下。

   第一步:确定原问题的初始基B,使所有检验数非正,即对偶问题有可行解,建立初始单纯形表。

   第二步:检查基变量的取值,若X:=BˉlD≥0,则已得最优解,计算停止,否则求min(fB刽D)氵B13)氵(0l=fB1ω厶,确定单纯形表第￡行对应的基变量为旋出变量。

   第三步:若所有则原问题无可行解,计算停止,否则,计算,确定对应的基变量为旋入变量。

   第四步:以气Κ为主元做(乙,Κ)旋转变换,得新的单纯形表,转第二步。可以证明,按上述方法进行迭代,所得解是对偶可行解。

   绝大多数集束型装备调度问题为NP-hard问题,本章参考文献[1,2]证明具有滞留时间约束的集束型装备调度问题为强NP-hard问题,即可行解个数随问题规模呈指数增长。另外,Brauncr等D]证明具有任意物理配置(单臂、双臂与并行模块等)的无限等待集束型装备调度问题为强NP-hard问题。本章参考文献卩,5]通过线性规划模型来确定双臂集束型装备调度问题的可调度性条件。该方法从可行性研究来说具有重要意义,但方法的模型复杂,线性规划求解也不是多项式算法,同样不适合于实时调度。本章参考文献首先采用扩展事件图方法对问题进行建模,然后通过识别模型中的所有回路来建立线性规划模型以判断问题的可调度性。如果系统可调度,则可求得最优调度方案。这个方法的问题在于:为建立线性规划模型,必须识别19个基本回路和更多的非基本回路。理论上这种网络中回路的数量与网络规模呈指数规律增长。同时,线性规划模型很难求解,计算复杂度非常高。本章参考文献[8]建立包括双臂机械手能力约束和加工模块时序约束关系的线性规划模型。在此模型基础上,分析机械手和加工模块周期性加工和搬运晶圆过程,从理论上证

明集束型装备可调度性的充要条件,并提出三种控制策略使不可调度方案变成可调度方案。因其可调度性条件是解析不等式,因此与本章参考文献卩~刀相比更高效。