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

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

   第二步:尋找獨(dú)立0元素。

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

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

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

   (1)對(duì)沒(méi)有◎的行打√。

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

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

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

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

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

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