匈牙利法的基本思想是修改效益矩阵的行或列,使得每一行或列中至少有一个为0的元素, FBMH1608HL601-T经过修正后,直至在不同行、不同列中至少有一个0元素,从而得到与这些0元素相对应的一个完全分配方案。当它用于效益矩阵时,这个完全分配方案就是一个最优分配,它使总的效益为最小。这种方法总是在有限步内收敛于一个最优解。该方法的理论基础是:在效益矩阵的任何行或列中,加上或减去一个常数后不会改变最优分配。其求解步骤如下。

   第一步:每行减去该行的最小数,每列减去该列的最小数,使矩阵每行每列均有0元素。

   第二步:寻找独立0元素。

   (1)从单个0元素的行(列)开始,给0加圈,记作◎,然后划去所在列(行)的其他0元素,记为⑦;重复进行,直到处理完所有列(行)的单个0元素。

   (2)若还存在没有画圈的0元素(同行或同列中的0元素多于1个),则从剩余的0元素最少的行(列)开始,选0元素画圈,然后划掉同行同列的其他0元素,反复进行,直到所有0元素均被圈出或划掉为止。若◎的数目昭=刀,贝刂该问题的最优解已经得到,否则转入第三步。

   第三步:设◎的数目阴(刀,找出最少覆盖所有0的直线。

   (1)对没有◎的行打√。

   (2)对已打√行中含⑦所在列打√。

   (3)对已打√列中含◎所在行打√。

   (4)重复(2)~(3),直至没有要打√的行和列为止。

   (5)对没有打√的行画横线,对打√的列画竖线得到最少覆盖所有0的直线数,则转第四步;转第二步。

第四步:设未被这些直线覆盖的元素中的最小值为α。对未画线的行减去α,画线的列加上α,转第二步。

   1976年,PhiIlips等lgl首次为机器人制造单元提出第一个混合整数规划模型,并构建迄今为止这一研究领域最为权威的基准研究案例。周支立等[lq则对存在可重入加工抓钩调度问题提出改进的混合整数规划模型。Ⅱu等[11]对同时含有重入和并行加工模块的机器人制造单元提出综合的混合整数规划方法模型,并应用商业软件ILOG CPLEX求解。以上文献研究的抓钩或机器人制造单元调度问题类似于单臂机械手集束型装备调度问题,本书在1.4节分析了这三类调度问题的差异性。Gcismar等凹证明具有双臂机械手和欧氏搬运时间下的调度问题是NP-hard问题,并给出问题的混合整数规划模型。该方法同样可以解决解的可调性和调度问题,但数学模型复杂,不适合实际的工程应用。