We investigate a novel scheduling problem where we have $n$ clients, each associated with a single job on each of a set of $m$ different days. On each day, a single machine is available to process the $n$ jobs non-preemptively. The goal is provide an equitable set of schedules for all $m$ days such that the sum of completion times of each client over all days is not greater than some specified equability parameter $k$. The $1\mid\mid\max_j\sum_i C_{i,j}$ problem, as we refer to it in this paper, fits nicely into a new model introduced by Heeger et al. [AAAI '21] that aims at capturing a generic notion of fairness in scheduling settings where the same set of clients repeatedly submit scheduling requests over a fixed period of time. We show that the $1\mid\mid\max_j\sum_i C_{i,j}$ problem is NP-hard even under quite severe restrictions. This leads us to investigating two natural special cases: One where we assume the number of days to be small and one where we consider the number of clients to be small. We present several tractability results for both cases.
翻译:我们调查了一个新颖的日程安排问题,即每个客户都有一美元,每个客户在每套不同的日子里都有一份工作,每套美元。每天,都有一台机器可以不先发制人地处理每份工作。目标是为所有的美元日提供一套公平的日程安排,使每个客户在一天之内的完成时间总和不超过某些规定的公平性参数$k美元。1美元Mid\mid\max_j\sum_i C ⁇ i,j}美元问题,正如我们在本文中所提到的那样,很好地适用于Heiger等人[AAI'推出的新模式,目的是在日程安排中体现一种一般的公平概念,即在同一组客户在固定的时间内反复提交日程安排请求。我们显示,1美元问题即使存在相当严格的限制,也是难以解决的。这导致我们调查了两个自然特例:一个我们假设几天是小的天数,另一个我们认为客户数目是小的案件。