考慮釋放時間限制之公平工作分配與排程演算法

A Fair Multi-Agent Job Assignment and Scheduling Algorithm Considering Release Times

李璨婷(Tsan-Ting Li)

指導教授 ： 孔令傑

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

https://doi.org/10.6342/NTU201901456

摘要

工作分配與排程問題在許多領域中一直是個重要的議題，有效的工作分配與排程有助於公司提高生產力以獲得更多利益。在現今競爭激烈的世代中，為了持續保有市佔率與客源，服務業者必須盡量減少延遲服務的時間以提高服務品質，且在工作有不同釋放時間的情況下，這就更具挑戰性。其中典型的衡量目標為最小化總等待時間。
除了上述經濟考量，公平性議題也變得越來越重要，每位員工都希望能在有限的資源下賺得最大利益，因此如何在最小化等待時間的同時，將工作公平地分配給每位員工，為管理者處理這一工作分配和排程問題帶來了新的挑戰。因此，我們希望設計一個演算法，兼顧公平性及等待時間最小化，有效分配工作與排程。
在本研究中，我們考慮若干工作及若干員工，完成工作會帶來利益，但也可能產生等待時間。為了最小化等待時間同時使各員工的獲利盡量地一致，我們的目標是最大化最低獲利員工的獲利除以總等待時間，並提出演算法HB-SRPT，此演算法結合了最長處理時間優先演算法（LPT rule）和最短剩餘處理時間優先演算法（SRPT rule），在分配工作時考慮公平性，並排序工作以最小化總等待時間。
我們證明當員工只有一位且所有工作的釋放時間皆相同的情況時，使用HB-SRPT可以得到最佳解。當只有一位員工且工作的釋放時間相異或有多位員工且工作的釋放時間相同時，我們證明HB-SRPT有最差情況的效能保證。我們也用數值實驗確認HB-SRPT平均而言具有良好效能。

關鍵字

排程 ； 公平性 ； 等待時間 ； 釋放時間 ； 近似演算法

並列摘要

Job assignment and scheduling problem is an important issue in many fields over the past few years, and effective job assignment and scheduling helps companies increase productivity and earn more benefits. In today's highly competitive environment, in order to ensure their market and customers, service providers must provide high quality services by paying attention to the beginning of service to avoid waiting. This is even more challenging if jobs are released at different moments. The issue of waiting time then arises. Waiting time is a measure of delay in executing certain operations. One typical goal of service providers in practice is to schedule jobs to minimize the total waiting time.
In addition to the above economic goal, the fairness issue is also becoming more and more important. More precisely, each agent wants to earn as much benefit as possible while not generating too long waiting time for customers. This characteristic introduces a new challenge for decision makers to deal with. Therefore, we want to design an algorithm that considers both fairness and waiting time to effectively assign and schedule jobs to agents.
In this study, we consider a job assignment and scheduling problem. Our objective is to maximize the ratio of the benefit earned by the agent earning the least to the total waiting time. Because this problem is NP-hard, we propose an algorithm HB-SRPT, which combines the longest processing time first (LPT) and shortest remaining processing time first (SRPT) rules to maximize fairness and schedule jobs to minimize total waiting time.
When there is only one agent, we prove that our algorithm is optimal for the case of equal job release times. For the cases of one agent with different job release times or multiple agents with equal job release times, we prove its worst-case performance guarantee. We also conduct numerical experiments to examine the average-case performance of our algorithm.

並列關鍵字

Job Scheduling ； Fairness ； Waiting Time ； Release Time ； Approximation Algorithm

參考文獻

Bansal, N., M. Sviridenk, 2006. The Santa Claus Problem, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, 31-40.

Bertsimas, D., V.F. Farias, N. Trichakis, 2011. The Price of Fairness, Operational 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.

Bruno, J., E. G. Coman, Jr., R. Sethi. 1974. Scheduling independent tasks to reduce mean finishing time. Communications of the ACM, 17(7) 382-387.

Cohen-Charash, Yochi, Paul E. Spector. 2001. The role of justice in organizations: A meta-analysis. Organizational Behavior and Human Decision Processes, 86(2) 278-321.