A New Fairness Model Based on User’s Objective for Multi-user Multi-processor Online Scheduling Problem

Abstract

In multi-user multi-processor online scheduling, resources are shared among competing users, and fairness is considered to be a major performance criterion for resource allocation by the scheduler. Fairness ensures equality of resource sharing among the users. According to our knowledge, fairness based on the user’s objective has neither been thoroughly explored nor a formal model has been well-defined in the literature. In this article, we propose a new fairness model for Multi-user Multi-processor Online Scheduling Problem (MUMPOSP). We introduce and formally define quantitative fairness measures for an online scheduling algorithm based on optimization of makespan as an user’s objective. Furthermore, we define unfairness and absolute fairness for an online scheduling algorithm. Lower bound results are shown for absolute fairness in a scheduling framework of equal length jobs. We show that our proposed fairness model can also measure algorithmic fairness by considering well-known optimality criteria such as sum of completion times, weighted sum of completion times and sum of flow times.

1 Introduction

Fairness is an important performance criterion for a scheduler. Particularly, in multi-user systems, where several users compete for a set of resources (e.g., processor, memory) in order to achieve their objectives, the scheduler must guarantee fairness with respect to allocation of resources and user’s objective. Though fairness has been studied based on resource allocation policies in the literature, there is less attention to devise a quantitative well-defined measure of fairness based on user’s objectives.

User’s objective as a fairness parameter has been motivated from the prevalent use of Web servers in client–server networking, grids and clusters in high-performance computing (HPC). Edge nodes in edge computing, service-oriented systems (SoS) and supercomputers [1]. Unlike the traditional computing systems such as personal computer, the SoS supports multiple users. The users compete for system’s resources for execution of their respective jobs. The most popular cluster scheduler MAUI [2] and the well-known BOINC platform [3] deal with a number of competing users, where each user submits a set of jobs simultaneously and desires minimum time of completion (makespan) for its submissions. A non-trivial challenge for the scheduler is to schedule jobs of multiple users in such a way that each user obtains its desired makespan.

Multi-user Multi-processor Online Scheduling Problem (MUMPOSP)

• Inputs: We are given a set $M=\{M_1, M_2, \ldots , M_m\}$ of m identical processors and a set of n jobs, where $m\ge 2$ and $n>>>m$. Let $U_r$ represents a user, where $1\le r\le k$ and $J^{r}$ is the sequence of jobs requested by user $U_r$, where $J^{r}=(J^{r}_i|1\le i\le n_r)$ such that $J=\bigcup _{r=1}^{k}{J^r}$, $\sum _{r=1}^{k}{n_r}=n$ and $J^x\cap J^y=\phi$, where $x\ne y$ and $1\le x, y\le k$. The processing time of job $J^{r}_i$ is $p^{r}_i$, where $p^{r}_i\ge 1$.

• Output: A schedule (S) in which makespan for each $U_r$ is denoted by $C^{r}_{\max }=\max \{c^{r}_i|1\le i\le n_r\}$, where $c^{r}_i$ is the completion time of job $J^{r}_{i}$

• Objective: Minimization of $C^{r}_{\max }$, $\forall U_r$.

• Constraint: The scheduler can receive a batch of at most r jobs at any time step, and the jobs must be irrevocably scheduled before the arrival of next batch of jobs, where $1\le r\le k$.

• Assumption: Jobs are independent and are requested from k parallel users, where $k\ge 2$.

Illustration of MUMPOSP. For simplicity and basic understanding of the readers, we illustrate an instance of MUMPOSP for scheduling of n jobs that are submitted by k users in Fig. 1. Here, $\{M_1, M_2,\ldots , M_m\}$ represent m identical machines and $\langle U_1, U_2,\ldots , U_{k-1}, U_k \rangle$ denote job sequences for k users, where each user has $\frac{n}{k}$ number of jobs. Jobs are submitted in batches online, where a batch is constructed after receiving exactly one job from each user (as long as a user has an unscheduled job). A batch consists of at least one job. Therefore, we have at least 1 batch, where $k=n$ and at most $n-k+1$ batches, where any one of the users $U_r$ has $n_r=n-k+1$, and remaining users have exactly one job each. Each $U_r$ seeks to obtain a minimum value for its makespan ($C^{r}_{\max }$) as the output, rather than the overall makespan ($C_{\max }$) of the system. Hence, it is indispensable for the scheduler to be fair while optimizing the $C^{r}_{\max }$, $\forall U_r$.

Fig. 1

Illustration of MUMPOSP for k users with equal number of jobs

Representation of MUMPOSP. By following general framework $\alpha |\beta |\gamma$ of Graham et al. [4], we represent MUMPOSP as MUMPOSP$(k, P_m|C^{r}_{\max })$, where $P_m$ denotes m identical machines and k represents number of users.

Perspectives of Fairness. Fairness has been considered and studied as a major performance criterion for scheduling algorithms in multi-user systems [5, 6] from two perspectives such as allocation of resources to the users and user’s objective. Fairness of an algorithm with respect to resource allocation guarantees uniform allocation of resources to the competing users [7]. The resources to be shared are application-dependent. For example, in client-server networking, the resources such as link bandwidth, network delay and specific time quantum can be shared [8, 9], whereas in case of HPC systems, the resources such as processors, memory and time slices can be shared [10, 11].

Algorithmic fairness based on user’s objective is evaluated by the objective values achieved for respective users. An equality in the obtained objective values for a user ensures fairness of a scheduling algorithm. It is important for a fairness measure to define the equality for quantifying gap of an achieved objective value from the defined equality.

Related Work. Fairness as a quantitative performance measure based on resource allocation was studied by Jain et al. [7]. A set of properties for an ideal fairness measure was defined, and a fairness index F(x) was proposed for resource allocation schemes. F(x) is defined as follows: if any scheduling algorithm assigns resources to k competing users such that rth user gets an allocation of $x_r$. Then,

$$F(x)=\frac{({\sum _{r=1}^{k}{x_r}})^2}{\sum _{r=1}^{k}{{x_r}^2}},\quad \text {where}\ x_r\ge 0.$$

The value of F(x) is bounded between 0 and 1 to show percentage of fairness and discrimination of a resource allocation scheme for each user. Fairness based on sharing of resources such as processors, memory, system clock and system bus in multi-programmed multi-user system was well studied in [10,11,12]. Some recent works on fairness in scheduling online jobs on multi-user systems can be found in [13, 14]. To the best of our knowledge, fairness of online scheduling algorithms based on user’s objective has not been exhaustively studied and explored the literature.

In [15,16,17,18], stretch matrix has been considered as a user’s objective-based fairness measure for resource scheduling algorithms in multi-user systems. Here, Stretch ($d^{r}_{A}$) has been defined as a degradation factor in the objective value obtained by any algorithm A for each user $U_r$. Let us consider $V^{r}_{A}$ be the objective value achieved by algorithm A and $V^{r}_{\text {OPT}}$ be the optimum objective value for respective $U_r$. Then, stretch has been defined as follows:

$$ d^{r}_{A}=\frac{V^{r}_{A}}{V^{r}_{\text {OPT}}}$$

The objective of any scheduling algorithm is to incur an equal stretch for each $U_r$ to ensure fairness. Stretch matrix guarantees fairness based on equality in achieved objective values. However, it fails to depict the exact value of fairness per user as well as overall fairness of a scheduling algorithm. Stretch matrix does not capture the discrimination of a scheduling algorithm for the deprived users. Therefore, it is quintessential to define a formal fairness measure based on user’s objective.

Our Contributions. We propose a novel model to evaluate fairness of online algorithms in the Multi-user Multi-processor Online Scheduling Problem (MUMPOSP). We introduce and formally define quantitative fairness measures in our proposed model by considering optimization of makespan as user’s objective. Furthermore, we define unfairness and absolute fairness of an online scheduling algorithm. We obtain lower bound results for the absolute fairness for a framework of m identical machines with equal length jobs. We show that our proposed model can be served as a framework for measuring algorithmic fairness by considering other optimality criteria such as sum of completion times, weighted sum of completion times and sum of flow times.

2 Our Proposed Fairness Model

We develop a new model, in which we define five quantitative measures to ensure algorithmic fairness. Instead of considering the resource allocation at the input level, our model considers the achieved value of user’s makespan at the output level to determine the fairness of a scheduling algorithm. The model captures the issues of relative and global parameters for fairness by a Fairness Index (FI). The issues of unfairness is captured by a Discrimination Index (DI). The FI includes fairness parameters such as Relative Fairness (RF) and Global Fairness (GF). Higher value of any fairness parameter indicates more fair algorithm. The DI includes unfairness measures such as User Discrimination Index (UDI), Global Discrimination Index (GDI) and Relative Discrimination Index (RDI). Lower value of any unfairness measure indicates higher degree of fairness of the algorithm. Before defining fairness and unfairness parameters, we illustrate our novel model and discuss the characteristics of a good fairness model as follows.

Illustration of Our Proposed Fairness Model. We illustrate our proposed fairness model as shown in Fig. 2. The model quantitatively defines the fairness of an online scheduling algorithm by taking into account the makespan ($C^{r}_{\max }$) of individual user in the MUMPOSP setup.

Fig. 2

A fairness model based on user’s objective

2.1 Characteristics of a Good Fairness Model

A fairness model evaluates the performance of a scheduling algorithm based on the achieved makespan for each user. Recall that in [15,16,17,18], Stretch was considered as a user’s objective-based fairness measure. For instance, if a scheduling algorithm A obtains makespans for three users as 5, 10, and 15, respectively, where their respective optimum makespans are 1, 5 and 10, then stretch defines the following degradation factors for respective users: $d^{1}_{A}= 5$, $d^{2}_{A}= 2$, and $d^{3}_{A}= 1.5$.

Before formally defining fairness and unfairness parameters, we present the characteristics of a good fairness model as follows. A good fairness model must be:

• Finitely Bounded—The fairness of a scheduling algorithm is bounded within a finite interval, preferably between 0 and 1 for meaningful representation of fairness with respect to each user.

• Consistent—If any change in the scheduling policy results in different makespans for at least one user, then the change in the fairness parameters must be reflected for the concerned users as well as in the overall fairness of the policy.

• Independent of Input Size—It is applicable to any number of users with any number of jobs and machines.

• Independent of Scale. It must be able to measure fairness irrespective of units of measurement of processing time of the jobs such as seconds or milliseconds, microseconds or nanoseconds. The measuring unit must be uniform or inter convertible.

In addition to the above-mentioned properties, we also consider relative and overall fairness as an essential feature to develop our fairness parameters. We believe that the model must represent relative equality among achieved objective values for the users to show fairness of an algorithm for each user. For example, the users may not seek equal makespan as a gesture of fairness; however, they expect from an online scheduling algorithm to obtain an equal ratio between the desired makespan (optimum value) to the achieved makespan for all users. The value obtained by an algorithm for relative equality leads to relative fairness with respect to each user. Also, the model must show overall fairness of an algorithm with respect to all users, which can lead to the comparison of the fairness of different scheduling policies.

2.2 Our Proposed Fairness and Unfairness Parameters

By considering the above-mentioned desirable properties, we now define formal measures of fairness and unfairness for MUMPOSP as follows.

Let A be an online scheduling algorithm. If algorithm A schedules jobs of k competing users on m identical processors such that rth user obtains a makespan of $C^{r}_{A}$, then we define the following fairness parameters.

Definition 1

The Relative Fairness (RF) obtained by algorithm A for any user $U_r$ is defined as:

$$\begin{aligned} \text {RF}(C^{r}_{A})=\frac{C^{r}_{\text {OPT}}}{C^{r}_{A}}, \quad \text {where}\ C^{r}_{\text {OPT}}=\frac{\sum _{i=1}^{n_r}{p^{r}_{i}}}{m} \end{aligned}$$

(1)

Corollary 1

The Relative Fairness Percentage (RFP) for any user $U_r$ obtained by algorithm A is defined as:

$$\begin{aligned} {RFP}(C^{r}_{A})=RF(C^{r}_{A})\cdot 100 \end{aligned}$$

(2)

Definition 2

The Global Fairness (GF) of algorithm A for k users is defined as:

$$\begin{aligned} \text {GF}(C_{A}, k)=\frac{1}{k}\cdot \sum _{r=1}^{k}{(\text {RF}(C^{r}_{A}))} \end{aligned}$$

(3)

Corollary 2

The Global Fairness Percentage (GFP) of any algorithm A for k users is defined as:

$$\begin{aligned} \text {GFP}(C_{A}, k)=\text {GF}(C_{A}, k)\cdot 100 \end{aligned}$$

(4)

If algorithm A schedules jobs of k competing users such that rth user obtains a makespan of $C^{r}_{A}$, then we define Fairness Index for algorithm A represented by 2-tuple with two parameters such as RF and GF as follows

$$\begin{aligned} \text {FI}(C_A, k)=\langle \{\text {RF}(C^{r}_{A}) | 1\le r\le k\}, \text {GF}(C_{A}, k) \rangle \end{aligned}$$

(5)

Example 1

Let us consider three departments {CSE, MAT, PHY} of a University as three users $\{U_1, U_2, U_3\}$, submitting jobs by MUMPOSP model to a centralized supercomputer (having 2 identical machines) in order to finish their respective projects at the earliest. Let us denote the job sequences of $U_1$, $U_2$, and $U_3$ as $U_1=\langle J^{1}_{1}/1, J^{1}_{2}/2 \rangle$, $U_2=\langle J^{2}_{1}/3, J^{2}_{2}/4 \rangle$ and $U_3=\langle J^{3}_{1}/5, J^{3}_{2}/6 \rangle$, respectively. Suppose that the supercomputer runs an online scheduling algorithm Alg that schedules the jobs of $U_1$, $U_2$ and $U_3$ and obtains $C^{1}_{\text {Alg}}=11$, $C^{2}_{\text {Alg}}=9$ and $C^{3}_{\text {Alg}}=10$, then we have, $\text {RF}(C^{1}_{\text {Alg}})=\frac{1.5}{11}=0.13$ and $\text {RFP}(C^{1}_{\text {Alg}})=13\%$, $\text {RF}(C^{2}_{\text {Alg}})=\frac{3.5}{9}=0.38$ and $\text {RFP}(C^{2}_{\text {Alg}})=38\%$, $\text {RF}(C^{3}_{\text {Alg}})=\frac{5.5}{10}=0.55$ and $\text {RFP}(C_{\text {Alg}})=55\%$. Therefore, we have $\text {GF} (C_{A}, 3)=0.35$ and $\text {GFP} (C_{A}, 3)=35\%$.

Definition 3

The Unfairness of algorithm A for MUMPOSP with respect to each user $U_r$ is defined by User Discrimination Index as:

$$\begin{aligned} \text {UDI}_{A}^{r}=1- \text {RF}(C^{r}_{A}) \end{aligned}$$

(6)

Definition 4

The Overall Unfairness of algorithm A for k users is defined by Global Discrimination Index as:

$$\begin{aligned} \text {GDI}(C^{r}_{A}, k)=1-\text {GF}(C^{r}_{A}, k) \end{aligned}$$

(7)

Definition 5

The Realtive Discrimination Index (RDI) of any algorithm A for MUMPOSP with respect to each user $U_r$ is defined as:

$$\begin{aligned} \text {RDI}_{A}^{r} = {\left\{ \begin{array}{ll} \text {GF}(C^{r}_{A}, k)- \text {RF}(C^{r}_{A}),&{} \text {if} {\ } \text {RF}(C^{r}_{A})< \text {GF}(C^{r}_{A}, k) \\ 0,&{} \text {otherwise} \end{array}\right. } \end{aligned}$$

(8)

If algorithm A schedules jobs of k competing users such that rth user obtains a makespan of $C^{r}_{A}$, then we define Discrimination Index for algorithm A as 3-tuple with three parameters such as UDI, GDI and RDI as follows.

$$\begin{aligned} \text {DI}(C_A, k) = \langle {\,\,} \{\text {UDI}^{r}_{A} {\,\,}| {\,\,}1\le r\le k\}, \text {GDI}(C^{r}_A, k), \{\text {RDI}_{A}^{r}|1\le r\le k\} {\,\,} \rangle \end{aligned}$$

(9)

Example 2

Let us consider algorithm A results in relative fairness for $U_1$, $U_2$, $U_3$ and $U_4$ as 0.6, 0.6, 0.6 and 0.2 respectively. We now have $\text {GF}(C^{r}_{A}, 4)=0.5$. Therefore, $\text {UDI}_{A}^{1}=1-0.6=0.4$, $\text {UDI}_{A}^{2}=1-0.6=0.4$, $\text {UDI}_{A}^{3}=1-0.6=0.4$, $\text {UDI}_{A}^{4}=1-0.2=0.8$, $\text {GDI}(C^{r}_{A}, 4)=1-0.5=0.5$ and $\text {RDI}_{A}^{4}=0.5-0.2=0.3$.

3 Absolute Fairness and Lower Bound Results

We define absolute fairness as a quantitative measure and provide lower bound results of absolute fairness in generic MUMPOSP setting with equal length jobs. Let A be an online scheduling algorithm for the setup MUMPOSP $(k, P_m|C^{r}_{\max })$.

Definition 6

Algorithm A achieves Absolute Fairness if $\text {RF}(C^{r}_{A})$ is same $\forall U_r$, where $1\le r\le k$.

Lemma 1

If any algorithm A incurs $\text {RDI}^{r}_{A}=0$, $\forall U_r$, then it achieves absolute fairness.

Proof

If $\text {RDI}^{r}_{A}=0$, $\forall U_r$, $1\le r\le k$, then by Eq. (8), we have

$$\begin{aligned} \text {RF}(C^{r}_{A})\ge \text {GF}(C^{r}_{A}, k) \end{aligned}$$

(10)

By Eqs. (3) and (10), we can infer that

$$\text {RF}(C^{r}_{A})=\text {GF}(C^{r}_{A}, k), \forall U_r.$$

Therefore, Lemma 1 holds true. $\Box$

Definition 7

Any Algorithm A is b-fair, if it achieves $\text {RF}(C^{r}_{A})=b$ for all $U_r$, where $1\le r\le k$ and $0<b\le 1$.

Theorem 1

Any online algorithm A achieves absolute fairness in the setup MUMPOSP ($k, P_2 |C^{r}_{\max }$) such that $\frac{C^{r}_{\text {OPT}}}{C^{r}_{A}}\ge \frac{1}{k}$, $\forall U_r$, where $k\ge 2$ and $1\le r\le k$.

Proof

Let us consider an instance of MUMPOSP ($k, P_| C^{r}_{\max })$, where $k=2$. We analyze two cases based on $n_r$ as follows.

• Case 1: $n_1\ne n_2$.

• Case 1(a): If the first job pair ($J^{1}_{1}, J^{2}_{1}$) is scheduled on different machines. Let us consider the following instance $U_1:\langle J^{1}_2/2, J^{1}_1/1 \rangle$, $U_2:\langle J^{2}_{1}/1 \rangle$, where each job is specified by its processing time. Assigning $J^{1}_{1}/1$ and $J^{2}_{1}/1$ to machines $M_1$ and $M_2$, respectively, followed by the assignment of $J^{1}_{2}/2$ to either of the machines such that $C^{1}_{A}=3$ and $C^{2}_{A}=1$, where $C^{1}_{\text {OPT}}\ge 1.5$ and $C^{2}_{OPT}\ge 0.5$. Therefore, we have $\frac{C^{1}_{\text {OPT}}}{C^{1}_A}\ge \frac{1}{2}$ and $\frac{C^{2}_{\text {OPT}}}{C^{2}_A}\ge \frac{1}{2}$.

• Case 1(b): If the first job pair ($J^{1}_{1}, J^{2}_{1}$) is scheduled on the same machine. Let us consider the following instance $U_1:\langle J^{1}_3/2, J^{1}_2/1, J^{1}_1/1 \rangle$, $U_2:\langle J^{2}_{2}/2, J^{2}_{1}/1 \rangle$. If the first job pair ($J^{1}_{1}/1, J^{2}_{1}/1$) is scheduled either on machine $M_1$ or on $M_2$, then by assigning the next pair of jobs ($J^{1}_{2}, J^{2}_{2}$) to the same or different machines, followed by the assignment of job $J^{1}_{3}/2$ such that $C^{1}_{A}=4$ and $C^{2}_{A}=3$, where $C^{1}_{\text {OPT}}\ge 2$ and $C^{2}_{\text {OPT}}\ge 1.5$. Therefore, we have $\frac{C^{1}_{\text {OPT}}}{C^{1}_A}\ge \frac{1}{2}$ and $\frac{C^{2}_{\text {OPT}}}{C^{2}_A}\ge \frac{1}{2}$.

• Case 2: $n_1=n_2$.

• Case 2(a): If the first job pair ($J^{1}_{1}, J^{2}_{1}$) is scheduled on different machines. Let us consider the following instance $U_1:\langle J^{1}_3/2, J^{1}_2/1, J^{1}_1/1 \rangle$, $U_2:\langle J^{2}_{3}/2, J^{2}_{2}/2, J^{2}_{1}/1 \rangle$. Assigning jobs $J^{1}_1/1$ and $J^{2}_{1}/1$ to machines $M_1$ and $M_2$ respectively, followed by the assignment of the subsequent jobs as shown in Fig. 3a, such that $C^{1}_{A}=4$ and $C^{2}_{A}=5$, where $C^{1}_{\text {OPT}}\ge 2$ and $C^{2}_{\text {OPT}}\ge 2.5$. Therefore, we have $\frac{C^{1}_{\text {OPT}}}{C^{1}_A}\ge \frac{1}{2}$ and $\frac{C^{2}_{\text {OPT}}}{C^{2}_A}\ge \frac{1}{2}$.

• Case 2(b): If the first job pair ($J^{1}_{1}, J^{2}_{1}$) is assigned to the same machine. We consider the same instance of Case 2(a). Assigning $J^{1}_{1}/1$ and $J^{2}_{1}$ on either machine $M_1$ or on $M_2$, followed by the assignment of the subsequent jobs as shown in Fig. 3b such that $C^{1}_{A}=4$ and $C^{2}_{A}=5$. Therefore, we have $\frac{C^{1}_{\text {OPT}}}{C^{1}_A}\ge \frac{1}{2}$ and $\frac{C^{2}_{\text {OPT}}}{C^{2}_A}\ge \frac{1}{2}$. $\Box$

Fig. 3

Illustration of case 2

3.1 Results on Absolute Fairness in MUMPOSP with m Identical Machines for Equal Length Jobs

For ease of understanding, we analyze the lower bound of absolute fairness for any online algorithm in a generic MUMPOSP setting, where each user has equal number of jobs, and all jobs have equal processing time of x unit, where $x\ge 1$. The objective of each user is to obtain a minimum $C^{r}_{\max }$. We formally denote the problem as MUMPOSP ($k, P_m | p^{r}_{i}=x | C^{r}_{\max }$).

Lemma 2

Let A be an online scheduling algorithm. In MUMPOSP ($k, P_m | p^{r}_{i}$=$x | C^{r}_{\max })$ with $k=b\cdot m$, algorithm A obtains $C^{r}_{A}\le b\cdot \sum _{i=1}^{n_r}{p^{r}_{i}}$, for each $U_r$, respectively, where $1\le r\le k$, $m\ge 2$ and $b\ge 1$.

Proof

We prove Lemma 2 by method of induction on number of jobs per user ($n_r$) as follows.

Induction Basis: Let us consider $k=m=2$, $n_1=n_2=1$ and $p^{1}_1=p^{2}_1=1$.

Clearly, $C^{r}_{A}=1 \le b\cdot 1\cdot 1$, where $r=1, 2$ and $b\ge 1$.

Induction Hypothesis: Let us consider $k=b\cdot m$, $n_r=\frac{n}{k}=y$, where $y\ge 1$, $b\ge 1$ and $n=\sum _{r=1}^{k}{n_r}$.

We assume that

$$\begin{aligned} C^{r}_{A} \le b\cdot \sum _{i=1}^{n_r}{p^{r}_{i}}\le b\cdot x\cdot y \end{aligned}$$

(11)

Inductive Step: For $n_r=y+1$ with $p^{r}_{i}=x$, $\forall J^{r}_{i}$. We have to show that $C^{r}_{A} \le (y+1)\cdot b\cdot x$.

By Eq. (11), we have $C^{r}_{A}=y\cdot b\cdot x$ with $n_r=y$. When we add extra one job to each user, we have by Induction Basis $C^{r}_{A}=b\cdot x\cdot y+(b\cdot x)=(y+1)\cdot b\cdot x$. Therefore, Lemma 2 holds true. $\Box$

Lemma 3

Any algorithm A is $\frac{1}{k}$-fair for MUMPOSP ($k, P_m | p^{r}_{i}=x| C^{r}_{\max }$) with $k=b\cdot m$, where $m\ge 2$ and $b\ge 1$.

Proof

By Lemma 2, we have

$$\begin{aligned} C^{r}_{A} \le b\cdot \sum _{i=1}^{n_r}{p^{r}_{i}}, \forall U_r \end{aligned}$$

(12)

We have the fair optimum bound as

$$\begin{aligned} C^{r}_{\text {OPT}}\ge \frac{\sum _{i=1}^{n_r}{p^{r}_{i}}}{m}, \quad \forall U_r \end{aligned}$$

(13)

By Eqs. (12) and (13), we have

$$\begin{aligned} \frac{C^{r}_{\text {OPT}}}{C^{r}_{A}} \ge \frac{1}{k}, {\,\,}\forall U_r. \end{aligned}$$

(14)

Therefore, Lemma 3 holds true. $\Box$

Lemma 4

In MUMPOSP ($k, P_m | p^{r}_{i}=x| C^{r}_{\max }$) with $k> m$, algorithm A obtains $C^{r}_{A}\le \lceil \frac{n}{m}\rceil \cdot x$, for each $U_r$ respectively, where $k\ne m\cdot b$ for $b\ge 1$.

Proof

The correctness of Lemma 4 is shown by method of induction on $n_r$ as follows.

Induction Basis: Let us consider $m=2$, $k=3$, $n_r=1$ and $p^{r}_{i}=1$. Now, we have $n=n_r\cdot k=3$.

Clearly, $C^{r}_{A}\le 2=\lceil \frac{n}{2}\rceil \cdot 1$.

Induction Hypothesis: Let us consider $n_r=\frac{n}{k}=y$, $p^{r}_{i}=x$ and $k> m$ with $k\ne m\cdot b$ for $b\ge 1$. We assume that $C^{r}_{A}\le \lceil \frac{n}{m}\rceil \cdot x$, $\forall U_r$.

Inductive Step: We show that $C^{r}_{A}\le \lceil \frac{n+k}{m}\rceil \cdot x$ for $n_r=y+1$, $\forall U_r$.

By our Induction Basis, for one extra job of each user $U_r$, where $1\le r\le k$, algorithm A incurs an additional time of $\lceil \frac{k}{m}\rceil \cdot x$ for each $U_r$.

Therefore, $C^{r}_{A}\le \lceil \frac{n}{m}\rceil \cdot x + \lceil \frac{k}{m}\rceil \cdot x \le \lceil \frac{n+k}{m}\rceil \cdot x$

Thus, Lemma 4 holds true. $\Box$

Theorem 2

Any Algorithm A is $\frac{1}{k}$-fair for MUMPOSP ($k, P_m | p^{r}_{i}=x| C^{r}_{\max }$), where $k\ge m$ and $m\ge 2$.

Proof

Theorem 2 holds true by Lemma 3 for $k=m\cdot b$, where $b\ge 1$.

By Lemma 4, we have

$$\begin{aligned} C^{r}_{A}\le \lceil \frac{n}{m}\rceil \cdot x \end{aligned}$$

(15)

By Eq. (13), we have $C^{r}_{\text {OPT}}\ge \frac{\frac{n}{k}\cdot x}{m}$.

Implies,

$$\begin{aligned} C^{r}_{\text {OPT}}\ge \frac{n\cdot x}{k\cdot m} \end{aligned}$$

(16)

By Eqs. (14) and (15), we have

$$\begin{aligned} \frac{C^{r}_{\text {OPT}}}{C^{r}_{A}}&\ge \frac{\frac{n\cdot x}{k\cdot m}}{\frac{n\cdot x}{m}}\\&\ge \frac{n\cdot x\cdot m}{n\cdot k \cdot m \cdot x}\ge \frac{1}{k}.\qquad \qquad \square \end{aligned}$$

4 Fairness Measure Using Flow Time and Completion Time as User’s Objective

We show that our proposed Fairness Index can be served as a framework for measuring fairness of any algorithm based on well-known user’s objectives such as sum of completion times ($S^{r}$), weighted sum of completion times ($W^{r}$) and sum of flow times ($\text {SF}^{r}$). Selection of an user’s objective is application-dependent. For instance, users of interactive systems require optimized value for respective flow time $f^{r}$, where $f^{r}_{i}$ of any $J^{r}_{i}$ is the difference between its completion time $c^{r}_{i}$ and arrival time $t^{r}_{i}$. We now define relative fairness measures based on the above-mentioned user’s objectives, respectively, by our proposed FI.

• Sum of Completion Times ($S^{r}$): Here, the objective for each $U_r$ is to obtain a minimum $S^{r}=\sum _{i=1}^{n_r}{c^{r}_{i}}$. The relative fairness for any $U_r$, obtained by any algorithm A based on $S^{r}$ is defined as

  $$R_{A}(S^{r}_{A})=\frac{S^{r}_{\text {OPT}}}{S^{r}_{A}},\quad \text {where}\ S^{r}_{\text {OPT}}\ \text {is the optimum value for}\ S^{r}.$$

• Weighted Sum of Completion Times ($W^{r}$): Here, the $c^{r}_{i}$ is associated with certain positive weight $w^{r}_{i}$. The objective for each $U_r$ is to obtain a minimum $W^{r}=\sum _{i=1}^{n_r}{w^{r}_{i}\cdot c^{r}_{i}}$. The relative fairness for any $U_r$ obtained by algorithm A based on $W^{r}$ is defined as

  $$R_{A}(W^{r}_{A})=\frac{W^{r}_{\text {OPT}}}{W^{r}_{A}}\quad \text {where},\ W^{r}_{\text {OPT}}\ \text {is the optimum value for}\ W^{r}.$$

• Sum of Flow Times (${\text {SF}}^{r}$): Here, each $U_r$ wants a minimum value for respective ${\text {SF}}^{r}=\sum _{i=1}^{n_r}{f^{r}_{i}}$, where $f^{*r}_{i}$ is the desired value of $f^{r}_{i}$ and ${\text {SF}}^{r}_{\text {OPT}}=\sum _{i=1}^{n_r}{f^{*r}_{i}}$. The relative fairness for any $U_r$ obtained by algorithm A based on ${\text {SF}}^{r}$ is defined as

  $$R_{A}({\text {SF}}^{r}_{A})=\frac{{\text {SF}}^{r}_{\text {OPT}}}{{\text {SF}}^{r}_{A}}.$$

5 Concluding Remarks and Scope of Future Work

In this work, we make an attempt to address the non-trivial research challenge of defining a new fairness model with quantitative measures of algorithmic fairness for Multi-user Multi-processor Online Scheduling Problem (MUMPOSP) based on user’s objective. We formally presented the MUMPOSP setting with an illustration followed by a discussion on perspectives of fairness in MUMPOSP. We have proposed a new fairness model and have defined five quantitative measures to ensure algorithmic fairness by considering minimization of makespan as the user objective. Lower bound results on absolute fairness of an online scheduling algorithm have been shown in MUMPOSP setup with equal length jobs. We have shown how our proposed fairness measure can be served as a framework for measuring algorithmic fairness based on well-known user’s objectives such as sum of completion times, weighted sum of completion times and sum of flow times.

Scope of Future Work. We assumed a ideal theoretical bound for $C^{r}_{\text {OPT}}$. It is still open to explore a realistic bound for $C^{r}_{\text {OPT}}$. A non-trivial challenge is to compare the fairness of any two online scheduling algorithms A and B, when global fairness of algorithms A and B are same, whereas relative fairness of A is more than that of B for some users or vice-versa. In this scenario, it is interesting to make a trade-off by considering the number of users and individual relative fairness for each user to compare the fairness of two different algorithms.