考慮公平性之工作分配問題

Job Allocation with a Consideration of Fairness

劉騏瑋(Chi-Wei Liu)

指導教授 ： 孔令傑

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

https://doi.org/10.6342/NTU201603583

摘要

工作分配在各領域中一直是一個重要議題。在製造業中，其中一個目標是希望能最大化最小利潤的機台。然而，完成工作除了能賺取利潤外，亦會為機台帶來工作量的負擔。這樣的特性，讓工作分配更為困難，儘管希望能多分配工作給機台使其利潤更高，但受到工作量的限制，機台僅能負擔一定工作量。我們希望能設計演算法，在兼顧公平性及工作量負擔下，有效分配工作。
　　在本研究中，我們考慮若干工作及若干機台，完成工作會帶來利潤，但也會為機台帶來工作量，各機台能負荷的最大工作量是一樣的。為了使各機台的利潤盡量地一致，我們的目標是最大化得到最小利潤的機台上的利潤，根據前人的最長處理時間優先演算法（LPT rule），我們提出兩個演算法。
我們證明了我們的第一個演算法在工作利潤與工作量有比例關係時，表現最差的情況會是1/2。除此之外，若工作利潤與工作量是凸函數或凹函數的關係時，我們亦能證明其存在最差表現的保證。透過數值研究分析，我們發現當工作環境有規模經濟效應時，採取第一種演算法表現較好；反之，若工作利潤與工作量呈現邊際效應的遞減，採取第二種演算法較好。了解這個發現後，我們便能知道該在何種環境使用哪一種演算法能讓工作分配較佳。

關鍵字

工作分配 ； 近似演算法 ； 公平性

並列摘要

Job scheduling is an important issue applied in many fields. In the manufacturing industry, one of the objectives is to assign jobs to machines in order to maximize the minimum profit among machines. Nevertheless, jobs not only bring profits, but also bring in workloads. Each machine cannot be assigned too many jobs due to limited capacity. This characteristic introduces a new challenge to this allocation problem. We would like to propose efficient algorithms to assign jobs by taking fairness issue into consideration.
In this study, we consider the aforementioned job allocation problem. Our objective is to assign jobs to bring benefits to all the machines as equally as possible while ensuring that machines cannot be overloaded. In our model, we formulate this problem as a job assignment problem in which a set of jobs is to be assigned to a set of machines to maximize the benefit obtained by the machine earning the minimum benefit. The capacity of all machines are the same. We propose two list scheduling algorithms based on the longest processing time (LPT) rule.
We show that the first algorithm guarantees a 1/2 worst-case performance when the job benefit is proportional to job workload. Moreover, our algorithm can have performance guarantees when the relationship between job benefits and workloads is convex or concave. Through numerical experiments, we also show that the algorithm works well when the jobs exhibit economy of scale but not so well when the jobs exhibit diminishing marginal benefits. The second algorithm is then shown to complement the first one in the latter case. Knowing this result, we can decide which algorithm to apply according to the environment.

並列關鍵字

Job scheduling ； Approximation algorithms ； Fairness

參考文獻

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 Coffman-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.