參與約束的團(tuán)隊形成問題的研究與實(shí)現(xiàn).pdf

1、團(tuán)隊形成問題，旨在為一個或者多個任務(wù)找到一個指定的團(tuán)隊來完成，這項研究已經(jīng)成為當(dāng)前的一個熱點(diǎn)研究領(lǐng)域。該問題的主要研究目的是如何為已知項目找到一組合適的團(tuán)隊成員，使得項目的實(shí)施能夠更加高效且項目負(fù)責(zé)人能夠更均衡的進(jìn)行任務(wù)分配。近年對團(tuán)隊形成的研究主要分為以下幾個方面：怎樣使團(tuán)隊成員之間通信開銷最小，怎樣使團(tuán)隊成本最低，怎樣使得項目收益最大等。求解該類型的問題對于各類眾包服務(wù)平臺，在線招聘和其他各個領(lǐng)域都具有非常廣泛的實(shí)踐意義。目前，針對

2、該問題的研究存在著明顯的缺點(diǎn)，專家在參與項目任務(wù)的分配是均被假設(shè)能夠參與所有的項目，然而，每個專家的專業(yè)程度和工作時間是完全不同的，以前的研究往往將專家所能承受的工作量忽略，這會使得各個專家之間的任務(wù)分配不均勻，導(dǎo)致團(tuán)隊合作不順利以及項目完成受阻。
　　在這篇論文中，我們針對以往問題的不足和缺點(diǎn)，提出了一個新的團(tuán)隊形成問題，將專家的工作時間和能承受的最大工作量考慮在內(nèi)。我們首先對提出的新問題進(jìn)行形式化的定義，給定一個項目集P和一個

3、專家集X，每個項目有需要被完成的技能且每個專家擁有自己的專業(yè)技能，薪資成本和參與約束（規(guī)定每個專家能夠同時參加的項目個數(shù)），問題的最優(yōu)化目標(biāo)是尋找到一個帶參與約束的團(tuán)隊使其不僅能夠滿足項目所有技能的要求而且成本最低。我們把這個問題叫做：參與約束的團(tuán)隊形成問題。據(jù)研究表明，本文是第一個提出類似問題的論文。在此基礎(chǔ)上，本文針對參與約束的團(tuán)隊形成問題提出了一個特例問題，該特例致力于研究當(dāng)專家的參與約束大于項目個數(shù)的情況。我們證明提出的兩個問題

4、均為NP-hard問題且難近似。我們針對特例問題提出了一個精確解算法，該算法依據(jù)提出的剪枝定理設(shè)計了兩個剪枝規(guī)則。同時我們針對參與約束的團(tuán)隊形成問題提出了三個近似算法，且每個算法均有其自身的優(yōu)勢。
　　在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗結(jié)果表明：本文對精確解算法提出的兩個剪枝規(guī)則，大大降低了算法過程中的迭代次數(shù)，提高算法效率，相對暴力搜索算法有明顯的優(yōu)勢，同時，三個近似算法在尋找出符合要求的團(tuán)隊的同時能夠滿足尋找不同側(cè)重點(diǎn)團(tuán)隊的需求