Scheduling uniform machines with restricted assignment

1.   Introduction

Scheduling jobs on (identical, uniform, or unrelated) parallel machines is one of the fundamental problems in deterministic scheduling theory ^[1,2,3]. In this paper, the problem of scheduling uniform machines with restricted assignment is studied, which generalizes the problem of scheduling jobs with unrestricted assignment on parallel machines.

Formally, there is a set of jobs $\mathcal{J} = \{1, 2, \ldots, n\}$, and there is a set of uniform machines $\mathcal{M} = \{{{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{m}}\}$. Job $j\in \mathcal{J}$ has a length ${{p}_{j}}\ge 0$ and a subset of machines ${{\mathcal{M}}_{j}}\subseteq \mathcal{M}$ to which it can be assigned, called its processing set. Machine ${{M}_{i}}\in \mathcal{M}$ has a speed ${{s}_{i}}$. Without loss of generality, we assume that all ${{s}_{i}}\ge 1$. If job $j$ is processed on machine ${{M}_{i}}$, then its processing time is ${{p}_{j}}/{{s}_{i}}$. A (non-preemptive) schedule is an $m$-tuple $({{\mathcal{S}}_{1}}, {{\mathcal{S}}_{2}}, \ldots, {{\mathcal{S}}_{m}})$, where ${{\mathcal{S}}_{i}}$ denotes the set of the jobs processed on machine ${{M}_{i}}$, $i = 1, 2, \ldots, m$. The sets ${{\mathcal{S}}_{1}}, {{\mathcal{S}}_{2}}, \ldots, {{\mathcal{S}}_{m}}$ are disjoint, and $\bigcup _{i = 1}^{m}{{\mathcal{S}}_{i}} = \mathcal{J}$, i.e., each job in $\mathcal{J}$ appears in exactly one ${{\mathcal{S}}_{i}}$. The completion time $C({{\mathcal{S}}_{i}})$ of machine ${{M}_{i}}$ in this schedule is given by $\sum\nolimits_{j\in {{\mathcal{S}}_{i}}}{{{p}_{j}}/{{s}_{i}}}$. The goal is to find a schedule to minimize the makespan, ${{C}_{\max }} = {{\max }_{i}}C({{\mathcal{S}}_{i}})$. Using the notations proposed in ^[4,5], the problem is denoted as $Q|{{\mathcal{M}}_{j}}|{{C}_{\max }}$.

As stated in the survey paper by Leung and Li ^[6], there are five types of assignment restrictions studied by the researchers: inclusive, nested, interval, tree-hierarchical and arbitrary. In this paper, we focus on the inclusive and tree-hierarchical restrictions, i.e., we study $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. The assignment restriction is inclusive, if for any job $j$, ${{\mathcal{M}}_{j}} = \{{{M}_{{{a}_{j}}}}, {{M}_{{{a}_{j}}+1}}, \ldots, {{M}_{m}}\}$, where ${{a}_{j}}$ ($1\le {{a}_{j}}\le m$) is called the machine index associated with job $j$. The assignment restriction is tree-hierarchical, if there is a tree whose nodes represent the machines, and each job $j$ is associated with a tree node ${{M}_{{{a}_{j}}}}$, such that ${{\mathcal{M}}_{j}}$ consists of the machines on the path from ${{M}_{{{a}_{j}}}}$ to the root of the tree. Clearly, the inclusive restriction is a special case of the tree-hierarchical restriction.

Leung and Ng ^[7] studied the problems $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$ under a reasonable assumption that machines with higher capabilities also run at higher speeds. (It is called the speed hierarchical model in ^[8]). Precisely, for the case of inclusive restriction, they assumed that ${{s}_{1}}\le {{s}_{2}}\le \cdots \le {{s}_{m}}$. For the case of tree-hierarchical restriction, they assumed that the speed of each node is not less than that of its predecessor. Under the assumption, they presented 4/3-approximation algorithms running in time $O(mn\cdot \log (\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}))$ for both cases. They remarked that the algorithms may not work if the assumption is not valid. For clarity, we denote their problems as $Q(Inc)|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $Q(Inc)|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$, respectively, where "Inc" means "increasing order of the speeds".

In this paper, we generalize the results in ^[7] by eliminating the speed hierarchical assumption. We present fast algorithms with approximation ratios 2 and 4/3 for both $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$.

Scheduling with restricted assignment has been extensively studied in the literature ^[6]. Here, we review the results which are related to inclusive or tree-hierarchical restrictions. Ou et al. ^[9] gave a PTAS (polynomial time approximation scheme) for $P|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ (the special case of $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ where all ${{s}_{i}} = 1$). Li and Wang ^[10] extended their work to include job release times (any job cannot be scheduled before its release time). There are also fast approximation algorithms for this problem: a $(2-1/(m-1))$ -approximation algorithm ^[11,12], a 3/2-approximation algorithm ^[13], and a 4/3-approximation algorithm ^[9]. Bar-Noy et al. ^[14] presented an online (over list) algorithm for $P|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ whose competitive ratio is $e+1$. They also gave an online algorithm for $P|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$ (the special case of $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$ where all ${{s}_{i}} = 1$) whose competitive ratio is 5. Huo and Leung ^[15] gave a 4/3-approximation algorithm for $P|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. Later, Epstein and Levin ^[8] presented PTASs for $P|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$ and $Q(Inc)|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$. However, the running times of their PTASs are rather high. Leung and Ng ^[7] presented fast 4/3-approximation algorithms for $Q(Inc)|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $Q(Inc)|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. There are also several papers which studied the problems of scheduling jobs with equal lengths and restricted assignment on uniform machines ^{[16,17,18,19,20]}.

The rest of the paper is organized as follows. In Section 2, we present 2-approximation algorithms for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. In Section 3, we present 4/3-approximation algorithms for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. In Section 4, we conclude this paper and discuss future research directions.

2.   2-approximation algorithms

In this section we will get a 2-approximation algorithm for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and then extend it to solve $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. Note that Leung and Ng ^[7] only presented algorithms for $Q(Inc)|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $Q(Inc)|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$.

For solving $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$, we set up some notations. Let ${{\mathcal{J}}_{i}}$ denote the set of the jobs whose processing set is $\{{{M}_{i}}, {{M}_{i+1}}, \ldots, {{M}_{m}}\}$, $i = 1, 2, \ldots, m$. The jobs in ${{\mathcal{J}}_{i}}$ are eligible for machines ${{M}_{i}}, {{M}_{i+1}}, \ldots, {{M}_{m}}$, and vice versa. It is possible that ${{\mathcal{J}}_{i}} = \varnothing$ for some $i$. We have: $\bigcup _{i = 1}^{m}{{\mathcal{J}}_{i}} = \mathcal{J}$. Sort all the jobs in ${{\mathcal{J}}_{i}}$ in non-increasing order of their lengths, and let ${{J}_{i}}$ denote the obtained ordered set, $i = 1, 2, \ldots, m$.

Let $OPT$ denote the makespan of an optimal schedule for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$. Let $A{{L}_{i}} = \frac{\sum\nolimits_{j\in {{\mathcal{J}}_{i}}\cup {{\mathcal{J}}_{i+1}}\cup \cdots \cup {{\mathcal{J}}_{m}}}{{{p}_{j}}}}{\sum\nolimits_{l = i}^{m}{{{s}_{l}}}}$ denote the average load on machines ${{M}_{i}}, {{M}_{i+1}}, \ldots, {{M}_{m}}$, $i = 1, 2, \ldots, m$. Let $LB = {{\max }_{i}}A{{L}_{i}}$, where "$LB$" means "lower bound". Since all jobs in ${{\mathcal{J}}_{i}}\cup {{\mathcal{J}}_{i+1}}\cup \cdots \cup {{\mathcal{J}}_{m}}$ must be processed on machines ${{M}_{i}}, {{M}_{i+1}}, \ldots, {{M}_{m}}$ ($i = 1, 2, \ldots, m$) in any feasible schedule, we get: $LB\le OPT$. On the other hand, let $UB = \frac{\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}}{{{s}_{m}}}$, where "$UB$" means "upper bound". Since a feasible schedule can be obtained easily by scheduling all the jobs on machine ${{M}_{m}}$, we get $OPT\le UB$.

To determine $OPT$, we do a binary search in time interval $[LB, UB]$. For each value $C$ selected, the following procedure, AssignA1, tells us whether it is possible to assign the jobs in $\mathcal{J}$ to the machines in $\mathcal{M}$ such that the total length of the jobs assigned to machine ${{M}_{i}}$ is no more than $2{{s}_{i}}\cdot C$, $i = 1, 2, \ldots, m$. If AssignA1 fails, we search the upper half of the interval; otherwise, we search the lower half.

If job $j$ is eligible for machine ${{M}_{i}}$ and ${{p}_{j}}\le {{s}_{i}}\cdot C$, then job $j$ is feasible for machine ${{M}_{i}}$, and vice versa. In AssignA1, ${{U}_{i}}$ represents the set of unassigned jobs which are eligible for machine ${{M}_{i}}$ and sorted in non-increasing order of their lengths, and ${{L}_{i}}$ denotes the total length of the jobs assigned to machine ${{M}_{i}}$, $i = 1, 2, \ldots, m$. Informally speaking, AssignA1 tries to put as many as possible of the largest, not yet assigned feasible jobs on the smaller-indexed machines such that each machine completes no later than $2C$.

AssignA1 ($C$):

Step 1. Let ${{U}_{0}} = \varnothing$, ${{L}_{i}} = 0$, $i = 1, 2, \ldots, m$.

Step 2. For $i = 1, 2, \ldots, m$ (this ordering is used crucially), do:

(i) Merge ${{U}_{i-1}}$ into ${{J}_{i}}$ to get ${{U}_{i}}$. (${{U}_{i-1}}$ and ${{J}_{i}}$ are ordered sets, and thus ${{U}_{i}}$ is also an ordered set.)

(ii) Find the first job $j\in {{U}_{i}}$ such that ${{p}_{j}}\le {{s}_{i}}\cdot C$. Assign job $j$ and the jobs after it in ${{U}_{i}}$ to machine ${{M}_{i}}$ until ${{L}_{i}} > {{s}_{i}}\cdot C$ or the jobs after $j$ in ${{U}_{i}}$ are used up (i.e., each unassigned job in ${{U}_{i}}$ has length larger than ${{s}_{i}}\cdot C$). Delete the newly assigned jobs from ${{U}_{i}}$.

Lemma 2.1. If $OPT\le C$, then AssignA1 will generate a feasible schedule for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ with makespan at most $2C$ in $O(mn)$ time.

Proof. Let ${{\Pi }^{\rm{*}}}$ be an optimal schedule. Let $\Pi$ be the schedule generated by AssignA1. Since $OPT\le C$, any job of length larger than ${{s}_{i}}\cdot C$ cannot be assigned on machine ${{M}_{i}}$ in ${{\Pi }^{\rm{*}}}$, $i = 1, 2, \ldots, m$. Therefore, in $\Pi$, we let ${{M}_{i}}$ process only the jobs whose lengths are no more than ${{s}_{i}}\cdot C$. We have ${{L}_{i}}\le 2{{s}_{i}}\cdot C$, and thus ${{C}_{i}}\le 2C$, where ${{C}_{i}}$ denotes the completion time of machine ${{M}_{i}}$ in $\Pi$, $i = 1, 2, \ldots, m$.

We prove the following claim by contradiction: If $OPT\le C$, then ${{U}_{m}} = \varnothing$ when AssignA1 terminates. Suppose that when AssignA1 terminates, some job $j$ cannot be assigned and has to be left over. Let ${{a}_{j}} = i$ denote the machine index associated with job $j$. Let $F{{M}_{j}}\subseteq \{{{M}_{i}}, {{M}_{i+1}}, \ldots, {{M}_{m}}\}$ denote the set of the feasible machines for job $j$, i.e., for any machine ${{M}_{l}}\in F{{M}_{j}}$, ${{p}_{j}}\le {{s}_{l}}\cdot C$. It must be true that ${{L}_{l}} > {{s}_{l}}\cdot C$ for any machine ${{M}_{l}}\in F{{M}_{j}}$. Let $D$ denote the set of the jobs processed on the machines in $F{{M}_{j}}$. In $\Pi$, all the jobs in $D$ have lengths not less than ${{p}_{j}}$ and hence cannot be assigned to the machines in $\{{{M}_{i}}, {{M}_{i+1}}, \ldots, {{M}_{m}}\}\backslash F{{M}_{j}}$. We consider the following two different cases:

Case 1. The machine indices associated with the jobs in $D$ are not less than ${{a}_{j}} = i$.

In this case, in any optimal schedule and particularly in ${{\Pi }^{\rm{*}}}$, all the jobs in $D$ have to be processed on the machines in $F{{M}_{j}}$. However, since ${{L}_{l}} > {{s}_{l}}\cdot C$ for any machine ${{M}_{l}}\in F{{M}_{j}}$, ${{\Pi }^{\rm{*}}}$ cannot complete all the jobs in $D$ by time $C\ge OPT$, a contradiction.

Case 2. Some jobs in $D$ have machine indices less than ${{a}_{j}} = i$.

Some jobs in $D$ may be associated with machine indices less than $i$, but they may be not feasible for machines ${{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{i-1}}$, or their feasible machines among ${{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{i-1}}$ have not enough space left to accommodate them when they are assigned. Since AssignA1 assigns the largest feasible jobs on the smaller-indexed machines greedily such that each machine completes later than $C$ whenever possible (i.e., unless there is no unassigned feasible job for the machine), an optimal schedule cannot schedule the jobs any better than this on the smaller-indexed machines. Therefore, the total length of the jobs processed on the machines in $F{{M}_{j}}$ in $\Pi$ is a lower bound on the total length of the jobs processed on the machines in $F{{M}_{j}}$ in ${{\Pi }^{\rm{*}}}$. As in Case 1, since ${{L}_{l}} > {{s}_{l}}\cdot C$ for any machine ${{M}_{l}}\in F{{M}_{j}}$, ${{\Pi }^{\rm{*}}}$ cannot complete all the jobs in $D$ by time $C\ge OPT$, a contradiction.

Step 1 can be executed in $O(m)$ time. Step 2 will be executed $m$ iterations, and each iteration can be done in $O(n)$ time. Hence, the running time of AssignA1 is $O(mn)$.

To obtain a faster algorithm, we can use the following AssignA2 procedure instead of AssignA1. AssignA2 handles the machines in increasing order of their indices. When ${{M}_{i}}$ is handled, the unassigned jobs eligible for ${{M}_{i}}$ are stored in a balanced binary search tree $T$ ^[21], using their lengths as the keys. The technique is similar to that used in ^[20].

AssignA2 ($C$):

Step 1. Let $T$ be a balanced binary search tree and $\tau$ be the length of the smallest job in $T$. Initially, $T$ is empty, and $\tau = \infty$. Let ${{L}_{i}}$ denote the total length of the jobs assigned to machine ${{M}_{i}}$. Initially, ${{L}_{i}} = 0$, $i = 1, 2, \ldots, m$.

Step 2. For $i = 1, 2, \ldots, m$ (this ordering is used crucially), do:

(i). Insert the jobs in ${{\mathcal{J}}_{i}}$ into $T$. Update $\tau$ accordingly.

(ii) If ${{L}_{i}}\le {{s}_{i}}\cdot C$ and $\tau \le {{s}_{i}}\cdot C$, then find the largest job $j$ in $T$ such that ${{p}_{j}}\le {{s}_{i}}\cdot C$. Assign job $j$ on machine ${{M}_{i}}$ and then delete it from $T$. Let ${{L}_{i}} = {{L}_{i}}+{{p}_{j}}$. If ${{p}_{j}} = \tau$, then check $\tau$ and update it if necessary.

(iii) Repeat Step 2(ii) until ${{L}_{i}} > {{s}_{i}}\cdot C$ or $\tau > {{s}_{i}}\cdot C$ (the latter case indicates that each job in $T$ has length larger than ${{s}_{i}}\cdot C$).

Lemma 2.2. If $OPT\le C$, then AssignA2 will generate a feasible schedule for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ with makespan at most $2C$ in $O(m+n\log n)$ time.

Proof. The correctness of AssignA2 follows that of AssignA1, and its proof is omitted. Step 1 can be executed in $O(m)$ time. In Step 2, each job will be inserted into and deleted from $T$ at most once. Inserting or deleting a job can be done in $O(\log n)$ time. Thus, it takes $O(n\log n)$ time to construct and maintain $T$ and $\tau$. In Step 2(ii), it takes $O(\log n)$ time to find the largest job $j$ in $T$ such that ${{p}_{j}}\le {{s}_{i}}\cdot C$. Hence, the running time of AssignA2 is $O(m+n\log n)$.

AssignA1 or AssignA2 will be called at most $\log UB$ times in the binary search. Since $UB = \frac{\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}}{{{s}_{m}}}\le \sum\nolimits_{j = 1}^{n}{{{p}_{j}}}$ (we assumed that all ${{s}_{i}}\ge 1$), we get the following:

Theorem 2.3. There is a 2-approximation algorithm for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ that runs in $O(min\{mn, m+n\log n\}\cdot \log (\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}))$ time.

Next, we extend the algorithm to solve $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. For the rooted tree $RT$ whose nodes are the $m$ machines, we define the depths of the nodes as follows. If the node is the root, then its depth is zero; otherwise, its depth is equal to the depth of its parent plus 1. Index the nodes (machines) of the tree in non-increasing order of their depths, ties broken in favor of the leftmost node. The root of the tree is ${{M}_{m}}$.

Let ${{\mathcal{J}}_{i}}$ denote the set of the jobs associated with machine ${{M}_{i}}$, $i = 1, 2, \ldots, m$. The jobs in ${{\mathcal{J}}_{i}}$ are eligible for the machines on the path from ${{M}_{i}}$ to the root of the tree, and vice versa. We have: $\bigcup _{i = 1}^{m}{{\mathcal{J}}_{i}} = \mathcal{J}$. Sort all the jobs in ${{\mathcal{J}}_{i}}$ in non-increasing order of their lengths, and let ${{J}_{i}}$ denote the obtained ordered set, $i = 1, 2, \ldots, m$.

Let $OPT$ denote the makespan of an optimal schedule for $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. For machine ${{M}_{i}}$ (which represents a node of $RT$), let ${{I}_{i}}$ denote the set of the indices of the machines on the path from ${{M}_{i}}$ to the root of the tree. Let $A{{L}_{i}} = \frac{\sum\nolimits_{l\in {{I}_{i}}}{\sum\nolimits_{j\in {{\mathcal{J}}_{l}}}{{{p}_{j}}}}}{\sum\nolimits_{l\in {{I}_{i}}}{{{s}_{l}}}}$ denote the average load on the machines whose indices are in ${{I}_{i}}$, $i = 1, 2, \ldots, m$. Let $LB = {{\max }_{i}}A{{L}_{i}}$. We have: $LB\le OPT$. Let $UB = \frac{\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}}{{{s}_{m}}}$. We have: $OPT\le UB$.

To determine $OPT$, we do a binary search in interval $[LB, UB]$. For each value $C$ selected, the following procedure, AssignB, tells us whether it is possible to assign the $n$ jobs to the $m$ machines such that the total length of the jobs assigned to machine ${{M}_{i}}$ is no more than $2{{s}_{i}}\cdot C$, $i = 1, 2, \ldots, m$. If AssignB fails, we search the upper half of the interval; otherwise, we search the lower half.

If job $j$ is eligible for machine ${{M}_{i}}$ and ${{p}_{j}}\le {{s}_{i}}\cdot C$, then job $j$ is feasible for machine ${{M}_{i}}$, and vice versa. In AssignB, ${{U}_{i}}$ represents the set of unassigned jobs which are eligible for machine ${{M}_{i}}$ and sorted in non-increasing order of their lengths, and ${{L}_{i}}$ denotes the total length of the jobs assigned to machine ${{M}_{i}}$, $i = 1, 2, \ldots, m$. Informally speaking, AssignB tries to put as many as possible of the largest, not yet assigned feasible jobs on the deeper machines such that each machine completes no later than $2C$.

AssignB ($C$):

Step 1. Let ${{L}_{i}} = 0$, ${{U}_{i}} = {{J}_{i}}$, $i = 1, 2, \ldots, m$. Let $h$ be equal to the maximum depth of the machines in tree $RT$.

Step 2. While ($h > 0$), do:

(i) For each machine ${{M}_{i}}$ whose depth is $h$, do:

Find the first job $j\in {{U}_{i}}$ such that ${{p}_{j}}\le {{s}_{i}}\cdot C$. Assign job $j$ and the jobs after it in ${{U}_{i}}$ to machine ${{M}_{i}}$ until ${{L}_{i}} > {{s}_{i}}\cdot C$ or the jobs after $j$ in ${{U}_{i}}$ are used up. Delete the newly assigned jobs from ${{U}_{i}}$. Merge ${{U}_{i}}$ into ${{U}_{k}}$, where ${{M}_{k}}$ is the parent of ${{M}_{i}}$. (${{U}_{i}}$ and ${{U}_{k}}$ are ordered sets before merging, and thus after merging ${{U}_{k}}$ is still an ordered set.)

(ii) Let $h = h-1$.

Step 3. If the total length of the jobs in ${{U}_{m}}$ is no more than $2{{s}_{m}}\cdot C$, then process all the jobs in ${{U}_{m}}$ on machine ${{M}_{m}}$ (whose depth is zero), and the procedure succeeds and terminates. Otherwise, the procedure fails and terminates.

Lemma 2.4. If $OPT\le C$, then AssignB will generate a feasible schedule for $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$ with makespan at most $2C$ in $O(mn)$ time.

Proof. Let ${{\Pi }^{\rm{*}}}$ and $\Pi$ denote an optimal schedule and the schedule generated by AssignB, respectively. Since $OPT\le C$, in ${{\Pi }^{\rm{*}}}$, machine ${{M}_{i}}$ cannot process any job of length larger than ${{s}_{i}}\cdot C$. Hence, in $\Pi$, we let ${{M}_{i}}$ process only the jobs whose lengths are no more than ${{s}_{i}}\cdot C$. We have ${{L}_{i}}\le 2{{s}_{i}}\cdot C$, and thus ${{C}_{i}}\le 2C$, $i = 1, 2, \ldots, m$.

If $OPT\le C$, when AssignB terminates, it must be true that ${{U}_{m}} = \varnothing$. We prove this claim by contradiction. Suppose that some job $j$ cannot be assigned when AssignB terminates. Let $j$ be associated with the tree node ${{M}_{{{a}_{j}}}}$, such that its processing set ${{\mathcal{M}}_{j}}$ consists of the machines on the path from ${{M}_{{{a}_{j}}}}$ to the root of the tree. Let $F{{M}_{j}}\subseteq {{\mathcal{M}}_{j}}$ denote the set of the feasible machines for job $j$, i.e., for any machine ${{M}_{l}}\in F{{M}_{j}}$, ${{p}_{j}}\le {{s}_{l}}\cdot C$. We have ${{L}_{l}} > {{s}_{l}}\cdot C$ for any machine ${{M}_{l}}\in F{{M}_{j}}$. Let $D$ denote the set of the jobs processed on the machines in $F{{M}_{j}}$ in $\Pi$. All the jobs in $D$ have lengths at least ${{p}_{j}}$ and hence cannot be assigned to the machines in ${{\mathcal{M}}_{j}}\backslash F{{M}_{j}}$. We consider the following two different cases:

Case 1. There are no eligible machines outside ${{\mathcal{M}}_{j}}$ for the jobs in $D$.

In this case, all the jobs in $D$ have to be processed on the machines in $F{{M}_{j}}$ in any optimal schedule. However, since ${{L}_{l}} > {{s}_{l}}\cdot C$ for any machine ${{M}_{l}}\in F{{M}_{j}}$, ${{\Pi }^{\rm{*}}}$ cannot complete all the jobs in $D$ by time $C\ge OPT$, a contradiction.

Case 2. Some jobs in $D$ have eligible machines in $\mathcal{M}\backslash {{\mathcal{M}}_{j}}$.

Some jobs in $D$ may have eligible machines in $\mathcal{M}\backslash {{\mathcal{M}}_{j}}$, but they may be not feasible for these machines, or their feasible machines in $\mathcal{M}\backslash {{\mathcal{M}}_{j}}$ have not enough space left to accommodate them when they are assigned. Since AssignB assigns the largest feasible jobs on the machines in $\mathcal{M}\backslash {{\mathcal{M}}_{j}}$ greedily such that each machine completes later than $C$ whenever possible, an optimal schedule cannot schedule the jobs any better than this on the machines in $\mathcal{M}\backslash {{\mathcal{M}}_{j}}$. Therefore, the total length of the jobs processed on the machines in $F{{M}_{j}}$ in $\Pi$ is a lower bound on the total length of the jobs processed on the machines in $F{{M}_{j}}$ in ${{\Pi }^{\rm{*}}}$. As in Case 1, since ${{L}_{l}} > {{s}_{l}}\cdot C$ for any machine ${{M}_{l}}\in F{{M}_{j}}$, ${{\Pi }^{\rm{*}}}$ cannot complete all the jobs in $D$ by time $C\ge OPT$, a contradiction.

We use the binary search together with AssignB to solve $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. Then, we get the following:

Theorem 2.5. There is a 2-approximation algorithm for $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$ that runs in $O(mn\cdot \log (\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}))$ time.

3.   4/3-approximation algorithms

In this section we will get a 4/3-approximation algorithm for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$, and then extend it to solve $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. We continue to use the notations introduced in the previous section.

Let $OPT$ denote the makespan of an optimal schedule for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$. We perform a binary search in $[LB, UB]$ to determine $OPT$, where $LB = {{\max }_{i}}A{{L}_{i}}$, $A{{L}_{i}} = \frac{\sum\nolimits_{j\in {{\mathcal{J}}_{i}}\cup {{\mathcal{J}}_{i+1}}\cup \cdots \cup {{\mathcal{J}}_{m}}}{{{p}_{j}}}}{\sum\nolimits_{l = i}^{m}{{{s}_{l}}}}$, and $UB = \frac{\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}}{{{s}_{m}}}$. For each value $C$ selected, we use the following procedure, AssignC1, to test whether it is possible to schedule the jobs such that the total length of the jobs processed on machine ${{M}_{i}}$ is no more than $4{{s}_{i}}\cdot C/3$, $i = 1, 2, \ldots, m$.

If job $j$ is eligible for machine ${{M}_{i}}$ and ${{p}_{j}}\le {{s}_{i}}\cdot C$, then job $j$ is feasible for machine ${{M}_{i}}$, and vice versa.

For each value $C$ selected, we classify feasible jobs as long, median, and short with respect to the machine speeds. For a particular machine ${{M}_{i}}$ ($i = 1, 2, \ldots, m$), job $j$ is long if $2{{s}_{i}}\cdot C/3 < {{p}_{j}}\le {{s}_{i}}\cdot C$, or median if ${{s}_{i}}\cdot C/3 < {{p}_{j}}\le 2{{s}_{i}}\cdot C/3$, or short if ${{p}_{j}}\le {{s}_{i}}\cdot C/3$.

In AssignC1, ${{U}_{i}}$ represents the set of unassigned jobs which are eligible for machine ${{M}_{i}}$ and sorted in non-increasing order of their lengths, $i = 1, 2, \ldots, m$. In Step 2(ii) of AssignC1, we first compare the total length of the two largest median jobs in ${{U}_{i}}$ with the length of the largest long job in ${{U}_{i}}$. If the former is larger, then we schedule the two largest median jobs in ${{U}_{i}}$ on machine ${{M}_{i}}$. Otherwise, we schedule the largest long job in ${{U}_{i}}$ on machine ${{M}_{i}}$.

AssignC1 ($C$):

Step 1. Let ${{U}_{0}} = \varnothing$ and $i = 1$.

Step 2. While $i\le m$, do:

(i) Merge ${{U}_{i-1}}$ into ${{J}_{i}}$ to get ${{U}_{i}}$.

(ii) If there is no long job in ${{U}_{i}}$, then add a "dummy'' long job of length zero into ${{U}_{i}}$. Similarly, if there is no median job (or only one median job) in ${{U}_{i}}$, then add two (or one) "dummy'' median job(s) of length zero into ${{U}_{i}}$. Let ${{j}_{1}}$, ${{j}_{2}}$ and ${{j}_{3}}$ denote the largest long job and the two largest median jobs in ${{U}_{i}}$, respectively. If ${{p}_{{{j}_{2}}}}+{{p}_{{{j}_{3}}}} > {{p}_{{{j}_{1}}}}$, then let ${{j}_{2}}$ and ${{j}_{3}}$ be processed on ${{M}_{i}}$ and remove them from ${{U}_{i}}$; else, let ${{j}_{1}}$ be processed on ${{M}_{i}}$ and remove it from ${{U}_{i}}$.

(iii) If the total length of the jobs on ${{M}_{i}}$ is less than or equal to ${{s}_{i}}\cdot C$, then we repeatedly assign the largest unassigned short jobs in ${{U}_{i}}$ to ${{M}_{i}}$ until the first time that the total length of the jobs on ${{M}_{i}}$ is larger than ${{s}_{i}}\cdot C$. Remove the newly assigned jobs from ${{U}_{i}}$.

(iv) Let $i = i+1$.

Lemma 3.1. If $OPT\le C$, then AssignC1 will generate a feasible schedule for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ with makespan at most $4C/3$ in $O(mn)$ time.

Proof. Let ${{\Pi }^{\rm{*}}}$ be an optimal schedule. Let $\Pi$ be the schedule generated by AssignC1. We will prove the lemma by modifying ${{\Pi }^{\rm{*}}}$ into $\Pi$.

To do so, we handle the machines in increasing order of their indices. Suppose that machines ${{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{i-1}}$ have been handled. We illustrate how to handle machine ${{M}_{i}}$. At this point, the jobs on machines ${{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{i-1}}$ in ${{\Pi }^{\rm{*}}}$ (after machines ${{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{i-1}}$ have been handled) are processed in the same manner as they are processed on machines ${{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{i-1}}$ in $\Pi$. We treat these jobs as assigned jobs. All the other jobs are treated as unassigned jobs. The unassigned jobs which are eligible for machine ${{M}_{i}}$ form the set ${{U}_{i}}$.

As described in Step 2(ii) of AssignC1, if ${{p}_{{{j}_{2}}}}+{{p}_{{{j}_{3}}}} > {{p}_{{{j}_{1}}}}$, then we let ${{j}_{2}}$ and ${{j}_{3}}$ be processed on ${{M}_{i}}$ in modified ${{\Pi }^{\rm{*}}}$. To achieve this, if at least one part of ${{j}_{2}}$ is on machine ${{M}_{l}}$ ($l > i$) other than ${{M}_{i}}$, we move this part from ${{M}_{l}}$ to ${{M}_{i}}$, and move a corresponding part of the same length (consisting of parts of the jobs which are on ${{M}_{i}}$ in ${{\Pi }^{\rm{*}}}$ but not on ${{M}_{i}}$ in $\Pi$, cutting some job if necessary) from ${{M}_{i}}$ to ${{M}_{l}}$. If the total length of the jobs which are on ${{M}_{i}}$ in ${{\Pi }^{\rm{*}}}$ but not on ${{M}_{i}}$ in $\Pi$ is less than the length of this part of ${{j}_{2}}$, then we exchange this part of ${{j}_{2}}$ and all the jobs which are on ${{M}_{i}}$ in ${{\Pi }^{\rm{*}}}$ but not on ${{M}_{i}}$ in $\Pi$. Repeat this process until the entire ${{j}_{2}}$ appears on ${{M}_{i}}$ in modified ${{\Pi }^{\rm{*}}}$. Perform a similar exchange process until the entire ${{j}_{3}}$ appears on ${{M}_{i}}$ in modified ${{\Pi }^{\rm{*}}}$. Note that ${{p}_{{{j}_{2}}}}+{{p}_{{{j}_{3}}}}\le 4{{s}_{i}}\cdot C/3$. If ${{p}_{{{j}_{2}}}}+{{p}_{{{j}_{3}}}}\le {{p}_{{{j}_{1}}}}$, then we let ${{j}_{1}}$ be processed on ${{M}_{i}}$ in modified ${{\Pi }^{\rm{*}}}$, by performing a similar exchange process. Note that ${{p}_{{{j}_{1}}}}\le {{s}_{i}}\cdot C$.

Next, we assign some short jobs in ${{U}_{i}}$ on machine ${{M}_{i}}$ as described in Step 2(iii) of AssignC1, by performing a similar exchange process. When we finish handling of ${{M}_{i}}$, the jobs processed on ${{M}_{i}}$ in modified ${{\Pi }^{\rm{*}}}$ are those processed on ${{M}_{i}}$ in $\Pi$. Moreover, the total length of the jobs on ${{M}_{i}}$ is no more than $4{{s}_{i}}\cdot C/3$. Hence, ${{M}_{i}}$ completes no later than $4C/3$.

Although some jobs have to be cut during the modification, when we finish handling of ${{M}_{m}}$, no cut job exists in modified ${{\Pi }^{\rm{*}}}$ (i.e., $\Pi$). It is easy to check that the total length of the jobs processed on machines ${{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{i}}$ in $\Pi$ is an upper bound on the total length of the jobs processed on machines ${{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{i}}$ in unmodified ${{\Pi }^{\rm{*}}}$, $i = 1, 2, \ldots, m$.

We can give an alternative implementation of AssignC1, called AssignC2, which runs in $O((m+n)\log n)$ time. The idea is to store the jobs in ${{U}_{i}}$ in a balanced binary search tree $T$, using their lengths as the keys. Before we perform Step 2(ii) of AssignC1, we do the following. First, find the largest job of length no more than ${{s}_{i}}\cdot C$ in $T$. If the job does not exist, then let $i = i+1$ and move on to the next iteration. If the job is a long job, then let it be ${{j}_{1}}$. Otherwise, let ${{j}_{1}}$ denote a "dummy" long job of length zero. Next, find the largest job of length no more than $2{{s}_{i}}\cdot C/3$ in $T$. If the job does not exist or is a short job, then let ${{j}_{2}}$ and ${{j}_{3}}$ denote two "dummy" median jobs of length zero. Otherwise (i.e., the job is a median job), let it be ${{j}_{2}}$, and continue to find another largest job of length no more than this job in $T$. If the job does not exist or is a short job, then let ${{j}_{3}}$ denote a "dummy" median job of length zero. Otherwise, let it be ${{j}_{3}}$. After ${{j}_{1}}$, ${{j}_{2}}$ and ${{j}_{3}}$ are determined, we perform Step 2(ii) of AssignC1. To perform Step 2(iii) of AssignC1, we need to find the currently largest job of length no more than ${{s}_{i}}\cdot C/3$ (i.e., the largest short job) in $T$. Note that each job will be inserted into $T$ or deleted from $T$ at most once. The balanced binary search tree $T$ can be constructed and maintained in $O(n\log n)$ time. Moreover, determining ${{j}_{1}}$, ${{j}_{2}}$ and ${{j}_{3}}$ for each machine can be done in $O(\log n)$ time. Determining the currently largest short job in $T$ can also be done in $O(\log n)$ time. Therefore, the overall running time of AssignC2 is $O((m+n)\log n)$.

Lemma 3.2. If $OPT\le C$, then AssignC2 will generate a feasible schedule for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ with makespan at most $4C/3$ in $O((m+n)\log n)$ time.

Theorem 3.3. There is a 4/3-approximation algorithm for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ that runs in $O(min\{mn, (m+n)\log n\}\cdot \log (\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}))$ time.

Next, we extend the algorithm to solve $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. Given the rooted tree $RT$ whose nodes are the $m$ machines, we index the nodes of $RT$ in non-increasing order of their depths, ties broken in favor of the leftmost node. The root of $RT$ is ${{M}_{m}}$.

Let $OPT$ denote the optimal makespan for $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$. For machine ${{M}_{i}}$ (which represents a node of $RT$), let ${{I}_{i}}$ denote the set of the indices of the machines on the path from ${{M}_{i}}$ to the root of the tree. Let $A{{L}_{i}} = \frac{\sum\nolimits_{l\in {{I}_{i}}}{\sum\nolimits_{j\in {{\mathcal{J}}_{l}}}{{{p}_{j}}}}}{\sum\nolimits_{l\in {{I}_{i}}}{{{s}_{l}}}}$ denote the average load on the machines whose indices are in ${{I}_{i}}$, $i = 1, 2, \ldots, m$. Let $LB = {{\max }_{i}}A{{L}_{i}}$. We have: $LB\le OPT$. Let $UB = \frac{\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}}{{{s}_{m}}}$. We have: $OPT\le UB$.

We perform a binary search in $[LB, UB]$ to determine $OPT$. For each value $C$ selected, we use the following procedure, AssignD, to test whether it is possible to schedule the jobs such that the total length of the jobs processed on machine ${{M}_{i}}$ is no more than $4{{s}_{i}}\cdot C/3$, $i = 1, 2, \ldots, m$. We continue to use the related definitions for $Q|{{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$, such as feasible, long, median and short jobs.

In AssignD, ${{U}_{i}}$ represents the set of unassigned jobs which are eligible for machine ${{M}_{i}}$ and sorted in non-increasing order of their lengths, $i = 1, 2, \ldots, m$. In Step 2(i)(1) of AssignD, we first compare the total length of the two largest median jobs in ${{U}_{i}}$ with the length of the largest long job in ${{U}_{i}}$. If the former is larger, then we schedule the two largest median jobs in ${{U}_{i}}$ on machine ${{M}_{i}}$. Otherwise, we schedule the largest long job in ${{U}_{i}}$ on machine ${{M}_{i}}$, $i = 1, 2, \ldots, m$.

AssignD ($C$):

Step 1. Let ${{U}_{i}} = {{J}_{i}}$, $i = 1, 2, \ldots, m$. Let $h$ be equal to the maximum depth of the machines in tree $RT$.

Step 2. While ($h > 0$), do:

(i) For each machine ${{M}_{i}}$ whose depth is $h$, do:

(1) If there is no long job in ${{U}_{i}}$, then add a "dummy'' long job of length zero into ${{U}_{i}}$. Similarly, if there is no median job (or only one median job) in ${{U}_{i}}$, then add two (or one) "dummy'' median job(s) of length zero into ${{U}_{i}}$. Let ${{j}_{1}}$, ${{j}_{2}}$ and ${{j}_{3}}$ denote the largest long job and the two largest median jobs in ${{U}_{i}}$, respectively. If ${{p}_{{{j}_{2}}}}+{{p}_{{{j}_{3}}}} > {{p}_{{{j}_{1}}}}$, then let ${{j}_{2}}$ and ${{j}_{3}}$ be processed on ${{M}_{i}}$ and remove them from ${{U}_{i}}$; else, let ${{j}_{1}}$ be processed on ${{M}_{i}}$ and remove it from ${{U}_{i}}$.

(2) If the total length of the jobs on ${{M}_{i}}$ is less than or equal to ${{s}_{i}}\cdot C$, then we repeatedly assign the largest unassigned short jobs in ${{U}_{i}}$ to ${{M}_{i}}$ until the first time that the total length of the jobs on ${{M}_{i}}$ is larger than ${{s}_{i}}\cdot C$. Remove the newly assigned jobs from ${{U}_{i}}$.

(3) Merge ${{U}_{i}}$ into ${{U}_{k}}$, where ${{M}_{k}}$ is the parent of ${{M}_{i}}$.

(ii) Let $h = h-1$.

Step 3. If the total length of the jobs in ${{U}_{m}}$ is no more than $4{{s}_{m}}\cdot C/3$, then process all the jobs in ${{U}_{m}}$ on machine ${{M}_{m}}$, and the procedure succeeds and terminates. Otherwise, the procedure fails and terminates.

Similarly to the proof of Lemma 3.1, we can prove the following lemma.

Lemma 3.4. If $OPT\le C$, then AssignD will generate a feasible schedule for $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$ with makespan at most $4C/3$ in $O(mn)$ time.

Theorem 3.5. There is a 4/3-approximation algorithm for $Q|{{\mathcal{M}}_{j}}(tree)|{{C}_{\max }}$ that runs in $O(mn\cdot \log (\sum\nolimits_{j = 1}^{n}{{{p}_{j}}}))$ time.

4.   Conclusions

In this paper we investigated the problem of minimizing makespan on uniform machines with restricted assignment. We presented algorithms with approximation ratios 2 and 4/3 for the cases of inclusive and tree-hierarchical restrictions. Since the algorithms do not rely on the speed hierarchical assumption, they generalize the results presented in ^[7]. The running times of the algorithms contain a factor of $\log (\sum\nolimits_{j = 1}^{n}{{{p}_{j}}})$, and in consequence they are not strongly polynomial time. To get strongly polynomial time algorithms, we use the technique described in ^[9] to modify the above algorithms slightly. The approximation ratios then become $2+\varepsilon$ and $4/3+\varepsilon$, where $\varepsilon > 0$ can be made arbitrarily small. In addition, as pointed out in ^[7], since the algorithms are based on the binary search, they produce schedules with makespans $\rm{2}\left\lceil OPT \right\rceil$ or $4\left\lceil OPT \right\rceil /3$, where $OPT$ denotes the optimal makespan.

It would be interesting to study the problem of minimizing makespan on uniform machines with other objective functions, or with other special types of assignment restrictions, such as nested, or interval restrictions. For further research, some learning strategies may be introduced, such as Probably Approximately Correct (PAC) learning with importance reweighting ^[22], dynamic feature weight selection ^[23], robust learning, granular-ball learning ^[24] or Complete Random Forest (CRF) based class noise filtering learning ^[25].

Acknowledgments

We thank the editor and reviewers for their helpful suggestions. This work is supported by the Natural Science Foundation of Shandong Province, China (No. ZR2020MA030).

Conflict of interest

The authors declare there is no conflict of interest.