雙目標瓶頸指派問題的遺傳算法
2014-08-12 19:36:28黃沙日娜趙國亮朱捷
經濟數學 2014年2期
黃沙日娜 趙國亮 朱捷
摘 要 給出一種雙目標瓶頸指派問題的新模型，本模型結合了決策者和工人兩方面的因素，特別之處在于考慮到了工人對工作的排名偏好. 進而，將雙目標瓶頸指派問題轉化為單目標規劃，并設計了解此問題的遺傳算法，算法的解均為雙目標瓶頸指派問題的Pareto最優解.
關鍵詞 雙目標； 瓶頸指派問題； 遺傳算法； Pareto最優解
中圖分類號 O221.6 文獻標識碼 A
1 引 言
經典指派問題是一類特殊的組合優化問題，是指將n項工作分配給n個工人去完成，且每個工人只能完成一項工作，每項工作只能由一個人來完成，不同的工人完成每一項工作的費用是不同的，從而求出最優指派. 所謂的最優是指使總體費用最大或者總體用時最小.
指派問題最早由Votaw和Orden提出[1]， 1955年，Kuhn給出了解指派問題的匈牙利算法[2]， 從此指派問題得到了真正的發展. 此后的幾十年，指派問題的解法日趨成熟，出現了隱枚舉法、分支定界法和割平面法等，但是用到最多的還是匈牙利法. 與此同時，還出現許多經典指派問題的變形，如瓶頸指派問題[3]、平衡指派問題[4]、半指派問題、多準則指派問題、分數指派問題、二次指派問題[5]、隨機指派問題[6，7]、模糊指派問題[8]以及帶負荷約束的指派問題[9]等，有關這些問題的介紹可參閱綜述文章[10]及其參考文獻.
指派問題在生產和服務系統中有著廣泛的應用. 例如在咨詢服務行業，決策者或者管理人員根據咨詢師以往的工作表現和顧客反饋，可以給出不同咨詢師完成某項工作的合適性，即費用. 經典指派問題的目標是要使這項費用最大化. 本文將在此基礎上，同時考慮咨詢師（工人）對工作的排名偏好，建立雙目標瓶頸指派問題的模型，進而將此問題轉化為單目標規劃問題，并設計遺傳算法來求解.
同樣，模型（4）的最優解也是問題（2）的Pareto最優解. 問題（2）到模型（4）的轉化方式也是處理多目標優化的常用方法.模型（3）與模型（4）相比其優勢在于約束條件相較于問題（2）沒有增加，問題的規模沒有增大，利用我們給出的編碼、交叉和變異算子可以保證個體的可行性.
參考文獻
[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]. 經濟數學，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]葛悅. 模糊環境下若干網絡優化問題的模型及其算法研究[D]. 哈爾濱：哈爾濱工業大學理學院數學系， 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
摘 要 給出一種雙目標瓶頸指派問題的新模型，本模型結合了決策者和工人兩方面的因素，特別之處在于考慮到了工人對工作的排名偏好. 進而，將雙目標瓶頸指派問題轉化為單目標規劃，并設計了解此問題的遺傳算法，算法的解均為雙目標瓶頸指派問題的Pareto最優解.
關鍵詞 雙目標； 瓶頸指派問題； 遺傳算法； Pareto最優解
中圖分類號 O221.6 文獻標識碼 A
1 引 言
經典指派問題是一類特殊的組合優化問題，是指將n項工作分配給n個工人去完成，且每個工人只能完成一項工作，每項工作只能由一個人來完成，不同的工人完成每一項工作的費用是不同的，從而求出最優指派. 所謂的最優是指使總體費用最大或者總體用時最小.
指派問題最早由Votaw和Orden提出[1]， 1955年，Kuhn給出了解指派問題的匈牙利算法[2]， 從此指派問題得到了真正的發展. 此后的幾十年，指派問題的解法日趨成熟，出現了隱枚舉法、分支定界法和割平面法等，但是用到最多的還是匈牙利法. 與此同時，還出現許多經典指派問題的變形，如瓶頸指派問題[3]、平衡指派問題[4]、半指派問題、多準則指派問題、分數指派問題、二次指派問題[5]、隨機指派問題[6，7]、模糊指派問題[8]以及帶負荷約束的指派問題[9]等，有關這些問題的介紹可參閱綜述文章[10]及其參考文獻.
指派問題在生產和服務系統中有著廣泛的應用. 例如在咨詢服務行業，決策者或者管理人員根據咨詢師以往的工作表現和顧客反饋，可以給出不同咨詢師完成某項工作的合適性，即費用. 經典指派問題的目標是要使這項費用最大化. 本文將在此基礎上，同時考慮咨詢師（工人）對工作的排名偏好，建立雙目標瓶頸指派問題的模型，進而將此問題轉化為單目標規劃問題，并設計遺傳算法來求解.
同樣，模型（4）的最優解也是問題（2）的Pareto最優解. 問題（2）到模型（4）的轉化方式也是處理多目標優化的常用方法.模型（3）與模型（4）相比其優勢在于約束條件相較于問題（2）沒有增加，問題的規模沒有增大，利用我們給出的編碼、交叉和變異算子可以保證個體的可行性.
參考文獻
[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]. 經濟數學，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]葛悅. 模糊環境下若干網絡優化問題的模型及其算法研究[D]. 哈爾濱：哈爾濱工業大學理學院數學系， 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
摘 要 給出一種雙目標瓶頸指派問題的新模型，本模型結合了決策者和工人兩方面的因素，特別之處在于考慮到了工人對工作的排名偏好. 進而，將雙目標瓶頸指派問題轉化為單目標規劃，并設計了解此問題的遺傳算法，算法的解均為雙目標瓶頸指派問題的Pareto最優解.
關鍵詞 雙目標； 瓶頸指派問題； 遺傳算法； Pareto最優解
中圖分類號 O221.6 文獻標識碼 A
1 引 言
經典指派問題是一類特殊的組合優化問題，是指將n項工作分配給n個工人去完成，且每個工人只能完成一項工作，每項工作只能由一個人來完成，不同的工人完成每一項工作的費用是不同的，從而求出最優指派. 所謂的最優是指使總體費用最大或者總體用時最小.
指派問題最早由Votaw和Orden提出[1]， 1955年，Kuhn給出了解指派問題的匈牙利算法[2]， 從此指派問題得到了真正的發展. 此后的幾十年，指派問題的解法日趨成熟，出現了隱枚舉法、分支定界法和割平面法等，但是用到最多的還是匈牙利法. 與此同時，還出現許多經典指派問題的變形，如瓶頸指派問題[3]、平衡指派問題[4]、半指派問題、多準則指派問題、分數指派問題、二次指派問題[5]、隨機指派問題[6，7]、模糊指派問題[8]以及帶負荷約束的指派問題[9]等，有關這些問題的介紹可參閱綜述文章[10]及其參考文獻.
指派問題在生產和服務系統中有著廣泛的應用. 例如在咨詢服務行業，決策者或者管理人員根據咨詢師以往的工作表現和顧客反饋，可以給出不同咨詢師完成某項工作的合適性，即費用. 經典指派問題的目標是要使這項費用最大化. 本文將在此基礎上，同時考慮咨詢師（工人）對工作的排名偏好，建立雙目標瓶頸指派問題的模型，進而將此問題轉化為單目標規劃問題，并設計遺傳算法來求解.
同樣，模型（4）的最優解也是問題（2）的Pareto最優解. 問題（2）到模型（4）的轉化方式也是處理多目標優化的常用方法.模型（3）與模型（4）相比其優勢在于約束條件相較于問題（2）沒有增加，問題的規模沒有增大，利用我們給出的編碼、交叉和變異算子可以保證個體的可行性.
參考文獻
[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]. 經濟數學，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]葛悅. 模糊環境下若干網絡優化問題的模型及其算法研究[D]. 哈爾濱：哈爾濱工業大學理學院數學系， 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
