iSMART 近似演算法：考慮公平性與機台歧異性 之工作分配問題

iSMART: An Approximation Algorithm for Fair Job Allocation on Unrelated Machines

林怡安(Yi-An Lin)

指導教授 ： 孔令傑

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201704133

摘要

排程最佳化與工作分配是經典的研究問題，如何找到有效的方法進行作業排程與機台分配來提高產能利用率進而獲利，科學家們仍不斷在尋找答案。然而，除了經濟考量，近年來公平性的議題也備受重視。每個員工、機台、工廠等(以下我們統稱為機台)都希望能在有限的資源下賺得最大利益，如何將工作公平地分配給各機台是管理者面臨的難題。為了解決這個問題，我們設計了一個近似演算法：iSMART，希望能在機台的工作品質或產能上限具有歧異性的情況下，最大化各機台中的最小收益產能比。此演算法根據一個特殊的公平性指標在迭代，每次都指派最有利的工作給此刻獲得最低分的機台。

經過推導，我們證明出當工作利益與工作負荷為線性關係時，iSMART 是一個 1/2 因子近似演算法，在其表現最差的情況下也有最佳解的一半好。當工作利益與工作負荷為凹函數或凸函數關係時，也存在有最差極值。而根據數值分析，我們發現工作利益與負荷間的關係、機台品質、資源限制與工作機台比都會對於 iSMART 演算法的表現有所影響，這些管理意涵讓管理者可依照其產業特性來決定是否適合採用 iSMART 演算法。最終實驗顯示，iSMART在追求公平性時並不會犧牲掉太大的總體利益，是一個穩定且有效率的演算法。

關鍵字

排程 ； 工作分配 ； 近似演算法 ； 公平性 ； 機台歧異性

並列摘要

Scheduling and job allocation have been widely studied in the past few decades. Designing effective methods to determine job schedules as well as machine assignments helps companies increase productivity and earn more benefits. However, not only economic objectives but also fairness become important issues in recent years. Each agent/machine/factory (hereafter “machine”) is willing to earn the most benefit while being restricted by its limited capacity. Managers face the problem of how to assign jobs to heterogeneous machines in a fair way while job benefits might be different due to diverse machine quality. To address this question, we develop an approximation algorithm: iSMART. Based on a specific fairness indicator, the benefit-capacity ratio, iSMART maximizes the minimum fairness score among all machines by assigning the most beneficial job to the machine with lowest score in each iteration.

By analyzing the algorithm, we prove that iSMART is a factor-½ approximation algorithm when benefits and workloads are in a linear relationship. There are also bounds when benefits and workloads are in a convex or concave relationship. Numerical studies show that the performance of iSMART is influenced by benefit-workload relationship, machine quality, capacity tightness, and the ratio of the number of jobs to the number of machines. This provides managerial implications for decision makers to determine when to adopt the algorithm. We also show that iSMART is a reliable algorithm which does not sacrifice too much efficiency while pursuing fairness.

並列關鍵字

Scheduling ； Job Allocation ； Approximation Algorithm ； Fairness ； Machine Heterogeneity

參考文獻

Alon, N., Y. Azar, G.J.Woeginger, T. Yadid. 1998. Approximation schemes for scheduling on parallel machines. Journal of Scheduling 1(1) 55-66.

Bertsimas, D., V.F. Farias, N. Trichakis. 2011. The price of fairness. Operation Research 59(1) 17-31.

Blazwicz, J., W. Domschke, E. Pesch. 1996. The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research 93(1) 1-33.

Blocher, J.D., S. Sevastyanov. 2015. A note on the Co man-Sethi bound for LPT scheduling. Journal of Scheduling 18(3) 325-327.

Csirik, J., H. Kellerer, G. Woeginger. 1992. The exact LPT-bound for maximizing the minimum completion time. Operations Research Letters 11(5) 281-287.