Scheduling with Time Dependent Utilities: Fairness and Efficiency

Gaia Nicosia; Andrea Pacifici; Ulrich Pferschy

cs.GTMar 26, 2026

Scheduling with Time Dependent Utilities: Fairness and Efficiency

Authors: Gaia Nicosia, Andrea Pacifici, Ulrich Pferschy

Organizations: Dipartimento di Ingegneria Civile, Informatica e delle Tecnologie Aeronautiche, Università degli Studi “Roma Tre”, via della Vasca Navale 79, 00146 Rome, Italy · Dipartimento di Ingegneria Civile e Ingegneria Informatica, Università degli Studi di Roma “Tor Vergata”, Via del Politecnico 1, 00133 Rome, Italy · Department of Operations and Information Systems, University of Graz, Universitaetsstrasse 15, 8010 Graz, Austria

Abstract

A new class of multi agent single machine scheduling problems is introduced, where each job is associated with a self interested agent with a utility function decreasing in completion time. We aim to achieve a fair solution by maximizing the minimum utility across all agents. We study the problem's complexity and propose solution methods for several variants. For the general case, we present a binary search procedure to find the largest possible minimum utility, as well as an exact greedy based alternative. Variants with release and due dates are analyzed, showing strong NP hardness for arbitrary release dates, but weak NP hardness for a single release date job, and polynomial solvability when all jobs share processing times. For all these cases we also study the corresponding problem of finding efficient solutions where the sum of utilities is maximized. We also examine settings where linear utility functions can be adjusted within budget constraints, exploring the impact on optimal schedules when intercepts or slopes are modified. From a single agent perspective, we investigate the effect of improving one agent's utility in the overall solution. Adding a new job to be inserted with the best possible utility gives rise to rescheduling problems, where different lower bounds depending on the utilities of the original fair schedule are imposed. Finally, we consider a bi level setting where a leader wants to enforce a certain target schedule by modifying utility functions while the follower computes a fair solution for the modified instance. Our work contributes to scheduling theory, multi agent systems, and algorithmic fairness, highlighting fairness oriented objectives in competitive scheduling.

Figures & tables

$J:=\{1,\ldots,n\}$	set of jobs/agents indexed by $j$
$p_{j}$ , $r_{j}$ , $d_{j}$ ,	processing time, release date, due date of job $j$
$P:=\sum_{j}^{n}p_{j}$	total processing time of the jobs
$s_{j}(\sigma)$ , $s_{j}$	starting time of job $j$ in schedule $\sigma$
$C_{j}(\sigma)$ , $C_{j}$	completion time of job $j$ in schedule $\sigma$
$u_{j}(C_{j}(\sigma))$ , $u_{j}(C_{j})$ , $u_{j}(\sigma)$	utility of job $j$ completing at $C_{j}$ in schedule $\sigma$
$u_{j}(C_{j})=b_{j}-a_{j}C_{j}$	linear utility of job $j$ completing at $C_{j}$

Table 1: Notation

N.	Problem specifications	Notation	Section
1	general utilities, objective $f=u_{\min}$ or $f=\sum u_{j}$	$1\|u_{j}\|f$	4.1 , 4.2
2	linear utilities, objective $f\in\{u_{\min},\sum u_{j}\}$	$1\|u_{j}=b_{j}-a_{j}C_{j}\|f$	4.1 , 4.2
3	release dates, linear utilities, objective $f\in\{u_{\min},\sum u_{j}\}$	$1\|r_{j},u_{j}=b_{j}-a_{j}C_{j}\|f$	4.3
4	release dates, unitary proc. times, lin. utilities, obj. $f\in\{u_{\min},\sum u_{j}\}$	$1\|p_{j}=1,r_{j},u_{j}=b_{j}-a_{j}C_{j}\|f$	4.3
5	release dates, equal proc. times, lin. utilities, obj. $f\in\{u_{\min},\sum u_{j}\}$	$1\|p_{j}=p,r_{j},u_{j}=b_{j}-a_{j}C_{j}\|f$	4.3
6	due dates, lin. utilities, bounded # of late jobs, obj. $f\in\{u_{\min},\sum u_{j}\}$	$1\|\sum U_{j}\leq k,u_{j}=b_{j}-a_{j}C_{j}\|f$	4.4

Table 2: Description of addressed problem variants and adopted Graham notation.

Problem	Complexity for $f=u_{\min}$	Complexity for $f=\sum u_{j}$
$1\|u_{j}\|f$	Polynomial (Thm. 2 )	Strongly NP-hard (Obs. 1 )
$1\|u_{j}=b_{j}-a_{j}C_{j}\|f$	Polynomial (Thm. 2 )	Polynomial ( Smith, 1956 )
$1\|r_{j},\,u_{j}=b_{j}-a_{j}C_{j}\|f$	Strongly NP-hard (Thm. 3 )	Strongly NP-hard (Thm. 5 )
$1\|p_{j}=1,\,r_{j},\,u_{j}\|f$	Polynomial (Thm. 7 )	Polynomial: assignment (Obs. 8 )
$1\|p_{j}=p,\,r_{j},\,u_{j}\|f$	Polynomial (Thm. 9 )	Polynomial (see Baptiste, 2000 , Obs. 10 )
$1\|\sum U_{j}\leq k,\,u_{j}=b_{j}-a_{j}C_{j}\|f$	Polynomial (Thm. 12 )	Strongly NP-hard (Thm. 13 )

Table 3: Overview of results for problems 1–6 of Table 2

Problem	Complexity
$1\|u_{j}=\tilde{b}_{j}-a_{j}C_{j}\|u_{\min}$	Polynomial (Sect. 5.1 )
$1\|u_{j}=b_{j}-\tilde{a}_{j}C_{j}\|u_{\min}$	Polynomial (Sect. 5.2 )
$1\|u_{j}=\tilde{b}_{j}-\tilde{a}_{j}C_{j},\,\tilde{A}_{j}=A_{j}\|u_{\min}$	Polynomial (Sect. 5.3 )
$1\|\tilde{u}_{i}\|u_{i}$	Polynomial (Sect. 5.4 )
$1\|\mbox{\it resch},\,\delta_{j}\geq 0\|u_{n+1}$	Weakly NP-hard (Thm. 14 )
$1\|\mbox{\it resch},\,\textstyle\sum\delta_{j}\geq 0\|u_{n+1}$	Weakly NP-hard (Thm. 15 )

Table 4: Overview of results for problems 7–16 of Table 2

Panel of Figure 1 — Figure 1: Algorithm MaxMinGreedy applied to an instance of $1|u_{j}|u_{\min}$ with three jobs and linear utility functions.

Figure 2: Proof of Theorem 6 : Non-balanced schedule

\sigma^{*}

and balanced schedule

\tilde{\sigma}

obtained by swapping blocks

E

and

L

Panel of Figure 3 — Figure 3: Example to illustrate that idle times may be useful. Schedule $\langle 1,2\rangle$ without idle times in red, optimal schedule $\langle 2,1\rangle$ with idle time in blue.

Figure 4: Optimal schedules corresponding to a yes -instance (above) and a no -instance of 3-Partition with

n=3

Panel of Figure 5 — Figure 5: Function $\tilde{u}_{j}(C_{j}(\sigma))$ as defined in ( 5.3 ).

Panel of Figure 6 — Figure 6: Increased utility $\tilde{u}_{i}$ as a function of the increase of the intercept $\Delta b_{i}$ .

Panel of Figure 7 — Figure 7: Increased utility $\tilde{u}_{i}$ as a function of the increase of the slope $\Delta a_{i}$ .

Panel of Figure 8 — Figure 8: Increased utility $\tilde{u}_{i}$ as a function of the increase of the area $\Delta A_{i}$ .

Figure 9: Original schedule

\sigma_{F}

output by MaxMinGreedy (above) and the schedule after inserting job

n+3

(below).

Fair Resource Allocation

Fair resource allocation studies how to distribute scarce goods, services, and computing capacity equitably while accounting for efficiency and constraints.

See all 57 papers

Jun 9, 2026

Trading Utility for Dynamic Fairness in Multiple Resource Division with Sequential Demand

Dynamic multi-resource allocation is a central problem in shared computing environments, where users' demands arrive sequentially and resources must be distributed fairly without knowledge of future demands. Existing methods emphasize fairness guarantees such as Sharing Incentive, Envy Freeness, and Dynamic Pareto Optimality, but often overlook system utility. Moreover, these fairness criteria are mutually incompatible, preventing strict enforcement of them at the same time. We propose a neural allocation mechanism that reconciles fairness with utility through multi-objective optimization during sequential rollout. We first formalize fairness in the dynamic setting via stepwise loss functions for Sharing Incentive, Envy Freeness, and Dynamic Pareto Optimality, enabling differentiable training. Leveraging non-wastefulness, we parameterized the solutions by constraining allocations to the subspace of demand while allowing elastic over-allocation when resources remain available. Empirical results demonstrate that our learned allocator achieves substantially higher utility at comparable levels of fairness, uncovering clear Pareto-frontier-like tradeoffs across metrics.

Kaiqi Jiang, Karim El Husseini, Wenzhe Fan +1

Computer Science Dept., University of Illinois Chicago, Chicago, Illinois, USA

Sequential Decision Making Fair Resource Allocation Algorithmic Fairness Online Resource Allocation

Ask PDF

Jul 26, 2026

Outcome-Fair Restless Multi-Armed Bandits for Stochastic Deadline Scheduling

We study a restless multi-armed bandit (RMAB) problem for a stochastic deadline scheduling application. RMAB problems are solved using the Whittle index policy. The goal in RMAB is to maximize the expected cumulative discounted reward maximization. The Whittle index policy maximizes reward, but is not fair among two classes. In this paper, we introduce fairness criteria and study an outcome-fair model for RMAB which allows fairness for jobs and users structurally disadvantaged demographic classes. We formulate an outcome fair stochastic deadline scheduling problem as RMAB, and we develop the outcome fair Whittle index policy. We define a virtual queue mechanism that dynamically enforces long-term completion rate guaranties across demographic groups. We analyze a standard Whittle index policy and the outcome-fair index policy. We demonstrate the performance of our algorithms with numerical examples. We compare policies---Whittle index policy (no fairness), input-fairness Whittle index policy, outcome fair Whittle index policy. We observe that the outcome-fair Whittle index policy provides better fairness among classes compared to other policies. We demonstrate a trade off between fairness and profit. This decreases as the server capacity increases.

Shakti Sharma, Rahul Meshram

Dept. of Physics, IIT Madras, Chennai, India. · Dept. of Electrical Engineering, IIT Madras, Chennai, India.

Sequential Decision Making Fair Resource Allocation Algorithmic Fairness Group Fairness

Ask PDF

Jun 17, 2026

Fair Online Resource Allocation

We study the problem of fair online resource allocation, motivated by applications such as refugee resettlement and airline scheduling, where agents arrive sequentially and must be assigned to facilities with limited capacities. We introduce a model that maximizes the overall welfare subject to resource constraints and a Lipschitz fairness requirement, which ensures that similar agents arriving in the same batch receive similar expected outcomes. We first analyze the offline problem, proving that the value of the optimal fair allocation is at least an

Ω(1/γ)

fraction of the optimal unfair allocation, where

γ

is the fairness coefficient, thereby bounding the price of fairness. For the online setting, we propose an algorithm based on dual mirror descent that enforces fairness constraints within batches while estimating optimal dual variables. We prove that this algorithm achieves sublinear regret relative to the optimal offline fluid benchmark. Finally, we validate our theoretical results using real-world data from the Refugee Economies Programme, demonstrating the algorithm's performance and examining the trade-offs between welfare maximization and fairness enforcement.

Christopher En, Yuri Faenza, Andrea Lodi +1

Columbia University, IEOR Department · Cornell Tech · Universidad de Chile

Sequential Decision Making Fair Resource Allocation Algorithmic Fairness Group Fairness Online Resource Allocation

Ask PDF

Abstract

Fair Resource Allocation

Explore similar work

Trading Utility for Dynamic Fairness in Multiple Resource Division with Sequential Demand

Outcome-Fair Restless Multi-Armed Bandits for Stochastic Deadline Scheduling

Fair Online Resource Allocation