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

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

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

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

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