匈牙利法的基本思想是修改效益矩陣的行或列,使得每一行或列中至少有一個為0的元素, FBMH1608HL601-T經(jīng)過修正后,直至在不同行、不同列中至少有一個0元素,從而得到與這些0元素相對應的一個完全分配方案。當它用于效益矩陣時,這個完全分配方案就是一個最優(yōu)分配,它使總的效益為最小。這種方法總是在有限步內(nèi)收斂于一個最優(yōu)解。該方法的理論基礎(chǔ)是:在效益矩陣的任何行或列中,加上或減去一個常數(shù)后不會改變最優(yōu)分配。其求解步驟如下。

   第一步:每行減去該行的最小數(shù),每列減去該列的最小數(shù),使矩陣每行每列均有0元素。

   第二步:尋找獨立0元素。

   (1)從單個0元素的行(列)開始,給0加圈,記作◎,然后劃去所在列(行)的其他0元素,記為⑦;重復進行,直到處理完所有列(行)的單個0元素。

   (2)若還存在沒有畫圈的0元素(同行或同列中的0元素多于1個),則從剩余的0元素最少的行(列)開始,選0元素畫圈,然后劃掉同行同列的其他0元素,反復進行,直到所有0元素均被圈出或劃掉為止。若◎的數(shù)目昭=刀,貝刂該問題的最優(yōu)解已經(jīng)得到,否則轉(zhuǎn)入第三步。

   第三步:設◎的數(shù)目陰(刀,找出最少覆蓋所有0的直線。

   (1)對沒有◎的行打√。

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

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

   (4)重復(2)~(3),直至沒有要打√的行和列為止。

   (5)對沒有打√的行畫橫線,對打√的列畫豎線得到最少覆蓋所有0的直線數(shù),則轉(zhuǎn)第四步;轉(zhuǎn)第二步。

第四步:設未被這些直線覆蓋的元素中的最小值為α。對未畫線的行減去α,畫線的列加上α,轉(zhuǎn)第二步。

   1976年,PhiIlips等lgl首次為機器人制造單元提出第一個混合整數(shù)規(guī)劃模型,并構(gòu)建迄今為止這一研究領(lǐng)域最為權(quán)威的基準研究案例。周支立等[lq則對存在可重入加工抓鉤調(diào)度問題提出改進的混合整數(shù)規(guī)劃模型。Ⅱu等[11]對同時含有重入和并行加工模塊的機器人制造單元提出綜合的混合整數(shù)規(guī)劃方法模型,并應用商業(yè)軟件ILOG CPLEX求解。以上文獻研究的抓鉤或機器人制造單元調(diào)度問題類似于單臂機械手集束型裝備調(diào)度問題,本書在1.4節(jié)分析了這三類調(diào)度問題的差異性。Gcismar等凹證明具有雙臂機械手和歐氏搬運時間下的調(diào)度問題是NP-hard問題,并給出問題的混合整數(shù)規(guī)劃模型。該方法同樣可以解決解的可調(diào)性和調(diào)度問題,但數(shù)學模型復雜,不適合實際的工程應用。