Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines

1.   Introduction

The problem of scheduling uniform parallel batch machines with processing set restrictions can be defined as follows. Let $\mathcal{J} = \{1, 2, \ldots, n\}$ be a set of jobs and $\mathcal{M} = \{{{M}_{1}}, {{M}_{2}}, \ldots, {{M}_{m}}\}$ be a set of uniform parallel batch machines. Job $j$ ($j = 1, 2, \ldots, n$) becomes available at its release time ${{r}_{j}}\ge 0$ and requires ${{p}_{j}}\ge 0$ units of processing called its length. For each job $j$, let ${{\mathcal{M}}_{j}}\subseteq \mathcal{M}$ be the set of the eligible machines which are capable of processing the job, called its processing set. Each job will be assigned to exactly one machine and job preemption is not allowed. Machine ${{M}_{i}}$ ($i = 1, 2, \ldots, m$) has a speed ${{v}_{i}}\ge 1$ and a capacity ${{K}_{i}} < n$. The impact of the speed is that ${{M}_{i}}$ can carry out ${{v}_{i}}$ units of processing in one time unit. That is, if job $j$ is assigned to machine ${{M}_{i}}$, then it requires ${{p}_{j}}/{{v}_{i}}$ processing time to be completed. Machine ${{M}_{i}}$ can process several jobs as a batch simultaneously as long as the total number of these jobs does not exceed ${{K}_{i}}$. The length of a batch is the maximum of the lengths of the jobs belonging to it. Jobs in the same batch have a common start time and a common completion time. The goal is to schedule the jobs on the machines in a manner that optimizes one or more objective functions.

Two classes of objectives are considered: the min-sum objective and the min-max objective. Specifically, let ${{f}_{j}}:[0, +\infty)\to [0, +\infty)$ ($j = 1, 2, \ldots, n$) be a non-decreasing function. Additional parameters that may be included for job $j$ are its due date ${{d}_{j}}$ and its weight ${{w}_{j}}$. For a particular schedule $\sigma$, let ${{C}_{j}}(\sigma)$ denote the completion time of job $j$ in $\sigma$. Let ${{T}_{j}}(\sigma) = \max \{{{C}_{j}}(\sigma)-{{d}_{j}}, 0\}$ denote the tardiness of job $j$ in $\sigma$. Let ${{U}_{j}}(\sigma) = 1$ if ${{C}_{j}}(\sigma) > {{d}_{j}}$ and ${{U}_{j}}(\sigma) = 0$ otherwise. (In the rest of this paper, we safely ignore $\sigma$ in the notations without causing confusion.) The objectives of minimizing $\sum\nolimits_{j = 1}^{n}{{{f}_{j}}}({{T}_{j}})$ and ${{\max }_{j = 1, 2, \ldots, n}}\{{{f}_{j}}({{T}_{j}})\}$ will be considered. Following ^[1,2], the models can be denoted as $Q|{{r}_{j}}, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\sum{{{f}_{j}}({{T}_{j}})}$ and $Q|{{r}_{j}}, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\max \{{{f}_{j}}({{T}_{j}})\}$.

Many popular scheduling objectives are covered by the two models, such as total weighted completion time ($\sum{{{w}_{j}}{{C}_{j}}}$) minimization, total weighted tardiness ($\sum{{{w}_{j}}{{T}_{j}}}$) minimization, weighted number of tardy jobs ($\sum{{{w}_{j}}{{U}_{j}}}$) minimization, makespan (${{C}_{\max }} = \max {{C}_{j}}$) minimization, and maximum weighted tardiness ($\max \{{{w}_{j}}({{T}_{j}})\}$) minimization. As shown in ^[3,4,5], most of such problems are NP-hard even for the special cases where all ${{v}_{i}} = 1$, all ${{K}_{i}} = 1$ and all ${{\mathcal{M}}_{j}} = \mathcal{M}$. Thus, we are interested in polynomial time exact algorithms for some important special cases of the problems ^[6].

In this paper, we focus on an important special case where all jobs have equal lengths (and equal release times). The problems under study can be denoted as $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\sum{{{f}_{j}}({{T}_{j}})}$ (the special case of $Q|{{r}_{j}}, {{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\sum{{{f}_{j}}({{T}_{j}})}$ where all ${{r}_{j}} = 0$) and $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\max \{{{f}_{j}}({{T}_{j}})\}$ (the special case of $Q|{{r}_{j}}, {{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\max \{{{f}_{j}}({{T}_{j}})\}$ where all ${{r}_{j}} = 0$). Li ^[7] presented polynomial time algorithms for uniform parallel machine scheduling problems $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}|\sum{{{f}_{j}}({{T}_{j}})}$ and $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}|\max \{{{f}_{j}}({{T}_{j}})\}$ (the special cases of $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\sum{{{f}_{j}}({{T}_{j}})}$ and $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\max \{{{f}_{j}}({{T}_{j}})\}$ where all ${{K}_{i}} = 1$). We extend the results obtained in ^[7] to uniform parallel batch machines, allowing the machines to have non-identical capacities. Moreover, for minimizing makespan, we allow unequal release times and get an algorithm for arbitrary processing set restrictions.

Although the above problem setting appears simple, it captures important aspects of a wide range of applications. There are many problems arise as its special or similar cases in networking and information systems. For example, Low ^[8] studied the problem in the context of retrieving data blocks from disks in video on demand systems. Suri et al. ^[9] considered the problem in peer-to-peer systems. The problem was also studied for workload balancing among packet queues ^[10], for data aggregation in wireless sensor networks ^[11]. Recently, Champati and Liang ^[12] studied a very similar problem where each machine has its own convex cost functions, aiming to minimize the sum cost and the maximum differential cost of the machines.

The remainder of this paper is organized as follows. In Section 2, the related researches are reviewed. In Section 3, we consider the case of equal release times. We present an algorithm with running time $O({{n}^{3}}m+{{n}^{2}}m\log (mn))$ for $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\sum{{{f}_{j}}({{T}_{j}})}$, as well as an algorithm with running time $O({{n}^{5/2}}{{m}^{3/2}}\log (mn))$ for $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\max \{{{f}_{j}}({{T}_{j}})\}$. In Section 4, we consider the case of unequal release times. We present an algorithm with running time $O({{n}^{5/2}}{{m}^{3/2}}\log (mn))$ for $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|{{C}_{\max }}$. Section 5 presents the conclusions and future directions of research.

2.   Literature review

Leung and Li ^[13] discussed several special cases of processing set restrictions. The processing sets of the jobs are inclusive, if for any two jobs ${{j}_{1}}$ and${{j}_{2}}$, either ${{\mathcal{M}}_{{{j}_{1}}}}\subseteq {{\mathcal{M}}_{{{j}_{2}}}}$, or ${{\mathcal{M}}_{{{j}_{2}}}}\subseteq {{\mathcal{M}}_{{{j}_{1}}}}$. The processing sets are nested, if for any two jobs ${{j}_{1}}$ and${{j}_{2}}$, either ${{\mathcal{M}}_{{{j}_{1}}}}\cap {{\mathcal{M}}_{{{j}_{2}}}} = \varnothing$, or ${{\mathcal{M}}_{{{j}_{1}}}}\subseteq {{\mathcal{M}}_{{{j}_{2}}}}$, or ${{\mathcal{M}}_{{{j}_{2}}}}\subseteq {{\mathcal{M}}_{{{j}_{1}}}}$. The processing sets are interval, if for any job $j$, ${{\mathcal{M}}_{j}} = \{{{M}_{{{a}_{j}}}}, {{M}_{{{a}_{j}}+1}}, \ldots, {{M}_{{{b}_{j}}}}\}$ for some $1\le {{a}_{j}}\le {{b}_{j}}\le m$. The processing sets are tree-hierarchical, if each machine is represented by a tree node, and each job $j$ is associated with a tree node ${{M}_{{{a}_{j}}}}$, such that ${{\mathcal{M}}_{j}}$ is exactly the set of the machines consisting of all the nodes on the unique path from ${{M}_{{{a}_{j}}}}$ to the root of the tree.

The problem studied in this paper combines two important sub-fields of scheduling theory: scheduling with processing set restrictions and parallel batch scheduling. The two sub-fields have received intense study in the literature, see the survey papers ^[13] and ^[14,15,16] respectively. There are also a few papers which combined the two-subfields into a unified framework ^{[17,18,19,20,21,22,23]}. In the problems studied in these papers except the last two, each job has a size and a machine can process several jobs simultaneously as a batch as long as the total size of these jobs does not exceed its capacity. Any machine cannot process the jobs whose sizes are larger than its capacity. Thus, for each job, the machines whose capacities are not less than its size form its processing set. Clearly, the processing sets of the jobs are inclusive. In ^[22], Li presented two algorithms with approximation ratios 3 and 9/4 for the problem of minimizing makespan on parallel batch machines with inclusive processing set restrictions, where the jobs have arbitrary lengths and the machines have the same speed. In ^[23], Li studied parallel batch scheduling with nested processing set restrictions to minimize makespan, and presented a $(3-1/m)$-approximation algorithm for the case of equal release times and a polynomial time approximation scheme (PTAS) for the case of unequal release times.

For scheduling with processing set restrictions, the review focuses on the case of equal job lengths. Lin and Li ^[24] obtained an algorithm for $P|{{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ (the special case of $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ where all ${{r}_{j}} = 0$ and all ${{v}_{i}} = 1$) that runs in $O({{n}^{3}}\log n)$ time, and generalized the algorithm to solve $Q|{{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ in $O({{n}^{3}}\log(n{{v}_{lcm}}))$ time, where ${{v}_{lcm}}$ denotes the least common multiple of ${{v}_{1}}, {{v}_{2}}, \ldots, {{v}_{m}}$. They also obtained an algorithm for $P|{{p}_{j}} = p, {{\mathcal{M}}_{j}}(interval)|{{C}_{\max }}$ (the special case of $P|{{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ with interval processing set restrictions) that runs in $O({{m}^{2}}+mn)$ time. Harvey et al. ^[25] independently developed an algorithm for $P|{{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ that runs in $O({{n}^{2}}m)$ time. Brucker et al. ^[26] presented algorithms running in $O({{n}^{2}}m(n+\log m))$ time for $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}|\sum{{{w}_{j}}{{T}_{j}}}$, $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}|\sum{{{w}_{j}}{{U}_{j}}}$, $P|{{r}_{j}}, {{p}_{j}} = 1, {{d}_{j}}, {{\mathcal{M}}_{j}}|\sum{{{w}_{j}}{{T}_{j}}}$ and $P|{{r}_{j}}, {{p}_{j}} = 1, {{d}_{j}}, {{\mathcal{M}}_{j}}|\sum{{{w}_{j}}{{U}_{j}}}$. Li ^[7] presented an algorithm for $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}|\sum{{{f}_{j}}({{T}_{j}})}$ that runs in $O({{n}^{3}}m+{{n}^{2}}m\log(mn))$ time. For the special cases where ${{f}_{j}}({{T}_{j}}) = {{C}_{j}}$ or ${{f}_{j}}({{T}_{j}}) = {{U}_{j}}$, the running time of the algorithm can be improved to $O({{n}^{5/2}}m\log n)$. He also presented an algorithm for $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}|\max \{{{f}_{j}}({{T}_{j}})\}$ that runs in $O({{n}^{5/2}}m\log (mn))$ time. For the special cases where ${{f}_{j}}({{T}_{j}}) = {{C}_{j}}$ (i.e., $Q|{{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$), the running time of the algorithm can be improved to $O({{n}^{2}}(m+\log (n{{v}_{\max }}))\log n)$, where ${{v}_{\max }} = \max \{{{v}_{j}}\}$. Lee et al. ^[27] showed that $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ can be solved in $O({{m}^{3/2}}{{n}^{5/2}}\log (mn))$ time, and $P|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$(the special case of $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ where all ${{v}_{i}} = 1$) can be solved in $O({{m}^{3/2}}{{n}^{5/2}}\log n)$ time. Shabtay et al. ^[28] obtained various results for several problems of scheduling uniform machines with equal length jobs, processing set restrictions and job rejection. Hong et al. ^[29] studied $P|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}|\sum{{{C}_{j}}}$. For the problem with a fixed number of machines, they provided a polynomial time dynamic programming algorithm. For the general case, they presented two polynomial time approximation algorithms with approximation ratios $3/5$ and $5/7$ respectively. Jiang et al. ^[30] presented a comprehensive overview (including their new findings) of ideal schedules for various scheduling problems in different machine environments and with different job characteristics. An ideal schedule is a schedule that simultaneously minimizes the total completion time and makespan. They pointed out that in most problems that are known to have an ideal schedule, the jobs have equal processing times. Along with other results, they proved that any optimal schedule for $Q|{{p}_{j}} = p, {{\mathcal{M}}_{j}}|\sum{{{C}_{j}}}$ also minimizes makespan. Jing et al. ^[31] studied the problem of scheduling high multiplicity jobs to minimize makespan on parallel machines with processing set restrictions, setup times and machine available times. High multiplicity means that jobs are partitioned into several groups and in each group all jobs are identical. Whenever there is a switch from processing a job of one group to a job of another group, a setup time is needed. They formulated the problem as a mixed integer programming and proposed a heuristic for it.

Pinedo ^[32] and Glass and Mills ^[33] presented algorithms for $P|{{p}_{j}} = p, {{\mathcal{M}}_{j}}(\text{nested})|{{C}_{\max }}$ (the special case of $P|{{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ with nested processing set restrictions) that run in time $O(n\log n)$ and $O({{m}^{2}})$ time respectively. Li and Li ^[34] presented algorithms for $P|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $P|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}(\text{tree})|{{C}_{\max }}$ (the special cases of $P|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ with inclusive and tree-hierarchical processing set restrictions) that run in $O({{n}^{2}}+mn\log n)$ time. For uniform machines, they showed that $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ and $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}(\text{tree})|{{C}_{\max }}$ can be solved in $O(m{{n}^{2}}\log m)$ time. Later, Li and Lee ^[35] developed an improved algorithm for $P|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}(inclusive)|{{C}_{\max }}$ that runs in $O(min\{m, \log n\}n\log n)$ time, and an improved algorithm for $P|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}(\text{tree})|{{C}_{\max }}$ that runs in $O(mn\log n)$ time.

For parallel batch scheduling, the review focuses on equal job lengths or uniform parallel batch machines. Liu et al. ^[36] presented an algorithm for $P|{{r}_{j}}, {{p}_{j}} = p, p-batch, B|{{C}_{\max }}$ (the special case of $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|{{C}_{\max }}$ where all ${{\mathcal{M}}_{j}} = \mathcal{M}$, all ${{K}_{i}} = B$ and all ${{v}_{i}} = 1$) that runs in $O(n\log n)$ time. Ozturk et al. ^[37] presented a 2-approximation algorithm for the problem of scheduling jobs with equal lengths, unequal release times and sizes on identical parallel batch machines (all ${{K}_{i}} = B$) to minimize makespan. Wang and Leung ^[18] studied the problem of scheduling jobs with equal lengths and arbitrary sizes on parallel batch machines (all ${{v}_{i}} = 1$) with non-identical capacities. The problem fits into the model of scheduling with inclusive processing set restrictions, since each job can only be processed by the machines whose capacities are not less than the size of the job. Wang and Leung ^[18] presented a 2-approximation algorithm, as well as an algorithm with asymptotic approximation ratio 3/2 for the problem. Li et al. ^[38] proposed several heuristics for the problem of scheduling jobs with unequal lengths, release times and sizes on uniform parallel batch machines with identical capacities to minimize makespan. Zhou et al. ^[39] presented an effective discrete differential evolution algorithm for the problem of scheduling jobs with unequal lengths and sizes on uniform parallel batch machines with non-identical capacities to minimize makespan. Both ^[38] and ^[39] have not included processing set restrictions.

3.   Equal release times

In this section, we consider the case of equal release times. We will present algorithms for $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\sum{{{f}_{j}}({{T}_{j}})}$ and $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\max \{{{f}_{j}}({{T}_{j}})\}$.

Since ${{f}_{j}}$ ($j = 1, 2, \ldots, n$) is a non-decreasing function, for both $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\sum{{{f}_{j}}({{T}_{j}})}$ and $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\max \{{{f}_{j}}({{T}_{j}})\}$, there is an optimal schedule in which the first batch on each machine starts at time zero, and the batches on each machine are processed successively. Moreover, we can assume that there are ${{n}_{i}}$ empty batches on machine ${{M}_{i}}$ ($i = 1, 2, \ldots, m$) to which the jobs may be assigned, where ${{n}_{i}}$ denotes the smallest integer such that ${{n}_{i}}{{K}_{i}}\ge n$. The k-th batch on ${{M}_{i}}$, ${{B}_{k, i}}$, completes at time $kp/{{v}_{i}}$, $k = 1, 2, \ldots, {{n}_{i}}$. To find a feasible schedule, we need only to assign the jobs to $\sum\nolimits_{i = 1}^{m}{{{n}_{i}}}$ empty batches such that all jobs obey the processing set restrictions.

First, we consider $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\sum{{{f}_{j}}({{T}_{j}})}$.

If job $j$ is assigned to ${{B}_{k, i}}$ and ${{M}_{i}}\in {{\mathcal{M}}_{j}}$, then the cost incurred is defined to be ${{c}_{jki}} = {{f}_{j}}(\max \{kp/{{v}_{i}}-{{d}_{j}}, 0\})$, $j = 1, 2, \ldots, n$, $k = 1, 2, \ldots, {{n}_{i}}$, $i = 1, 2, \ldots, m$. Let $C = {{\max }_{j, k, i}}{{c}_{jki}}$. By regarding each job $j\in \mathcal{J}$ as a vertex in $X$, and each empty batch ${{B}_{k, i}}$ as ${{K}_{i}}$ vertices ${{y}_{k1}}, {{y}_{k2}}, \ldots, {{y}_{k{{K}_{i}}}}$ in $Y$, we construct a bipartite graph $G$ with bipartition $(X, Y)$, where $j$ is joined to ${{y}_{k1}}, {{y}_{k2}}, \ldots, {{y}_{k{{K}_{i}}}}$ if and only if ${{M}_{i}}\in {{\mathcal{M}}_{j}}$, and the incurred costs are equal to ${{c}_{jki}}$, $j = 1, 2, \ldots, n$, $k = 1, 2, \ldots, {{n}_{i}}$, $i = 1, 2, \ldots, m$. Then we use the Successive Shortest Path algorithm to solve the bipartite weighted matching problem ^[40] and get a matching of minimum cost that saturates every vertex in $X$. From this matching we can construct an optimal schedule easily.

The Successive Shortest Path algorithm runs in $O(\left| X \right|\cdot S(\left| X \right|+\left| Y \right|, \left| X \right|\left| Y \right|, C))$ time, where $S(\left| X \right|+\left| Y \right|, \left| X \right|\left| Y \right|, C)$ is the time for solving a shortest path problem with $\left| X \right|+\left| Y \right|$ vertices, $\left| X \right|\left| Y \right|$ edges (these edges have non-negative costs), and maximum coefficient $C$. Currently, $S(u, a, C) = O(a+u\log u)$ ^[41]. Note that $\left| X \right| = n$ and $\left| Y \right|\le 2mn$. We get:

Theorem 3.1. There is an exact algorithm for $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\sum{{{f}_{j}}({{T}_{j}})}$ that runs in $O({{n}^{3}}m+{{n}^{2}}m\log(mn))$ time.

Next, we consider $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\max \{{{f}_{j}}({{T}_{j}})\}$. Let $OPT$ denote the objective value of an optimal schedule.

Recall that we are focusing on an optimal schedule in which machine ${{M}_{i}}$ ($i = 1, 2, \ldots, m$) processes ${{n}_{i}}$ batches (some batches may be empty), where ${{n}_{i}}$ denotes the smallest integer such that ${{n}_{i}}{{K}_{i}}\ge n$. Each batch on ${{M}_{i}}$ has ${{K}_{i}}$ positions to accommodate jobs, and there are at most $2n$ positions on ${{M}_{i}}$, $i = 1, 2, \ldots, m$. Therefore, there are at most $2mn$ positions in total. Since each position has at most $n$ choices of accommodating a job, there are at most $2m{{n}^{2}}$ possible values for $OPT$. We can sort these values in ascending order in $O(m{{n}^{2}}\log(mn))$ time. Then, we perform a binary search in the interval to determine $OPT$ in $O(\log (mn))$ iterations.

For each value $\lambda$ selected, we test whether there is a feasible schedule whose objective value is no more than $\lambda$. To this end, we construct a bipartite graph $G$ with bipartition $(X, Y)$ as follows. Regard each job $j\in \mathcal{J}$ as a vertex in $X$, and each empty batch ${{B}_{k, i}}$ as ${{K}_{i}}$ vertices ${{y}_{k1}}, {{y}_{k2}}, \ldots, {{y}_{k{{K}_{i}}}}$ in $Y$, where $j$ is joined to ${{y}_{k1}}, {{y}_{k2}}, \ldots, {{y}_{k{{K}_{i}}}}$ if and only if ${{M}_{i}}\in {{\mathcal{M}}_{j}}$ and ${{f}_{j}}(kp/{{v}_{i}}-{{d}_{j}})\le \lambda$, $j = 1, 2, \ldots, n$, $k = 1, 2, \ldots, {{n}_{i}}$, $i = 1, 2, \ldots, m$. Then we use the algorithm in ^[42] to solve the maximum cardinality bipartite matching problem. If the obtained matching saturates every vertex in $X$, then the procedure succeeds and we search the lower half of the interval. Otherwise, the procedure fails and we search the upper half of the interval.

The algorithm in ^[42] runs in $O(\sqrt{\left| X \right|+\left| Y \right|}\cdot \left| X \right|\left| Y \right|)$ time. Note that $\left| X \right| = n$ and $\left| Y \right|\le 2mn$. We get:

Theorem 3.2. There is an exact algorithm for $Q|{{p}_{j}} = p, {{d}_{j}}, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|\max \{{{f}_{j}}({{T}_{j}})\}$ that runs in $O({{n}^{5/2}}{{m}^{3/2}}\log (mn))$ time.

4.   Unequal release times

In this section, we consider the case of unequal release times. We will present an algorithm for $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|{{C}_{\max }}$, which generalizes the one in ^[27] for $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}|{{C}_{\max }}$ (the special case of $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|{{C}_{\max }}$ where all ${{K}_{i}} = 1$). Let $OPT$ denote the makespan of an optimal schedule for $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|{{C}_{\max }}$. Let $\Lambda =$ $\{\lambda |\lambda = {{r}_{j}}+kp/{{v}_{i}}; j, k\in \{1, 2, \ldots n\}\text{ and }i\in \{1, 2, \ldots m\}\}$. The following lemma, adopted from ^[27], still holds for $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|{{C}_{\max }}$.

Lemma 4.1. The set $\Lambda$, as defined above, contains all candidates for $OPT$.

Since $\left| \Lambda \right|\le m{{n}^{2}}$, there are at most $m{{n}^{2}}$ possible values for $OPT$. We can sort these values in ascending order in $O(m{{n}^{2}}\log (mn))$ time. Then, we perform a binary search to determine $OPT$ in $O(\log (mn))$ iterations.

For each value $\lambda$ selected, we use the following procedure, AssignJobs, to test whether there is a feasible schedule whose makespan is no more than $\lambda$.

AssignJobs ($\lambda$):

Step 1. Assign ${{b}_{i}} = \min \{{{n}_{i}}, \left\lfloor \lambda \cdot {{v}_{i}}/p \right\rfloor \}$ empty batches of length $p$ and capacity ${{K}_{i}}$ to machine ${{M}_{i}}$, where ${{n}_{i}}$ denotes the smallest integer such that ${{n}_{i}}{{K}_{i}}\ge n$. The k-th batch on ${{M}_{i}}$, ${{B}_{k, i}}$, starts at time $\lambda -({{b}_{i}}-k+1)p/{{v}_{i}}$ and completes at time $\lambda -({{b}_{i}}-k)p/{{v}_{i}}$, $k = 1, 2, \ldots, {{b}_{i}}$, $i = 1, 2, \ldots, m$.

Step 2. Construct a bipartite graph $G$ with bipartition $(X, Y)$ as follows. Regard each job $j\in \mathcal{J}$ as a vertex in $X$, and each empty batch ${{B}_{k, i}}$ as ${{K}_{i}}$ vertices ${{y}_{k1}}, {{y}_{k2}}, \ldots, {{y}_{k{{K}_{i}}}}$ in $Y$, where $j$ is joined to ${{y}_{k1}}, {{y}_{k2}}, \ldots, {{y}_{k{{K}_{i}}}}$ if and only if ${{M}_{i}}\in {{\mathcal{M}}_{j}}$ and ${{r}_{j}}\le \lambda -({{b}_{i}}-k+1)p/{{v}_{i}}$, $j = 1, 2, \ldots, n$, $k = 1, 2, \ldots, {{b}_{i}}$, $i = 1, 2, \ldots, m$.

Step 3. Use the algorithm in ^[42] to solve the maximum cardinality bipartite matching problem. If the obtained matching saturates every vertex in $X$, then the procedure succeeds and terminates. Otherwise, the procedure fails and terminates.

Lemma 4.2. If $OPT\le \lambda$, then AssignJobs will generate a feasible schedule in $O({{n}^{5/2}}{{m}^{3/2}})$ time for $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|{{C}_{\max }}$ whose makespan is at most $\lambda$.

Proof. Let ${{\sigma }^{*}}$ denote an optimal schedule. Consider machine ${{M}_{i}}$, $i = 1, 2, \ldots, m$. Since $OPT\le \lambda$, in ${{\sigma }^{*}}$, ${{M}_{i}}$ processes at most ${{b}_{i}}$ batches. Without loss of generality, assume that there are ${{b}_{i}}$ batches (some of which may be dummy empty batches) processed on ${{M}_{i}}$ in ${{\sigma }^{*}}$, denoted as $B_{1, i}^{*}, B_{2, i}^{*}, \ldots B_{{{b}_{i}}, i}^{*}$.

Modify ${{\sigma }^{*}}$ as follows. Let $B_{{{b}_{i}}, i}^{*}$ be completed at time $\lambda$, $B_{{{b}_{i}}-1, i}^{*}$ be completed at time $\lambda -p/{{v}_{i}}$, ..., $B_{1, i}^{*}$ be completed at time $\lambda -({{b}_{i}}-1)p/{{v}_{i}}$, $i = 1, 2, \ldots, m$. Denote by ${{\tilde{\sigma }}^{*}}$ the modified schedule. Since each batch in ${{\tilde{\sigma }}^{*}}$ starts no earlier than its corresponding batch in ${{\sigma }^{*}}$, ${{\tilde{\sigma }}^{*}}$ is a feasible schedule. The makespan of ${{\tilde{\sigma }}^{*}}$ is exactly $\lambda$. Clearly, AssignJobs will generate a feasible schedule which is no worse than ${{\tilde{\sigma }}^{*}}$.

The algorithm in ^[42] runs in $O(\sqrt{\left| X \right|+\left| Y \right|}\cdot \left| X \right|\left| Y \right|)$ time. Since $\left| X \right| = n$ and $\left| Y \right|\le 2mn$, the running time of AssignJobs is $O({{n}^{5/2}}{{m}^{3/2}})$.

We get:

Theorem 4.3. There is an exact algorithm for $Q|{{r}_{j}}, {{p}_{j}} = p, {{\mathcal{M}}_{j}}, p-batch, {{K}_{i}}|{{C}_{\max }}$ that runs in $O({{n}^{5/2}}{{m}^{3/2}}\log (mn))$ time.

5.   Conclusions

We studied the problem of scheduling jobs with equal lengths and processing set restrictions on uniform parallel batch machines with non-identical capacities. For the case of equal release times, we gave efficient exact algorithms for various objective functions. For the case of unequal release times, we gave efficient exact algorithms for minimizing makespan. The findings extend previous results for uniform machines counterparts.

Future research should focus on extending the algorithms to the case of unequal release times for objective functions other than makespan. It would also be interesting (and difficult) to extend the techniques to other related models, for general or special cases of processing set restrictions, such as scenario-dependent processing times and/or due dates ^[43], two-agent scheduling problems ^[44], or multitasking scheduling problems ^[45].

Acknowledgments

This work is supported by Natural Science Foundation of Shandong Province China (No. ZR2020MA030).

Conflict of interest

The authors declare there is no conflict of interest.