考量公平性之有限產能無關連性機台工作分配

Abstract

本研究探討一種考量公平性、機台相依效益與有限產能之工作分配問題。在欲求解的問題中，每個工作有完成所需消耗的產能以及完成工作獲得的效益，且將同一個工作分配給不同的機台會獲得不同的效益。在工作不可分割與產能有限的前提下，目標為最大化所有機台中的最小累積效益。根據機台間性質（相同、均勻分布、無關聯）及工作量與工作效益間是否存在關聯性，研究問題可分為六種組合，本研究專注於其中兩種，分別是在無關聯機台下考量工作量與工作效益間存在關聯性（FARF）以及在相同機台下考量工作量與工作效益間不存在關聯性（FAPN）。在證明問題為 NP-hard 後，本研究提出一個修改自最長處理時間優先演算法的近似演算法。此演算法在 FARF 中，可以保證在工作量與效益呈線性關係的情況下，最差情況的目標式值至少為最佳解的 1/2，並推導在工作量與效益呈凸函數和凹函數關係的情況下，近似演算法與最佳解之間的差異。在 FAPN 中我們透過加入工作量與工作效益之間的偏移設定放寬工作量與工作效益之間的無關聯性，發現不論在工作量與效益呈線性、凸函數與凹函數關係的情況下，當偏移量不到原本的 100% 時，此演算法就能保證最差情況的目標式值與最佳解之間的關係。透過數值實驗，本研究闡明演算法在兩種問題設定與工作量與工作效益的三種不同函數關係下的平均性能；當工作具規模經濟性質時，此演算法表現出良好的性能，但在工作呈現邊際效益遞減特性時表現較不佳。

We consider a fairness problem of allocating jobs to multiple machines under capacity limitations. Each job has a specific workload and benefits when completed on a machine. The workload and benefits may different depending on which machine the job is assigned to. All machines have the same capacity limitation. Given the machine capacity constraint and the constraint against splitting jobs, we aim to maximize the minimum cumulative benefit among all machines. Based on the different types of multiple machines (identical, uniform, unrelated) and whether there exists a relationship between job workload and job benefit, there are six combinations of problems. In this study, we focus on two problems: one involves unrelated machines with a functional relationship (FARF), and the other involves identical machines with no functional relationship (FAPN). After demonstrating the problem is NP-hard, we propose a heuristic algorithm modified from the classic Longest Processing Time (LPT) rule, called the Capacitated Highest Benefit First (CHBF), to solve it in polynomial time.

Next, we apply CHBF to FARF and FAPN and analyze the theoretical worst-case performance guarantees and average performance guarantees through numerical studies. In FARF, we prove a worst-case performance guarantee of 1/2 for a linear workload-benefit relationship and derive similar guarantees based on job numbers and machine capacities for convex and concave workload-benefit relationships. For FAPN, the problem becomes more complex when there is no clear relationship between benefits and workloads for mathematical analysis. We analyze a special case by adding a bias when converting job workload to job benefit. Regarding the three relationships in FAPN, we find that the performance guarantee reduces to the result in FARF when there is no bias. When the bias level is less than 100%, performance guarantees exist in each of the three relationships.

Finally, numerical studies show that average performance is better than the worst-case guarantees. In FARF, CHBF performs best when job benefits are linear or convex, machines are identical, capacities are loose, and the ratio of jobs-machines is large. In FAPN, CHBF outperforms when job benefits correlate linearly or randomly with workloads, there is no bias, machine capacities are loose, and the jobs-machines ratio is large.