匈牙利法的基本思想是修改效益矩陣的行或列,使得每一行或列中至少有一個為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問題,并給出問題的混合整數規劃模型。該方法同樣可以解決解的可調性和調度問題,但數學模型復雜,不適合實際的工程應用。