考量專長限制下之人力派遣

Abstract

在本研究中，我們將會探討考量專長限制之人力派遣。我們給定一個人力資源集合U = {1,2,...,n}，代表我們可以分配的資源。以及一個任務集合T = {T1,T2,...,Tm}，表示有各種不同專長需求的任務子集合。我們希望在每一群至少完成k 個任務的前提下，將資源分成越多群越好。為了使結果更趨近於現實應用，對於所有任務子集合我們會給定一個相同密度限制，使每個子集合的人數不超過給定之密度。我們提出一個基於線性規劃模型的隨機演算法，以期在有限的時間內，求得一個不錯的近似解。同時也設計了啟發式演算法以及螞蟻演算法。我們透過實驗來評估每一個所提出演算法的效能。

關鍵字：集合覆蓋; 集合分組; 線性規劃; 整數規劃; 隨機處理演算法; 螞蟻演算法

In this thesis, we consider the allocation of human resource subject to skill constraints. We are given a staff set U = {1,2,...,n} that indicates the human resource available for the considered project, and a task set T = {T1,T2,...,Tm} that contains the tasks of the project. Each task demands a subset of skills or expertises. Under the premise that each time period should have at least k tasks completed, we want to partition the available human resource into as many time periods as possible. In order to reflect the practical significance of the problem, we give a limit on each subset Tj ∈ T to ensure that for each subset the amount of resources will not exceed the given density. We develop a randomized algorithm, based on a linear programming formulation, to produce approximate solutions. A heuristic algorithm and an ant colony optimization (ACO) algorithm are also designed. We conduct a computational study to appraise the performances of the proposed algorithms.

Keywords: Bin Covering; Set Covering; Set Partitioning; Linear Programming; Integer Programming; Randomized Algorithm; Ant Colony Optimization.