雙目標瓶頸指派問題的遺傳算法

黃沙日娜　趙國亮　朱捷

摘 要 給出一種雙目標瓶頸指派問題的新模型，本模型結(jié)合了決策者和工人兩方面的因素，特別之處在于考慮到了工人對工作的排名偏好. 進而，將雙目標瓶頸指派問題轉(zhuǎn)化為單目標規(guī)劃，并設計了解此問題的遺傳算法，算法的解均為雙目標瓶頸指派問題的Pareto最優(yōu)解.

關鍵詞 雙目標； 瓶頸指派問題； 遺傳算法； Pareto最優(yōu)解

中圖分類號 O221.6 文獻標識碼 A

1 引 言

經(jīng)典指派問題是一類特殊的組合優(yōu)化問題，是指將n項工作分配給n個工人去完成，且每個工人只能完成一項工作，每項工作只能由一個人來完成，不同的工人完成每一項工作的費用是不同的，從而求出最優(yōu)指派. 所謂的最優(yōu)是指使總體費用最大或者總體用時最小.

指派問題最早由Votaw和Orden提出^[1]， 1955年，Kuhn給出了解指派問題的匈牙利算法^[2]， 從此指派問題得到了真正的發(fā)展. 此后的幾十年，指派問題的解法日趨成熟，出現(xiàn)了隱枚舉法、分支定界法和割平面法等，但是用到最多的還是匈牙利法. 與此同時，還出現(xiàn)許多經(jīng)典指派問題的變形，如瓶頸指派問題^[3]、平衡指派問題^[4]、半指派問題、多準則指派問題、分數(shù)指派問題、二次指派問題^[5]、隨機指派問題^[6，7]、模糊指派問題^[8]以及帶負荷約束的指派問題^[9]等，有關這些問題的介紹可參閱綜述文章^[10]及其參考文獻.

指派問題在生產(chǎn)和服務系統(tǒng)中有著廣泛的應用. 例如在咨詢服務行業(yè)，決策者或者管理人員根據(jù)咨詢師以往的工作表現(xiàn)和顧客反饋，可以給出不同咨詢師完成某項工作的合適性，即費用. 經(jīng)典指派問題的目標是要使這項費用最大化. 本文將在此基礎上，同時考慮咨詢師（工人）對工作的排名偏好，建立雙目標瓶頸指派問題的模型，進而將此問題轉(zhuǎn)化為單目標規(guī)劃問題，并設計遺傳算法來求解.

同樣，模型（4）的最優(yōu)解也是問題（2）的Pareto最優(yōu)解. 問題（2）到模型（4）的轉(zhuǎn)化方式也是處理多目標優(yōu)化的常用方法.模型（3）與模型（4）相比其優(yōu)勢在于約束條件相較于問題（2）沒有增加，問題的規(guī)模沒有增大，利用我們給出的編碼、交叉和變異算子可以保證個體的可行性.

參考文獻

[1] DF VOTAW， A ORDEN. The personnel assignment problem[C]//Symposium on Linear Inequalities and Programming. Scoop 10， US Air Force， 1952： 155-163.

[2] H W KUHN. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly， 1955， 2（1/2）： 83-97.

[3] J GORSKI， K KLAMROTH， S RUZIKA. Generalized multiple objective bottleneck problems[J]. Operations Research Letters， 2012， 40（4）： 276-281.

[4] L LIU， H MU， Y SONG， et al. The equilibrium generalized assignment problem and genetic algorithm[J]. Applied Mathematics and Computation， 2012， 218（11）： 6526–6535.

[5] A A PESSOA， PM HAHN， M GUIGNARD， et al. Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization technique[J]. European Journal of Operational Research， 2010， 206（1）： 54-63.

[6] PA KROKHMAL， PM PARDALOS. Random assignment problems[J]. European Journal of Operational Research， 2009， 194（1）： 1-17.

[7] F LI， LD XU， C JIN， et al. Random assignment method based on genetic algorithms and its application in resource allocation[J]. Expert Systems with Applications， 2012， 39（15）： 12213-12219.

[8] PN TAPKAN， LZBAKIR， A BAYKASOGLU. Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking[J]. Expert Systems with Applications， 2013， 40（3）： 892-898.

[9] 林浩，林瀾. 有負荷約束的指派問題[J]. 經(jīng)濟數(shù)學，2013，30（1）： 17-21.

[10]D W PENTICO. Assignment problem： A golden anniversary survey[J]. European Journal of Operational Research， 2007， 176（2）： 774-793.

[11]葛悅. 模糊環(huán)境下若干網(wǎng)絡優(yōu)化問題的模型及其算法研究[D]. 哈爾濱：哈爾濱工業(yè)大學理學院數(shù)學系， 2012.

[12]D Z DU， P M PARDALOS. Minmax and Applications[M]. Netherland： Kluwer Academic Publishers， 1995.

[13]I H TOROSLU， Y ARSLANOGLU. Genetic algorithm for the personnel assignment problem with multiple objectives[J]. Information Sciences， 2007， 177（3）： 787–803.

[14]S Y LIN， S J HORNG， T W KAO， et al. Solving the bi-objective personnel assignment problem using particle swarm optimization[J]. Applied Soft Computing， 2012， 12（9）： 2840-2845.

[15]A ZINFLOU， C GAGNE， M GRAVEL. GISMOO： A new hybrid genetic/immune strategy for multiple-objective optimization[J]. Computers & Operations Research， 2012，39（9）： 1951-1968.endprint

摘 要 給出一種雙目標瓶頸指派問題的新模型，本模型結(jié)合了決策者和工人兩方面的因素，特別之處在于考慮到了工人對工作的排名偏好. 進而，將雙目標瓶頸指派問題轉(zhuǎn)化為單目標規(guī)劃，并設計了解此問題的遺傳算法，算法的解均為雙目標瓶頸指派問題的Pareto最優(yōu)解.

關鍵詞 雙目標； 瓶頸指派問題； 遺傳算法； Pareto最優(yōu)解

中圖分類號 O221.6 文獻標識碼 A

1 引 言

經(jīng)典指派問題是一類特殊的組合優(yōu)化問題，是指將n項工作分配給n個工人去完成，且每個工人只能完成一項工作，每項工作只能由一個人來完成，不同的工人完成每一項工作的費用是不同的，從而求出最優(yōu)指派. 所謂的最優(yōu)是指使總體費用最大或者總體用時最小.

指派問題最早由Votaw和Orden提出^[1]， 1955年，Kuhn給出了解指派問題的匈牙利算法^[2]， 從此指派問題得到了真正的發(fā)展. 此后的幾十年，指派問題的解法日趨成熟，出現(xiàn)了隱枚舉法、分支定界法和割平面法等，但是用到最多的還是匈牙利法. 與此同時，還出現(xiàn)許多經(jīng)典指派問題的變形，如瓶頸指派問題^[3]、平衡指派問題^[4]、半指派問題、多準則指派問題、分數(shù)指派問題、二次指派問題^[5]、隨機指派問題^[6，7]、模糊指派問題^[8]以及帶負荷約束的指派問題^[9]等，有關這些問題的介紹可參閱綜述文章^[10]及其參考文獻.

指派問題在生產(chǎn)和服務系統(tǒng)中有著廣泛的應用. 例如在咨詢服務行業(yè)，決策者或者管理人員根據(jù)咨詢師以往的工作表現(xiàn)和顧客反饋，可以給出不同咨詢師完成某項工作的合適性，即費用. 經(jīng)典指派問題的目標是要使這項費用最大化. 本文將在此基礎上，同時考慮咨詢師（工人）對工作的排名偏好，建立雙目標瓶頸指派問題的模型，進而將此問題轉(zhuǎn)化為單目標規(guī)劃問題，并設計遺傳算法來求解.

同樣，模型（4）的最優(yōu)解也是問題（2）的Pareto最優(yōu)解. 問題（2）到模型（4）的轉(zhuǎn)化方式也是處理多目標優(yōu)化的常用方法.模型（3）與模型（4）相比其優(yōu)勢在于約束條件相較于問題（2）沒有增加，問題的規(guī)模沒有增大，利用我們給出的編碼、交叉和變異算子可以保證個體的可行性.

參考文獻

[1] DF VOTAW， A ORDEN. The personnel assignment problem[C]//Symposium on Linear Inequalities and Programming. Scoop 10， US Air Force， 1952： 155-163.

[2] H W KUHN. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly， 1955， 2（1/2）： 83-97.

[3] J GORSKI， K KLAMROTH， S RUZIKA. Generalized multiple objective bottleneck problems[J]. Operations Research Letters， 2012， 40（4）： 276-281.

[4] L LIU， H MU， Y SONG， et al. The equilibrium generalized assignment problem and genetic algorithm[J]. Applied Mathematics and Computation， 2012， 218（11）： 6526–6535.

[5] A A PESSOA， PM HAHN， M GUIGNARD， et al. Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization technique[J]. European Journal of Operational Research， 2010， 206（1）： 54-63.

[6] PA KROKHMAL， PM PARDALOS. Random assignment problems[J]. European Journal of Operational Research， 2009， 194（1）： 1-17.

[7] F LI， LD XU， C JIN， et al. Random assignment method based on genetic algorithms and its application in resource allocation[J]. Expert Systems with Applications， 2012， 39（15）： 12213-12219.

[8] PN TAPKAN， LZBAKIR， A BAYKASOGLU. Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking[J]. Expert Systems with Applications， 2013， 40（3）： 892-898.

[9] 林浩，林瀾. 有負荷約束的指派問題[J]. 經(jīng)濟數(shù)學，2013，30（1）： 17-21.

[10]D W PENTICO. Assignment problem： A golden anniversary survey[J]. European Journal of Operational Research， 2007， 176（2）： 774-793.

[11]葛悅. 模糊環(huán)境下若干網(wǎng)絡優(yōu)化問題的模型及其算法研究[D]. 哈爾濱：哈爾濱工業(yè)大學理學院數(shù)學系， 2012.

[12]D Z DU， P M PARDALOS. Minmax and Applications[M]. Netherland： Kluwer Academic Publishers， 1995.

[13]I H TOROSLU， Y ARSLANOGLU. Genetic algorithm for the personnel assignment problem with multiple objectives[J]. Information Sciences， 2007， 177（3）： 787–803.

[14]S Y LIN， S J HORNG， T W KAO， et al. Solving the bi-objective personnel assignment problem using particle swarm optimization[J]. Applied Soft Computing， 2012， 12（9）： 2840-2845.

[15]A ZINFLOU， C GAGNE， M GRAVEL. GISMOO： A new hybrid genetic/immune strategy for multiple-objective optimization[J]. Computers & Operations Research， 2012，39（9）： 1951-1968.endprint

摘 要 給出一種雙目標瓶頸指派問題的新模型，本模型結(jié)合了決策者和工人兩方面的因素，特別之處在于考慮到了工人對工作的排名偏好. 進而，將雙目標瓶頸指派問題轉(zhuǎn)化為單目標規(guī)劃，并設計了解此問題的遺傳算法，算法的解均為雙目標瓶頸指派問題的Pareto最優(yōu)解.

關鍵詞 雙目標； 瓶頸指派問題； 遺傳算法； Pareto最優(yōu)解

中圖分類號 O221.6 文獻標識碼 A

1 引 言

經(jīng)典指派問題是一類特殊的組合優(yōu)化問題，是指將n項工作分配給n個工人去完成，且每個工人只能完成一項工作，每項工作只能由一個人來完成，不同的工人完成每一項工作的費用是不同的，從而求出最優(yōu)指派. 所謂的最優(yōu)是指使總體費用最大或者總體用時最小.

指派問題最早由Votaw和Orden提出^[1]， 1955年，Kuhn給出了解指派問題的匈牙利算法^[2]， 從此指派問題得到了真正的發(fā)展. 此后的幾十年，指派問題的解法日趨成熟，出現(xiàn)了隱枚舉法、分支定界法和割平面法等，但是用到最多的還是匈牙利法. 與此同時，還出現(xiàn)許多經(jīng)典指派問題的變形，如瓶頸指派問題^[3]、平衡指派問題^[4]、半指派問題、多準則指派問題、分數(shù)指派問題、二次指派問題^[5]、隨機指派問題^[6，7]、模糊指派問題^[8]以及帶負荷約束的指派問題^[9]等，有關這些問題的介紹可參閱綜述文章^[10]及其參考文獻.

指派問題在生產(chǎn)和服務系統(tǒng)中有著廣泛的應用. 例如在咨詢服務行業(yè)，決策者或者管理人員根據(jù)咨詢師以往的工作表現(xiàn)和顧客反饋，可以給出不同咨詢師完成某項工作的合適性，即費用. 經(jīng)典指派問題的目標是要使這項費用最大化. 本文將在此基礎上，同時考慮咨詢師（工人）對工作的排名偏好，建立雙目標瓶頸指派問題的模型，進而將此問題轉(zhuǎn)化為單目標規(guī)劃問題，并設計遺傳算法來求解.

同樣，模型（4）的最優(yōu)解也是問題（2）的Pareto最優(yōu)解. 問題（2）到模型（4）的轉(zhuǎn)化方式也是處理多目標優(yōu)化的常用方法.模型（3）與模型（4）相比其優(yōu)勢在于約束條件相較于問題（2）沒有增加，問題的規(guī)模沒有增大，利用我們給出的編碼、交叉和變異算子可以保證個體的可行性.

參考文獻

[1] DF VOTAW， A ORDEN. The personnel assignment problem[C]//Symposium on Linear Inequalities and Programming. Scoop 10， US Air Force， 1952： 155-163.

[2] H W KUHN. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly， 1955， 2（1/2）： 83-97.

[3] J GORSKI， K KLAMROTH， S RUZIKA. Generalized multiple objective bottleneck problems[J]. Operations Research Letters， 2012， 40（4）： 276-281.

[4] L LIU， H MU， Y SONG， et al. The equilibrium generalized assignment problem and genetic algorithm[J]. Applied Mathematics and Computation， 2012， 218（11）： 6526–6535.

[5] A A PESSOA， PM HAHN， M GUIGNARD， et al. Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization technique[J]. European Journal of Operational Research， 2010， 206（1）： 54-63.

[6] PA KROKHMAL， PM PARDALOS. Random assignment problems[J]. European Journal of Operational Research， 2009， 194（1）： 1-17.

[7] F LI， LD XU， C JIN， et al. Random assignment method based on genetic algorithms and its application in resource allocation[J]. Expert Systems with Applications， 2012， 39（15）： 12213-12219.

[8] PN TAPKAN， LZBAKIR， A BAYKASOGLU. Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking[J]. Expert Systems with Applications， 2013， 40（3）： 892-898.

[9] 林浩，林瀾. 有負荷約束的指派問題[J]. 經(jīng)濟數(shù)學，2013，30（1）： 17-21.

[10]D W PENTICO. Assignment problem： A golden anniversary survey[J]. European Journal of Operational Research， 2007， 176（2）： 774-793.

[11]葛悅. 模糊環(huán)境下若干網(wǎng)絡優(yōu)化問題的模型及其算法研究[D]. 哈爾濱：哈爾濱工業(yè)大學理學院數(shù)學系， 2012.

[12]D Z DU， P M PARDALOS. Minmax and Applications[M]. Netherland： Kluwer Academic Publishers， 1995.

[13]I H TOROSLU， Y ARSLANOGLU. Genetic algorithm for the personnel assignment problem with multiple objectives[J]. Information Sciences， 2007， 177（3）： 787–803.

[14]S Y LIN， S J HORNG， T W KAO， et al. Solving the bi-objective personnel assignment problem using particle swarm optimization[J]. Applied Soft Computing， 2012， 12（9）： 2840-2845.

[15]A ZINFLOU， C GAGNE， M GRAVEL. GISMOO： A new hybrid genetic/immune strategy for multiple-objective optimization[J]. Computers & Operations Research， 2012，39（9）： 1951-1968.endprint