[1]Samuel Bismuth

[1]Department of Computer Science, Ariel University, Ariel, 40700, Israel

2]Department of Mathematics and Computer Science, St. Petersburg State
University, St. Petersburg, 199178, Russia

# Uniform Machines Scheduling with Bounded Splittable Jobs

0000-0003-3471-5402<EMAIL_ADDRESS>Vladislav Makarov
<EMAIL_ADDRESS>Erel Segal-Halevi  0000-0002-7497-5834<EMAIL_ADDRESS>Dana
Shapira  0000-0002-2320-9064<EMAIL_ADDRESS>*  [

###### Abstract

We consider the classic problem of makespan minimization on a fixed number $n$
of machines with possibly different speeds (“uniform machines”). In an attempt
to improve the makespan, we allow a fixed number $s$ of jobs to be split
between two or more machines. We show that makespan minimization on $n\geq 3$
uniform machines with $s$ split jobs can be solved in polynomial time whenever
$s\geq n-2$, while it is NP-complete otherwise even for identical machines. We
provide a Fully Polynomial-Time Approximation Scheme (FPTAS) to deal with the
case $s<n-2$.

The main technique we use is a two-way polynomial-time reduction between
makespan-minimization with splitting and a second variant, which may be of
independent interest, in which the makespan must be within a pre-specified
interval. We prove that, for any fixed integer $n\geq 3$, the second variant
can be solved in polynomial time if the length of the allowed interval is at
least $(n-2)/n$ times the maximum job size, and it is NP-complete otherwise
even for identical machines.

Using the same reduction, we implement a state-space-search algorithm for
makespan minimization with any number $s$ of split jobs, and use it in
computerized simulations to evaluate the effect of $s$ on the makespan.

###### keywords:

FPTAS, algorithm, complexity, combinatorial problems, partitioning problems

##  1 Introduction

In the problem of _uniform machine scheduling_ , we are given a list of $m$
jobs with positive integer lengths denoted by ${\cal
X}:=(x_{1},\ldots,x_{m})$, and a list of $n$ machines with positive integer
speeds denoted by ${\cal R}:=(r_{1},\dots,r_{n})$. Machine $i$ processes job
$j$ in $x_{j}/r_{i}$ seconds. Our goal is to partition the jobs among the
machines such that the _makespan_ (the maximum completion time of a machine)
is as small as possible; ideally, we would like to find a _perfect partition_
, in which all machines complete at the same time,
$(\sum_{j}x_{j})/(\sum_{i}r_{i})$. The problem is NP-hard even when $r_{i}=1$
for all $i$ (the setting of _identical machines_); this setting is equivalent
to the problem of _multiway number-partitioning_ , which is NP-hard for every
fixed $n\geq 2$ [1]. We present the problem formally below (where the input is
in parentheses, and fixed parameters that are not part of the input are in
brackets): UniMinMax$[n,{\cal R}]$(${\cal X}$): Minimize
$\max(b_{1},\dots,b_{n})$ where $b_{1},\dots,b_{n}$ are completion times in an
$n$-way partition (a partition into $n$ bins) of ${\cal X}$ among machines
with speeds ${\cal R}$ ($b_{i}$ is the completion time of machine $i$).

The same problem can also be interpreted as a problem of _fair division with
different rights_. Some $m$ items with values $x_{1},\ldots,x_{m}$ have to be
divided among $n$ partners with different rights, $r_{1},\ldots,r_{n}$. The
goal is to find a _perfectly fair partition_ , in which each partner $i$
receives a total value of exactly $r_{i}\cdot(\sum_{j}x_{j})/(\sum_{i}r_{i})$.

When the original instance does not admit a perfect partition, we may want to
improve the makespan by _splitting_ one or more jobs among two or more
machines (assuming different parts of the same job can run on parallel).
Splitting is particularly common in the fair division applications, in which
the ownership on one or more items may be split in order to attain a perfectly
fair partition. If all $m$ jobs can be split then the problem becomes easy.
Denote $A:=\sum_{i=1}^{n}r_{i}$. Splitting each job $j$ into $n$ parts such
that the part allocated to machine $i$ has length $\frac{r_{i}}{A}\cdot x_{j}$
yields a perfect partition. However, splitting a job (or splitting an
ownership of an item) may be inconvenient or expensive. Therefore, the number
of split jobs (or items with split ownership) should be bounded.

As an example, consider a food factory with $n=3$ chopping machines with
speeds $2,1,1$, who has to cut $m=4$ vegetables with processing times ${\cal
X}=(22,7,4,3)$ minutes. Each job is divisible — as one vegetable may be cut in
different machines, but splitting a job is inconvenient — since it requires
washing more dishes. Without splitting, the minimum total processing time is
11 minutes: $(22)/2,(7)/1,(4+3)/1$. By splitting the vegetable with processing
time $22$ into three different machines, the processing time is 9 minutes:
$(18)/2,(7+2)/1,(4+3+2)/1$.

As a second example (using the same $m,n$ and ${\cal X}$), a video streaming
platform earns money by showing advertisements to users. The platform has an
agreement with $m$ different companies to display ${\cal X}$ seconds of
advertisements to $n$ users. One or several of them can be split by enabling
the user to skip it after a given number of seconds. Nevertheless, if an
advertisement is split, the platform earns less. Similarly to the case with
the chopping machine, the option to split a single advertisement can make the
division more balanced among the users.

While we use the terminology of machine scheduling, which is common in the
literature, our motivating application actually comes from fair division. Some
$m$ items with values $x_{1},\ldots,x_{m}$ have to be divided among $n$
partners with different rights, $r_{1},\ldots,r_{n}$. A _perfect partition_ is
one in which each partner $i$ receives a total value of exactly
$\frac{r_{i}}{A}\cdot\sum_{j}x_{j}$. Attaining a perfect partition may require
to split the ownership of one or more items. For example, suppose the items
are houses with values $22,7,4,3$ and the partners’ rights are $1/2,1/4,1/4$.
Without splitting, one partner necessarily gets the house with value $22$,
which is worth more than $1/2$ of the total. Splitting the ownership on this
house among the three partners enables a perfect partition, in which the
partners’ values are $18,7+2,4+3+2$. In this case, a single split item is
sufficient for a perfect partition.

Motivated by these and similar examples of fair division and machine
scheduling problems, we define a variant of the UniMinMax$[n,{\cal R}]$
problem, parametrized by an integer $s\in\\{0,\ldots,m\\}$, which specifies
that at most $s$ jobs from ${\cal X}$ are allowed to be split between machines
(equivalently: at most $s$ items may be shared among partners).
UniMinMaxSplit$[n,s,{\cal R}]$(${\cal X}$): Minimize $\max(b_{1},\dots,b_{n})$
where $b_{1},\dots,b_{n}$ are completion times in an $n$-way partition of
${\cal X}$ among machines with speeds ${\cal R}$, in which at most $s$ jobs
are split.

We denote by IsPerfectSplit$[n,s,{\cal R}]$ the decision version of
UniMinMaxSplit$[n,s,{\cal R}]$, which only asks if there exists a perfect
partition (a partition with equal completion times). Note that the problem
definition does not determine in advance which $s$ jobs will be split, but
only bounds their number. The solver may decide which jobs to split after
receiving the input.

When $s=0$, UniMinMaxSplit$[n,s,{\cal R}]$ is equivalent to the NP-hard
problem UniMinMax$[n,{\cal R}]$. In contrast, when $s\geq n-1$ the problem is
easily solvable by the following algorithm: put the jobs on a line, cut the
line into $n$ pieces such that the length of line $i$ is
$\frac{r_{i}}{A}\cdot(\sum_{j}x_{j})$, and put the corresponding piece in
machine $i$. Since $n-1$ cuts are made, at most $n-1$ jobs need to be split.
So for $n=2$, the runtime complexity of the UniMinMaxSplit$[n,s,{\cal R}]$
problem is well-understood (assuming ${\sf P}\neq{\sf NP}$): it is polynomial-
time solvable if and only if $s\geq 1$. The main goal of this paper is to
analyze the runtime complexity of the problem for any fixed integers $n\geq 3$
and $1\leq s\leq n-2$, as a function of $m$ — the number of input integers,
and $\log_{2}{S}$ — where $S$ is defined as the perfect completion time,
$S:=(\sum_{j}x_{j})/A$. Note that $\log_{2}{S}$ is upper bounded by the number
of bits in the input (assuming $A$ is a constant). Our main results are:

######  Theorem 1.

For any fixed integers $n\geq 3$ and $s\geq n-2$ and fixed speeds ${\cal R}$,
UniMinMaxSplit$[n,s,{\cal R}]$ can be solved in time $O(poly(m,\log{S}))$.

The condition $s\geq n-2$ is tight: when $s<n-2$, the problem is NP-hard even
in the special case of identical machines ($r_{i}=1$ for all $i$), and this is
true even for its decision variant IsPerfectSplit$[n,s,{\cal R}]$.

######  Theorem 2.

For any fixed integers $n\geq 3$ and $s<n-2$, IsPerfectSplit$[n,s,{\cal R}]$
when $r_{i}\equiv 1$ is NP-complete.

In order to solve UniMinMaxSplit$[n,s,{\cal R}]$, we consider another variant
of uniform machines scheduling, a decision problem which asks whether the
maximum completion time is within a pre-specified interval around the perfect
completion time, $S:=(\sum_{j}x_{j})/A$. The runtime complexity of this
problem depends on the size of the allowed interval. In general, the problem
is NP-complete when the interval is “small” and in P when the interval is
“large”. Specifically, when $n=2$, the runtime complexity depends on the ratio
of the allowed interval to the _average completion time_ , while when $n\geq
3$ it depends on the ratio of the allowed interval to the _longest job
length_. Therefore, we present two variants of the problem. The first is
parametrized by a rational number $t\geq 0$: IsMaxInIntervalT$[n,t,{\cal
R}]$(${\cal X}$): Given a set ${\cal X}$ of $m$ jobs with positive integer
sizes, decide if there exists a partition of ${\cal X}$ among $n$ machines
with speeds ${\cal R}$ in which the completion time of every machine $i$ is at
most $(1+t)S$, where $S:=(\sum_{j}x_{j})/A$. The second is parametrized by a
rational number $d\geq 0$: IsMaxInIntervalD$[n,d,{\cal R}]$(${\cal X}$): Given
a set ${\cal X}$ of $m$ jobs with positive integer sizes, decide if there
exists a partition of ${\cal X}$ among $n$ machines with speeds ${\cal R}$ in
which the completion time of every machine $i$ is at most $(S+dM)$, where
$S:=(\sum_{j}x_{j})/A$ and $M:=(\max_{j}x_{j})/A$. Note that
$S\leq\max(b_{1},\ldots,b_{n})$ always holds by the pigeonhole principle, so
we could have named our problems “Upper Bound” instead of “Interval”. We
prefer to use “Interval” because our proofs are based on both lower bounds and
upper bounds. Our secondary results are:

######  Theorem 3.

For $n=2$ and any rational number $t>0$ and fixed speeds ${\cal R}$, the
IsMaxInIntervalT$[n,t,{\cal R}]$(${\cal X}$) problem can be solved in time
$O(\emph{poly}(m,\log{S},1/t))$.

######  Theorem 4.

For any fixed integer $n\geq 3$ and rational number $d\geq n-2$ and fixed
speeds ${\cal R}$, the IsMaxInIntervalD$[n,d,{\cal R}]$(${\cal X}$) problem
can be solved in time $O(\emph{poly}(m,\log{S}))$.

Again, the condition $d\geq n-2$ is tight even for the special case of
identical machines:

######  Theorem 5.

For any fixed $n\geq 3$ and rational number $d<n-2$,
IsMaxInIntervalD$[n,d,{\cal R}]$(${\cal X}$) when $r_{i}\equiv 1$ is NP-
complete.

Our algorithms use as building-blocks several Fully Polynomial-Time
Approximation Scheme (FPTAS) algorithms, which we define next.

######  Definition 1.

An FPTAS for UniMinMax$[n,{\cal R}]$ is an algorithm that finds, for each real
$\epsilon>0$, an $n$-way partition of ${\cal X}$ with
$OPT\leq\max(b_{1},\ldots,b_{n})\leq(1+\epsilon)\cdot OPT$, where OPT is the
smallest possible value of $\max(b_{1},\ldots,b_{n})$ in the given instance,
in time $O(poly\allowbreak(m,1/\epsilon,\log S))$.

Notice that an FPTAS finds a solution for which the relative deviation from
optimality depends on the optimal integral solution. The
IsMaxInIntervalT$[n,t,{\cal R}]$ problem requires a stronger solution, for
which the relative deviation from optimality depends on the optimal fractional
solution. Therefore, although UniMinMax$[n,{\cal R}]$ has an FPTAS [2], it
does not automatically solve IsMaxInIntervalT$[n,t,{\cal R}]$. In Section 3.1
we show how an FPTAS for a slightly different problem can be used to solve
IsMaxInIntervalT$[n=2,t,{\cal R}]$ and prove Theorem 3. In the rest of Section
3 we analyze IsMaxInIntervalD$[n,d,{\cal R}]$ and prove Theorem 4 and Theorem
5.

In Section 4, we prove a two-way polynomial-time reduction between the machine
scheduling with interval target and machine scheduling with split jobs
problems. Using this reduction and Theorems 4 and 5, we conclude the proof of
Theorems 1 and 2. In Section 4.1, we provide an FPTAS to deal with the problem
UniMinMaxSplit$[n,s,{\cal R}]$ when $s<n-2$ splittings.

In Section 5, using the same reduction, we develop a practical (not
polynomial-time) algorithm for solving the case of identical machines:
UniMinMaxSplit$[n,s,r_{i}\equiv 1]$, for any $s\geq 0$. The algorithm can use
any practical algorithm for solving the UniMinMax$[n,r_{i}\equiv 1]$ problem;
we use a variant of the Complete Greedy Algorithm [3]. We apply this algorithm
to various randomly generated instances, and analyze the effect of $s$ on the
quality of the attained solution. We find out that, in most cases, much fewer
than $n-1$ splits are sufficient for attaining a perfect partition. For
example, in over $74\%$ of the settings we checked, $n/2$ splits are
sufficient.

The supplement provides complementary results and technical proof details
omitted from the main text.

In Section A.1, we show that assuming $n$ is fixed is necessary for our
positive results: when $n$ is part of the input (not fixed in advance), both
IsMaxInIntervalD$[d,{\cal R}]$$({\cal X},n)$ and IsPerfectSplit$[s,{\cal
R}]$$({\cal X},n)$ are strongly NP-hard for every fixed rational number $d$
and integer $s$, even in the special case of identical machines.

In Section A.2, we analyze a different way to control the amount of splitting.
Instead of the number of split jobs, one can measure the number of times each
job is split. The number of splittings is at least the number of split jobs,
but might be larger. For example, a single job split into $10$ different
machines counts as $9$ splittings. We name this variant
IsPerfectSplittings$[n,s,{\cal R}]$(${\cal X}$). When $s\geq n-1$, a perfect
partition can be found by the same ”line-cutting” algorithm. We prove that
this variant is NP-hard for all $s<n-1$ even in the special case of identical
machines, thus completing its run-time complexity classification.

In Appendix B we prove the existence of FPTAS for our problems and we prove
the exact running time of our algorithms. We prove our main Lemma (Lemma 4) in
Appendix C. Finally in Appendix D we present the plots obtained for different
values of the parameters presented in the Section 5.

##### Techniques.

The main results of our paper are based on FPTAS for several machine
scheduling problems. [2] gives a general method for converting a dynamic
program to an FPTAS. He shows that his method can be used to design FPTAS for
hundreds of different combinatorial optimization problems. We apply his method
to several different problems. We remark that the FPTAS designed by
Woeginger’s method for partitioning problems are polynomial in $m$ and
$\log{S}$, but exponential in $n$; the same is true for our algorithms.

##  2 Related work

###  2.1 Splitting in job scheduling.

There are several variants of job scheduling problems in which it is allowed
to break jobs apart. They can be broadly classified into _preemption_ and
_splitting_. In the preemption variants, different parts of a job must be
processed in different times. In the three-field notation, they are denoted by
”pmtn” and were first studied by [4]. In the splitting variants, different
parts of a job may be processed simultaneously on different machines. They are
denoted by ”split” and were introduced by [5]. While we consider the splitting
variant in Section A.2, our main focus is on a new variant, in which we
measure the number of jobs that are split, rather than the number of
splittings. This is motivated by the fair division application, in which it is
desirable to bound the number of items with split ownership.

Various problems have been studied in job scheduling with preemption. The most
closely related to our problem is the generalized multiprocessor scheduling
(GMS). It has two variants. In the first variant, the total number of
preemptions is bounded by some fixed integer. In the second variant, each job
$j$ has an associated parameter that bounds the number of times $j$ can be
preempted. In both variants, the goal is to find a schedule that minimizes the
makespan subject to the preemption constraints.

For identical machines, [6] prove that with the bound of $n-2$ on the total
number of preemptions, the problem is NP-hard, whereas [4] shows a linear-time
algorithm with $n-1$ preemptions. In Section A.2 we prove an analogous result
where the bound is on the total number of splittings.

For uniform machines, a polynomial algorithm by [7] yields at most $2n-2$
preemptions, and [8] proved NP-hardness for the case where the number of
preemption is strictly less than $2n-2$. Also, [8] present a PTAS for GMS with
a global preemption bound, and another PTAS for GMS with job-wise preemption
bound when the number of machines is a fixed constant. [9] study the special
case in which at most one preemption is allowed. They show that makespan
minimization is polynomial for two machines.

Another closely related problem is called the minimum preemption scheduling
(MPS). In this problem, the only feasible schedules are preemptive schedules
with the smallest possible makespan. The goal is to find a feasible schedule
that minimizes the overall number of preemptions. Using uniform machines, [8]
show a lower bound on the number of preemptions: $2m-2$ and gives an algorithm
that achieves this bound.

There are many other papers that work on other variants of preemptive
scheduling. For example, [10] consider single-machine scheduling with job
release and delivery dates, where there is no firm bound on the number of
preemptions, but each preemption requires spending time on ”job setup”.

For job scheduling with splittings, [11] assumes unbounded splittings and
preemptions and gives polynomial-time algorithms that minimize the maximum
tardiness and the maximum weighted tardiness, for uniform and unrelated
machines. [5] allow unbounded splittings, and give polynomial algorithms for
many optimality criteria (such as makespan, lateness, tardiness and more),
with identical, uniform and unrelated machines. [12] study makespan
minimization using the $k$-splittable variant, a variant where each job is
allowed to be split into at most $k$ different machines. While they consider
job-wise splitting bounds, we consider a global splitting bound. [13] study
makespan minimization on a single machine with a machine-availability
constraint with a lower bound on the length of each part of a job that is
split.

For identical machines, [14], suggest a branch and bound algorithm with the
objective to minimize the total tardiness with independent job setup time.
[15] propose a heuristic to the same problem, with the objective to minimize
the makespan. [16] suggest a two-phase heuristic algorithm with the objective
of minimizing total tardiness. With the objective to minimize the makespan,
[17] studies another variant with family setup time in which no setup is
required when parts from the same job are produced consecutively. And, [18]
include a learning property that improves the processing time of a job
according to the learning effect. The learning has to be restarted if one job
is split and processed by a different machine.

For uniform machines, [19] study a variant with dedicated machines (there are
some dedicated machines for each job), sequence-dependent setup times, and
limited setup resources (jobs require setup operators that are limited) with
the objective to minimize the makespan.

In all these works, there is no global bound on the number of splitting jobs.
As far as we know, bounding the number of splittings or split jobs was not
studied before.

###  2.2 Splitting in fair division.

Splitting was also studied in the context of fair division. The idea of
finding fair allocations with a bounded number of split items originated from
[20, 21]. They presented the _Adjusted Winner_ (AW) procedure for allocating
items among two agents with possibly different valuations. AW finds an
allocation that is _envy-free_ (no agent prefers the bundle of another agent),
_equitable_ (both agents receive the same subjective value), and _Pareto-
optimal_ (there is no other allocation where some agent gains and no agent
loses), and in addition, at most a single item is split between the agents.
Hence, AW solves a problem that is similar to
IsPerfectSplit$[n=2,s=1,r_{i}\equiv 1]$(${\cal X}$) but more general, since AW
allows the agents to have different valuations to the same items. AW was
applied (at least theoretically) to division problems in divorce cases and
international disputes [22, 23] and was studied empirically in [24, 25]. The
AW procedure is designed for two agents. For $n\geq 3$ agents, the number of
split items allowed was studied in an unpublished manuscript of [26] using
linear programming techniques. He proved the existence of an _egalitarian_
allocation of goods (i.e., an allocation in which all agents have a largest
possible equal utility [27]), with at most $n-1$ split items; this can be seen
as a generalization of IsPerfectSplit$[n,s=n-1,r_{i}\equiv 1]$(${\cal X}$).

[28] studied the problem of _consensus partitioning_. In this problem, there
are $n$ agents with different valuations, and the goal is to partition a list
of items into some $k$ subsets (where $k$ and $n$ may be different), such that
the value of each subset is $1/k$ for each agent. They prove that a consensus
partitioning with at most $n(k-1)$ split items can be found in polynomial
time. The $n(k-1)$ is tight in the worst case.

Most similar to our paper is the recent work of [29]. Their goal is to find an
allocation among $n$ agents with different valuations, which is both fair and
_fractionally Pareto-optimal(fPO)_, a property stronger than Pareto-optimality
(there is no other discrete or fractional allocation where some agent gains
and no agent loses). This is a very strong requirement: when $n$ is fixed, and
the valuations are _generic_ (i.e., for every two agents, no two items have
the same value-ratio), the number of fPO allocations is polynomial in $m$, and
it is possible to enumerate all such allocations in polynomial time. Based on
this observation, they present an algorithm that finds an allocation with the
smallest number of split items, among all allocations that are fair and fPO.
In contrast, in our paper, we do not require fPO, which may allow allocations
with fewer split items. However, the number of potential allocations becomes
exponential, so enumerating them all is no longer feasible.

Recently, [30] studied an allocation problem where some items are divisible
and some are indivisible. In contrast to our setting, in their setting the
distinction between divisible and indivisible items is given in advance, that
is, the algorithm can only divide items that are pre-determined as divisible.
In our setting, only the _number_ of divisible items is given in advance, but
the algorithm is free to choose _which_ items to split after receiving the
input.

##  3 Partition with Interval Target

In this section we analyze the problems IsMaxInIntervalT$[n,t,{\cal R}]$ and
IsMaxInIntervalD$[n,d,{\cal R}]$. Recall that these problems accept as input a
list ${\cal X}$ of positive integers with sum $A\cdot S$ and maximum element
$A\cdot M$, where $A=\sum_{i}r_{i}$ and $S,M$ are some rational numbers.

###  3.1 The IsMaxInIntervalT$[n,t,{\cal R}]$ problem

Given an instance of IsMaxInIntervalT$[n,t,{\cal R}]$(${\cal X}$), we say that
a partition of ${\cal X}$ is _$t$ -feasible_ if
$S\leq\max(b_{1},\ldots,b_{n})\allowbreak\leq(1+t)\cdot S$, where
$b_{1},\ldots,b_{n}$ are the completion times and $S$ is the sum of job
lengths divided by $A$. The IsMaxInIntervalT$[n,t,{\cal R}]$(${\cal X}$)
problem is to decide whether a $t$-feasible partition exists.

######  Lemma 1.

When $t\geq 1$, the problem IsMaxInIntervalT$[n,t,{\cal R}]$(${\cal X}$) can
be decided in linear time by a greedy algorithm.

###### Proof.

Given an instance of IsMaxInIntervalT$[n,t,{\cal R}]$(${\cal X}$), the total
length of all jobs is $A\cdot S$. Therefore, there are at most $A$ jobs with
length $S$ or greater. Since $A$ is a fixed parameter, we can try all possible
ways to partition the jobs with lengths at least $S$ among the $n$ machines.
If, in all these partitions, the maximum completion time is larger than
$(1+t)S$, the answer is clearly “no”. Otherwise, we claim that the answer is
“yes”. To prove this, we pick arbitrarily one partition in which the maximum
completion time is at most $(1+t)S$, and show how the jobs with length smaller
than $S$ can be allocated, such that the maximum completion time remains at
most $(1+t)S$.

We first claim that there exists at least one machine $i$ with completion time
at most $(2-1/r_{i})S$. Suppose by contradiction that no such machine exists.
Then, the sum of the job lengths processed by the machines is larger than:

$\sum_{i}r_{i}(2-1/r_{i})S=\sum_{i}(2r_{i}-1)S\geq\sum_{i}r_{i}S=AS,$

which is a contradiction since the total length of all jobs is $A\cdot S$.

So at each moment, we pick one machine $i$ with completion time at most
$(2-1/r_{i})S$, and put there an arbitrary remaining job. Since the length of
the remaining job is at most $S$, the completion time of machine $i$ after the
addition is at most $2S$, which is at most $(1+t)S$ since $t\geq 1$.

We repeat this argument until all remaining jobs are allocated.

Therefore, the problem can be decided in time $O(m)$. ∎

Therefore, we focus below on the case $t<1$.

As a first (incomplete) attempt to solve IsMaxInIntervalT$[n,t,{\cal R}]$, let
us apply a known FPTAS for the UniMinMax$[n,{\cal R}]$ problem [2]. Denote the
largest completion time in the solution obtained by the FPTAS for a list
${\cal X}$ and an $\epsilon>0$ by FPTAS(UniMinMax$[n,{\cal R}]$$({\cal X})$,
$\epsilon$).

If FPTAS(UniMinMax$[n,{\cal R}]$$({\cal X})$, $\epsilon$)$\leq(1+t)\cdot S$,
then the partition returned by the FPTAS is $t$-feasible, so the answer to
IsMaxInIntervalT$[n,t,{\cal R}]$$({\cal X})$ is “yes”.

If FPTAS(UniMinMax$[n,{\cal R}]$$({\cal X})$, $\epsilon$)$>(1+t)\cdot S$, then
the partition returned by the FPTAS is not $t$-feasible, but we cannot
conclude that the answer to IsMaxInIntervalT$[n,t,{\cal R}]$$({\cal X})$ is
“no”. Still, this outcome does give us valuable information about the
instance: by the definition of FPTAS, it implies that the optimal value to
UniMinMax$[n,{\cal R}]$$({\cal X})$ is larger than $(1+t)\cdot
S/(1+\epsilon)$. This implies that, in _any_ $n$-way partition of ${\cal X}$,
there is at least one completion time larger than $(1+t)\cdot S/(1+\epsilon)$.

######  Definition 2.

Given an instance of IsMaxInIntervalT$[n,t,{\cal R}]$(${\cal X}$), a real
number $\epsilon>0$, and a partition of ${\cal X}$ among $n$ machines with
speeds ${\cal R}$, an _almost-full machine_ is a machine with completion time
larger than $(1+t)\cdot S/(1+\epsilon)$.

In the previous paragraph we have proved the following lemma:

######  Lemma 2.

For any integer $n\geq 2$, rational $t>0$ and real $\epsilon>0$, if
FPTAS$($UniMinMax$[n,{\cal R}]$$\allowbreak({\cal X})$, $\epsilon)>(1+t)\cdot
S$, then in any $n$-way partition of ${\cal X}$, at least one machine is
almost-full.

To gain more information on the instance, we apply an FPTAS for a constrained
variant of UniMinMax$[n,{\cal R}]$, with a Critical Coordinate (CC). For an
integer $n\geq 2$, a list ${\cal X}$, and a rational number $t>0$, we define
the following problem: UniMinMaxCC$[n,t,i,{\cal R}]$(${\cal X}$): Minimize
$\max(b_{1},\dots,b_{i-1},b_{i+1},\dots,b_{n})$ subject to
$b_{i}\leq(1+t)\cdot S$ where $b_{1},\dots,b_{n}$ are completion times in an
$n$-way partition of ${\cal X}$. The general technique developed by [2] for
converting a dynamic program to an FPTAS can be used to design an FPTAS for
UniMinMaxCC$[n,t,i,{\cal R}]$; we give the details in Section B.1. We denote
by FPTAS(UniMinMaxCC$[n,t,i,{\cal R}]$(${\cal X},t$), $\epsilon$) the largest
completion time in the obtained solution. The following lemma is the key for
our algorithms.

######  Lemma 3.

For any $n\geq 2,t>0,\epsilon>0$, if FPTAS$($UniMinMaxCC$[n,t,i,{\cal
R}]$$({\cal X})$, $\epsilon)>(1+t)\cdot S$ for all $i\in[n]$, then in any
$t$-feasible $n$-way partition of ${\cal X}$, at least _two_ machines are
almost-full.

###### Proof.

Suppose by contradiction that there exists a $t$-feasible partition of ${\cal
X}$ with at most one almost-full machine. Let $i$ be the index of the machine
with the largest completion time in that partition. Since machine $i$ has the
largest completion time, if there is one almost-full machine, it must be
machine $i$. Hence, machines that are not $i$ are not almost-full, so
$\max(b_{1},\dots,b_{i-1},b_{i+1},\dots,b_{n})\leq(1+t)\cdot S/(1+\epsilon)$.
Moreover, $b_{i}\leq(1+t)\cdot S$ since the partition is $t$-feasible.
Therefore, FPTAS$($UniMinMaxCC$[n,t,i,{\cal R}]$$({\cal X})$,
$\epsilon)\leq(1+t)\cdot S$ by the definition of FPTAS. This contradicts the
lemma assumption. ∎

Using Lemma 3, we can now derive a complete algorithm for
IsMaxInIntervalT$[n=2,t,{\cal R}]$.

Algorithm 1 IsMaxInIntervalT$[n=2,t,{\cal R}]$

1:for $i\in\\{1,2\\}$ do

2: Run the FPTAS for UniMinMaxCC$[n=2,t,i,{\cal R}]$(${\cal X}$) with critical
coordinate $i$ and $\epsilon=t/2$.

3: Let $b_{j}$ be the returned value, that is, the completion time of the
machine $j\neq i$.

4: if $b_{j}\leq(1+t)\cdot S$ then

5: return “yes”

6: end if

7:end for

8:return “no”

######  Theorem 6 (=Theorem 3).

For any rational $t>0$, Algorithm 1 solves the IsMaxInIntervalT$[n=2,t,{\cal
R}]$(${\cal X}$) problem in time $O(\text{poly}(m,\log{S},1/t))$, where $m$ is
the number of jobs in ${\cal X}$ and $S=(\sum_{j}x_{j})/A$ is the perfect
completion time.

###### Proof.

The run-time of Algorithm 1 is dominated by the run-time of the FPTAS for the
problem UniMinMaxCC$[n,t,i,{\cal R}]$, which is
$O(\text{poly}(m,\log{S},1/\epsilon))=O(\text{poly}(m,\log{S},1/t))$ (we show
in Section B.3.1 that the exact run-time is $O(\frac{m}{t}\log{S})$). It
remains to prove that Algorithm 1 indeed solves IsMaxInIntervalT$[n=2,t,{\cal
R}]$ correctly.

If $b_{j}$, the returned completion time of one of the
FPTAS(UniMinMaxCC$[2,t,i,{\cal R}]$(${\cal X}$), $\epsilon=t/2$), is at most
$(1+t)\cdot S$, then the partition found by the FPTAS is $t$-feasible, so
Algorithm 1 answers “yes” correctly. Otherwise, by Lemma 3, in any
$t$-feasible uniform partition of ${\cal X}$ into two machines, both machines
are almost-full. This means that, in any $t$-feasible partition, both
completion times $b_{1}$ and $b_{2}$ are larger than $(1+t)\cdot
S/(1+\epsilon)$, which is larger than $S$ since $\epsilon=t/2$. This means
that $r_{1}b_{1}+r_{2}b_{2}>(r_{1}+r_{2})S$. But this is impossible, since the
total length of all jobs is $A\cdot S=(r_{1}+r_{2})S$ by assumption.
Therefore, no $t$-feasible partition exists, and Algorithm 1 answers “no”
correctly. 111 Instead of an FTPAS for UniMinMaxCC$[n,t,i,{\cal R}]$, we could
use an FTPAS for the Subset Sum problem [31], using the same arguments. The
critical coordinate is not needed in the Subset Sum FPTAS, since the output is
always smaller than the target. We prefer to use the FTPAS for
UniMinMaxCC$[n,t,i,{\cal R}]$, since it is based on the general technique of
[2], that we use later for solving other problems.  ∎

######  Remark 1.

The reader may wonder why we cannot use a similar algorithm for $n\geq 3$. For
example, we could have considered a variant of UniMinMaxCC$[n,t,i,{\cal R}]$
with two critical coordinates: Minimize $\max(b_{3},\dots,b_{n})$ subject to
$b_{1}\leq(1+t)\cdot S$ and $b_{2}\leq(1+t)\cdot S$, where
$b_{1},b_{2},b_{3},\dots,b_{n}$ are completion times in an $n$-way partition
of ${\cal X}$. If the FPTAS for this problem does not find a $t$-feasible
partition, then any $t$-feasible partition must have at least three almost-
full machines. Since not all machines can be almost-full, one could have
concluded that there is no $t$-feasible partition into $n=3$ machines.

Unfortunately, the problem with two critical coordinates probably does not
have an FPTAS even for $n=3$, even for identical machines, since it is
equivalent to the Multiple Subset Sum problem, which does not have an FPTAS
unless P=NP [32]. In the next subsection we handle the case $n\geq 3$ in a
different way.

###  3.2 IsMaxInIntervalD$[n,d,{\cal R}]$: an algorithm for $n\geq 3$ and
$d\geq n-2$

We are given an instance of IsMaxInIntervalD$[n,d,{\cal R}]$(${\cal X}$),
where the sum of the job lengths is $A\cdot S$ and the maximum job length is
$A\cdot M$, where $S,M\in\mathbb{Q}$. We say that a partition of ${\cal X}$ is
_$d$ -possible_ if $S\leq\max(b_{1},\ldots,b_{n})\leq S+d\cdot M$, where
$b_{1},\ldots,b_{n}$ are the completion times. The IsMaxInIntervalD$[n,d,{\cal
R}]$(${\cal X}$) problem is to decide whether a $d$-possible partition exists.
Given an instance of IsMaxInIntervalD$[n,d,{\cal R}]$(${\cal X}$) , we let
$t:=dM/S$, so that a partition is $d$-possible if-and-only-if it is
$t$-feasible.

The algorithm starts by running FPTAS$($UniMinMaxCC$[n,t,i,{\cal R}]$$({\cal
X})$, $\epsilon=t/(4An^{2}m^{2}))$ for every $i\in[n]$. If the FPTAS find a
$t$-feasible partition for some $i$, we return “yes”. Otherwise, by Lemma 3,
any $t$-feasible partition must have at least two almost-full machines.

Now, we take a detour from the algorithm and prove some existential results
about partitions with two or more almost-full machines.

We assume that there are more jobs than machines, that is, $m>n$. This
assumption is because if $m\leq n$, one can compute all the combinations using
brute force (note that the running time is polynomial since $2^{m}\leq
2^{n}=O(1)$.

####  3.2.1 Structure of partitions with two or more almost-full machines

We distinguish between big, medium and small jobs defined as follows. A _small
job_ is a job with length smaller than $2\epsilon AS$; a _big job_ is a job
with length greater than $(\frac{t}{n-2}-2\epsilon)AS$. All other jobs are
called _medium jobs_. We denote by $m_{b}$ the number of big jobs in the
input.

######  Lemma 4.

Suppose that $d\geq n-2$, $t=dM/S<1$, $\epsilon=\frac{t}{4An^{2}m^{2}}$ and
the following properties hold.

  1. (1)

There is no $t$-feasible partition with at most $1$ almost-full machine;

  2. (2)

There is a $t$-feasible partition with at least $2$ almost-full machines.

Then, there is a $t$-feasible partition with the following properties.

  1. (a)

Exactly two machines are almost-full (let us call them 1 and 2).

  2. (b)

The total length of jobs processed by every not-almost-full machine
$i\in\\{3,\ldots,n\\}$ satisfies

$\displaystyle\left(r_{i}+\left(r_{i}-\frac{A}{n-2}\right)t-r_{i}2\epsilon\right)\cdot
S\leq~{}r_{i}b_{i}~{}\leq\left(r_{i}+\left(r_{i}-\frac{A}{n-2}\right)t+(A-r_{i})2\epsilon\right)\cdot
S.$

  3. (c)

Every almost-full machine processes only big jobs.

  4. (d)

Every not-almost-full machine processes only big jobs that are larger than
every job in machine $1,2$, and small jobs.

  5. (e)

Denote by $m_{i}$ the number of big jobs in machine $i$. Then,

$\displaystyle m_{i}=\begin{cases}r_{i}\cdot(m_{b}+n-2)/A&\text{for any
almost-full machine $i\in\\{1,2\\}$;}\\\ r_{i}\cdot(m_{b}+n-2)/A-1&\text{for
any not-almost-full machine $i\in\\{3,\ldots,n\\}$.}\end{cases}$

Note that properties (c) and (d) together imply that ${\cal X}$ contains no
medium jobs. In other words, if an instance contains some medium jobs, then
the lemma assumptions cannot hold, that is, either there is a $t$-feasible
partition with at most one almost-full machine, or there is no $t$-feasible
partition at all. Similarly, property (e) implies that $r_{i}\cdot(m_{b}+n-2)$
must be an integer multiple of $A$ for all $i$, where $m_{b}$ is the number of
big jobs in the input; if this is not the case, then again the lemma
assumptions cannot hold.

As an example to the situation described in the lemma, consider an instance
that admits a partition with two almost-full machines, and no partition with
at most one almost-full machine. There are $n=5$ identical machines (so
$A=n=5$), $~{}d=n-2=3,~{}{\cal X}=(n+2)\cdot[1]=(1,1,1,1,1,1,1)$. Then
$m=7,~{}5M=1,~{}5S=7,~{}S+dM=7/5+3/5=2$. Now, we can compute $t$ and
$\epsilon$: $t=dM/S=(3/5)/(7/5)=3/7$ and $\epsilon=t/(4\cdot m^{2})=3/1372$.
That is, an almost-full machine is a machine with completion time larger than
$(1+t)\cdot
S/(1+\epsilon)=((10/7)\cdot(7/5))/(1375/1372)=2/(1375/1372)=2744/1375<2$.
Also, a $d$-feasible solution of the instance is a solution where the largest
completion time is at most $(1+t)S=2$. Therefore, one possible partition is
$P_{1}=((1,1),(1,1),(1),(1),(1))$. This partition is $d$-possible since the
largest completion time equals $2$ as required. It has two almost-full
machines: 1 and 2. Note that there is also a partition with three almost-full
machines: $((1,1),(1,1),(1,1),(1),())$. However, there is no solution with at
most one almost-full machine. Let us see that $P_{1}$ satisfies all the
properties in the structure Lemma.

  1. (a)

Exactly two machines are almost-full: machine 1 and machine 2.

  2. (b)

The completion time of machines 3,4,5 (not-almost-full) satisfies

$\displaystyle\left(1-\frac{2}{n-2}t-2\epsilon\right)\cdot S$
$\displaystyle\leq
b_{3},b_{4},b_{5}\leq\left(1-\frac{2}{n-2}t+(n-1)2\epsilon\right)\cdot S$
$\displaystyle(1-2/7-3/686)\cdot 7/5$ $\displaystyle\leq
b_{3},b_{4},b_{5}\leq(1-2/7+6/342)\cdot 7/5$ $\displaystyle 0.99387755102$
$\displaystyle\leq b_{3},b_{4},b_{5}\leq 1.02456140351,$

which is true since $b_{3}=b_{4}=b_{5}=1$

  3. (c)

Every almost-full machine processes only _big-jobs_ , jobs with length larger
than $nS(\frac{t}{n-2}-2\epsilon)=7(1/7-3/686)=0.9693877551$. Since every job
length equals 1, the claim holds.

  4. (d)

Every not-almost-full machine processes big-jobs with length larger or equal
than every job length in machine 1,2, or _small-jobs_. Since all jobs are big
and have the same size, the claim holds trivially.

  5. (e)

All jobs are big, so $m_{b}=m=7$. Denote by $m_{i}$ the number of big jobs in
machine $i$. So $m_{1}=m_{2}=(m_{b}+n-2)/A=(7+5-2)/5=2$ and
$m_{3}=m_{4}=m_{5}=(m_{b}+n-2)/A-1=2-1=1$, which is true.

This example can be easily generalized to other values of $n$, such that all
the other example parameters are computed as a function $n$. For example, for
$n=4$ we have $d=n-2=4,{\cal X}=(n+2)\cdot[1]=[1,1,1,1,1,1]$, and the
partition with two almost-full machines is $[1,1],[1,1],[1],[1]$.

A full proof of the lemma appears in Appendix C; here we provide a sketch.

###### Proof Sketch.

We start with an arbitrary $t$-feasible partition with some $u\geq 2$ almost-
full machines $1,\ldots,u$, and convert it using a sequence of transformations
to another $t$-feasible partition satisfying properties (a)–(e), as explained
below. Note that the transformations are not part of our algorithm and are
only used to prove the lemma. First, we note that there must be at least one
machine which is not almost-full, since otherwise, each machine has a
completion time larger than $S$ (since it is an almost-full machine), implying
that the total length of the jobs is larger than $AS$ which is a
contradiction.

For (a), if there are $u\geq 3$ almost-full machines, we move any job from one
of the almost-full machine $3,\ldots,u$ to some not-almost-full machine. We
prove that, as long as $u\geq 3$, the target machine remains not-almost-full.
This transformation is repeated until $u=2$ and only machines 1 and 2 remain
almost-full.

For (b), for the lower bound, if there is some $i\in\\{3,\ldots,n\\}$ for
which $b_{i}$ is smaller than the lower bound, we move a job from the almost-
full machines $1,2$ to machine $i$. We prove that machine $i$ remains not-
almost-full, so by assumption (1) of the lemma, machines 1, 2 must remain
almost-full. We repeat until $b_{i}$ satisfies the lower bound. Once all
machines satisfy the lower bound, we prove that the upper bound is satisfied
too.

For (c), if machine 1 or 2 contains a job that is not big, we move it to some
machine $i\in\\{3,\ldots,n\\}$. We prove that machine $i$ remains not-almost-
full, so by assumption (1), machines 1, 2 must remain almost-full. We repeat
until machines 1 and 2 contain only big jobs.

For (d), if some machine $i\in\\{3,\ldots,n\\}$ contains a job $j$ that is
bigger than $2AS\epsilon$ and smaller than some job $j^{\prime}$ in machine 1
or 2, we exchange $j$ and $j^{\prime}$. We prove that, after the exchange,
machine $i$ remains not-almost-full, so machines 1, 2 must remain almost-full.
We repeat until machines 1,2 contain only the smallest big-items. Note that
transformations (b), (c), (d) increase the sum in the not-almost-full machines
$3,\ldots,n$, so the process must end.

For (e), we show an upper bound on the total processing length of the almost-
full machines depending on the number of big jobs. We divide the upper bound
by the longest job size, to get a lower bound on the number of big jobs in
each machine. We show that the sum of the lower bounds is exactly the number
of big jobs $m_{b}$, so the lower bound must in fact hold with equality. ∎

####  3.2.2 Back to the algorithm

We have left the algorithm at the point when FPTAS$($UniMinMaxCC$[n,t,i,{\cal
R}]$$({\cal X})$, $\epsilon)$ did not find a $t$-feasible partition. Lemma 3
implies that if a $t$-feasible partition exists, then it must have at least
two almost-full machines, and therefore there exists a $t$-feasible partition
satisfying all properties of Lemma 4. We can find such a partition (if it
exists) in the following way. We loop over all pairs of machines. For
simplicity, let us call the current pair of machines: $1$ and $2$. For each
pair, we check whether there exists an allocation in which these machines are
the almost-full machines, in two steps:

  * –

For Machines 1 and 2: Let $B\subseteq{\cal X}$ contain all big jobs in ${\cal
X}$, $m_{b}:=|B|$, and $m_{1},m_{2}$ given by Lemma 4(e). Find a $t$-feasible
partition of the $m_{1}+m_{2}$ smallest jobs in $B$ into two machines with
$m_{i}$ jobs in each machine $i\in\\{1,2\\}$.

  * –

For Machines 3,$\ldots$,n: Find a $t$-feasible partition of the remaining jobs
into $n-2$ machines.

For machines $3,\ldots,n$, we use the FPTAS for the problem
UniMinMax$[n-2,{\cal R^{\prime}}]$ where ${\cal
R^{\prime}}=[r_{3},\ldots,r_{n}]$. If it returns a $t$-feasible partition, we
are done. Otherwise, by Lemma 2, every partition into $(n-2)$ machines must
have at least one almost-full machine; but by Lemma 4(a), all machines
$3,\ldots,n$ are not almost-full — a contradiction. Therefore, if the FPTAS
does not find a $t$-feasible partition, we answer “no”. Machines 1 and 2
require a more complicated algorithm. 222Using a simple FPTAS for Subset Sum
to solve our problem is not possible since the total length of the jobs may
equal $(r_{1}+r_{2})(S+dM)$ and our goal is to schedule the jobs among two
machines of capacity $(r_{1}+r_{2})(S+dM)$, which means that no approximation
is allowed. Therefore, we need to pre-process the jobs in some way. The
technique we use is to inverse the job length. Even after inverting the jobs,
we need an additional cardinality constraint enforcing that there are exactly
$m_{i}$ jobs in machine $i$.

We need two new variants of the IsMaxInIntervalT$[n,t,{\cal R}]$ problem. We
first define the IsMaxInIntervalTT$[n=2,t_{1},t_{2},{\cal R}]$ problem as
follows. For two fixed rationals $t_{1},t_{2}$ and a set of ratios ${\cal
R}=(r_{1},r_{2})$ such that $r_{1}t_{1}+r_{2}t_{2}>0$,

> IsMaxInIntervalTT$[n=2,t_{1},t_{2},{\cal R}]$(${\cal X},m_{1},m_{2}$):
> Decide if there exists a partition of ${\cal X}$ among two machines in which
> the completion time of every machine $i$ is at most $(1+t_{i})S$ where
> machine $q$ processes exactly $m_{q}$ jobs.

If such a partition exists, we call it a _$tt$ -feasible_ partition. We also
need a variant with a critical coordinate,

> UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$(${\cal X},m_{1},m_{2}$): Minimize
> $\max(b_{1},b_{2})$ subject to $b_{i}\leq(1+t_{i})\cdot S$ where
> $b_{1},b_{2}$ are completion time of machine in a $2$-way partition of
> ${\cal X}$ where machine $q$ processes exactly $m_{q}$ jobs.

We prove in Section B.2 that UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$ has an
FPTAS. Using similar techniques as in Algorithm 1, we show a polynomial time
algorithm for IsMaxInIntervalTT$[n=2,t_{1},t_{2},{\cal R}]$.

####  3.2.3 Polynomial time algorithm for
IsMaxInIntervalTT$[n=2,t_{1},t_{2},{\cal R}]$

######  Lemma 5.

Let $\epsilon=(r_{1}t_{1}+r_{2}t_{2})/(r_{1}+r_{2})>0$. If for every
$i\in\\{1,2\\}$ and $j=2/i$ , FPTAS$($UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal
R}]$$({\cal X},m_{1},m_{2})$, $\epsilon)>(1+t_{j})\cdot S$, then there is no
$tt$-feasible $2$-way partition of ${\cal X}$.

###### Proof.

First set $i=1$ and $j=2$. If FPTAS$($UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal
R}]$$({\cal X},m_{1},m_{2})$, $\epsilon)$ is greater than $r_{2}(1+t_{2})\cdot
S$, by definition of FPTAS, UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$$({\cal
X},m_{1},m_{2})>r_{2}(1+t_{2})\cdot S/(1+\epsilon)=r_{2}(1+t_{2})\cdot
S/(1+(r_{1}t_{1}+r_{2}t_{2})/(r_{1}+r_{2}))=r_{2}\frac{1+t_{2}}{r_{1}(1+t_{1})+r_{2}(1+t_{2})}\cdot(r_{1}+r_{2})S$.

Similarly, for $i=2$ and $j=1$, we have UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal
R}]$$({\cal
X},m_{1},m_{2})>r_{1}\frac{1+t_{1}}{r_{1}(1+t_{1})+r_{2}(1+t_{2})}\cdot(r_{1}+r_{2})S$.
Therefore, in any partition, if $r_{1}b_{1}\leq r_{1}(1+t_{1})\cdot S$ then,
$r_{2}b_{2}>r_{2}\frac{1+t_{2}}{r_{1}(1+t_{1})+r_{2}(1+t_{2})}\cdot(r_{1}+r_{2})S$,
and if $r_{2}b_{2}\leq r_{2}(1+t_{2})\cdot S$ then,
$r_{1}b_{1}>r_{1}\frac{1+t_{1}}{r_{1}(1+t_{1})+r_{2}(1+t_{2})}\cdot(r_{1}+r_{2})S$.
Since a $tt$-feasible partition requires both $r_{1}b_{1}\leq
r_{1}(1+t_{1})\cdot S$ and $r_{2}b_{2}\leq r_{2}(1+t_{2})\cdot S$, we must
have

$\displaystyle r_{1}b_{1}+r_{2}b_{2}$
$\displaystyle>r_{1}\frac{1+t_{1}}{r_{1}(1+t_{1})+r_{2}(1+t_{2})}\cdot(r_{1}+r_{2})S+r_{2}\frac{1+t_{2}}{r_{1}(1+t_{1})+r_{2}(1+t_{2})}\cdot(r_{1}+r_{2})S$
$\displaystyle=\frac{r_{1}(1+t_{1})+r_{2}(1+t_{2})}{r_{1}(1+t_{1})+r_{2}(1+t_{2})}\cdot(r_{1}+r_{2})S$
$\displaystyle=(r_{1}+r_{2})S,$

by the problem definition, the sum $r_{1}b_{1}+r_{2}b_{2}=(r_{1}+r_{2})S$, so
we reach a contradiction. ∎

We are ready to design our algorithm.

Algorithm 2 IsMaxInIntervalTT$[n=2,t_{1},t_{2},{\cal R}]$

1:for $i\in\\{1,2\\}$ do

2: Set $j:=2/i$.

3: Run the FPTAS for UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$(${\cal
X},m_{1},m_{2}$) with critical coordinate $i$ and
$\epsilon=(r_{1}t_{1}+r_{2}t_{2})/(r_{1}+r_{2})$.

4: Let $b_{j}$ the completion time of machine $j$ as returned by this FPTAS.

5: if $b_{j}\leq(1+t_{j})\cdot S$ then

6: return “yes”

7: end if

8:end for

9:return “no”

######  Theorem 7.

For any rationals $t_{1},t_{2}$ and every speed ratios $r_{1},r_{2}$, with
$r_{1}t_{1}+r_{2}t_{2}>0$, Algorithm 2 solves the problem
IsMaxInIntervalTT$[n=2,t_{1},t_{2},{\cal R}]$(${\cal X},m_{1},m_{2}$) in time
$O(\text{poly}(m,\log{S},(r_{1}+r_{2})/(r_{1}t_{1}+r_{2}t_{2})))$, where
$m=m_{1}+m_{2}$ is the number of input jobs in ${\cal X}$.

###### Proof.

The run-time of Algorithm 2 is dominated by the run-times of the two FPTAS-s
for the problem UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$, which by definition
of FPTAS is in $O(\text{poly}(m,\log{S},1/\epsilon))$, which is
$O(\text{poly}(m,\log{S},(r_{1}+r_{2})/(r_{1}t_{1}+r_{2}t_{2})))$ (we show in
Section B.3.2 that the exact run-time is
$O(\frac{m}{r_{1}t_{1}+r_{2}t_{2}}\log{S})$).

If $b_{j}$, the returned completion time of one of the
FPTAS(UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$(${\cal X},m_{1},m_{2}$),
$\epsilon=(r_{1}t_{1}+r_{2}t_{2})/(r_{1}+r_{2})$), is at most $(1+t_{j})\cdot
S$, then the partition found by the FPTAS is $tt$-feasible, so Algorithm 2
answers “yes” correctly (the number of jobs in the machines is respected by
the FPTAS). Otherwise, by Lemma 5, there is no $tt$-feasible partiton, and
Algorithm 2 answers “no” correctly. ∎

In the following, we show how to use IsMaxInIntervalTT$[n=2,t_{1},t_{2},{\cal
R}]$ to schedule the $m_{1}+m_{2}$ smallest jobs in $B$ among machines 1,2.

####  3.2.4 Algorithm for machine 1 and 2

We use the following notation:

  * –

$B_{1:2}$ is the list of $m_{1}+m_{2}$ smallest jobs in $B$ (where $B$ is the
set of big jobs in ${\cal X}$).

  * –

$S_{1:2}:=(\sum_{j\in B_{1:2}}x_{j})/(r_{1}+r_{2})$, so that the sum of
lengths of all jobs in $B_{1:2}$ is $(r_{1}+r_{2})S_{1:2}$.

  * –

$M_{1:2}:=(\max_{j\in B_{1:2}}x_{j})/A$, so that the longest job in $B_{1:2}$
is $AM_{1:2}$.

Construct a new set $\overline{B_{1:2}}$, by replacing the length $x$ of each
job in $B_{1:2}$ by its “inverse”, defined by $\overline{x}:=AM_{1:2}-x$.
Since all jobs in $B_{1:2}$ are big jobs, every inverse length is at most
$2AS\epsilon$, since $\frac{tAS}{n-2}\geq AM\geq AM_{1:2}$. Let
$\overline{S_{1:2}}$ be the sum of inverses divided by $r_{1}+r_{2}$, so that
the sum of inverses by $(r_{1}+r_{2})\overline{S_{1:2}}$.

Given a $t$-feasible partition of $B_{1:2}$ with completion times
$b_{1},b_{2}$ and with $m_{1}$ jobs in machine $1$ and $m_{2}$ jobs in machine
$2$, denote the completion times of the corresponding partition of
$\overline{B_{1:2}}$ by $\overline{b_{1}}$ and $\overline{b_{2}}$,
respectively. Since machines $1$ and $2$ contain $m_{1},m_{2}$ jobs
respectively,

$\displaystyle r_{1}\overline{b_{1}}$ $\displaystyle=m_{1}\cdot
AM_{1:2}-r_{1}b_{1}$ $\displaystyle\text{ and, }r_{2}\overline{b_{2}}$
$\displaystyle=m_{2}\cdot AM_{1:2}-r_{2}b_{2}$
$\displaystyle(r_{1}+r_{2})\overline{S_{1:2}}$
$\displaystyle=r_{1}\overline{b_{1}}+r_{2}\overline{b_{2}}=(m_{1}+m_{2})\cdot
AM_{1:2}-(r_{1}+r_{2})S_{1:2}$ $\displaystyle\overline{S_{1:2}}$
$\displaystyle=\frac{m_{1}+m_{2}}{r_{1}+r_{2}}\cdot AM_{1:2}-S_{1:2}$
$\displaystyle=\frac{m_{b}+n-2}{A}\cdot AM_{1:2}-S_{1:2}$
$\displaystyle=(m_{b}+n-2)\cdot M_{1:2}-S_{1:2}.~{}~{}~{}~{}~{}~{}\text{(by
property \eqref{prop:litems})}$ (1)

Now,

$\displaystyle b_{1}\leq(1+t)S\iff$ $\displaystyle r_{1}\overline{b_{1}}\geq
m_{1}AM_{1:2}-r_{1}(1+t)S$ $\displaystyle\iff$ $\displaystyle
r_{2}\overline{b_{2}}\leq(r_{1}+r_{2})\overline{S_{1:2}}-m_{1}AM_{1:2}+r_{1}(1+t)S\iff$
$\displaystyle\overline{b_{2}}\leq\overline{S_{1:2}}+\frac{r_{1}\overline{S_{1:2}}-m_{1}AM_{1:2}}{r_{2}}+\frac{r_{1}}{r_{2}}(1+t)S$
$\displaystyle~{}~{}~{}=\overline{S_{1:2}}+\frac{1}{r_{2}}\cdot(r_{1}\frac{m_{1}+m_{2}}{r_{1}+r_{2}}\cdot
AM_{1:2}-r_{1}S_{1:2}-m_{1}AM_{1:2}+r_{1}(1+t)S)$
$\displaystyle~{}~{}~{}=\overline{S_{1:2}}+\frac{1}{r_{2}}\cdot((r_{1}\frac{m_{1}+m_{2}}{r_{1}+r_{2}}-m_{1})AM_{1:2}+r_{1}(S+tS-
S_{1:2}))$
$\displaystyle~{}~{}~{}=\overline{S_{1:2}}+\frac{1}{r_{2}}\cdot(\frac{r_{1}m_{1}+r_{1}m_{2}-r_{1}m_{1}-r_{2}m_{1}}{r_{1}+r_{2}}AM_{1:2}+r_{1}(S+tS-
S_{1:2}))$
$\displaystyle~{}~{}~{}=\overline{S_{1:2}}+\frac{1}{r_{2}}\cdot(\frac{r_{1}m_{2}-r_{2}m_{1}}{r_{1}+r_{2}}AM_{1:2}+r_{1}(S+tS-
S_{1:2}))$
$\displaystyle~{}~{}~{}=\overline{S_{1:2}}\cdot(1+\frac{1}{r_{2}\overline{S_{1:2}}}\cdot(\frac{r_{1}m_{2}-r_{2}m_{1}}{r_{1}+r_{2}}AM_{1:2}+r_{1}(S+tS-
S_{1:2}))),$

and similarly, $b_{2}\leq(1+t)S$ holds iff
$\overline{b_{1}}\leq\overline{S_{1:2}}\cdot(1+\frac{1}{r_{1}\overline{S_{1:2}}}\cdot(\frac{r_{2}m_{1}-r_{1}m_{2}}{r_{2}+r_{1}}AM_{1:2}+r_{2}(S+tS-
S_{1:2}))$. So the problem of finding a $t$-feasible partition of $B_{1:2}$
with $m_{1}$ jobs in machine $1$ and $m_{2}$ jobs in machine $2$ is equivalent
to the problem of finding a $\overline{tt}$-feasible partition of
$\overline{B_{1:2}}$ with $m_{1}$ jobs in machine $1$ and $m_{2}$ jobs in
machine $2$, where

$\displaystyle\overline{t_{1}}=\frac{1}{r_{1}\overline{S_{1:2}}}\cdot\left[\frac{r_{2}m_{1}-r_{1}m_{2}}{r_{2}+r_{1}}AM_{1:2}+r_{2}(S+tS-
S_{1:2})\right],$
$\displaystyle\overline{t_{2}}=\frac{1}{r_{2}\overline{S_{1:2}}}\cdot\left[\frac{r_{1}m_{2}-r_{2}m_{1}}{r_{1}+r_{2}}AM_{1:2}+r_{1}(S+tS-
S_{1:2})\right].$

By Theorem 7, this problem can be solved in
$O(\text{poly}(m,(r_{1}+r_{2})/(r_{1}\overline{t_{1}}+r_{2}\overline{t_{2}}),\log{S}))$
time. We now show that
$(r_{1}+r_{2})/(r_{1}\overline{t_{1}}+r_{2}\overline{t_{2}})$ is polynomial in
the problem size. By adding the above two equations, we get

$\displaystyle\overline{S_{1:2}}\cdot(r_{1}\overline{t_{1}}+r_{2}\overline{t_{2}})$
$\displaystyle:=\frac{r_{1}m_{2}-r_{2}m_{1}}{r_{1}+r_{2}}AM_{1:2}+r_{1}(S+tS-
S_{1:2})$
$\displaystyle+\frac{r_{2}m_{1}-r_{1}m_{2}}{r_{2}+r_{1}}AM_{1:2}+r_{2}(S+tS-
S_{1:2})$ $\displaystyle=(r_{1}+r_{2})(S+tS-S_{1:2}),$

so
$(r_{1}+r_{2})/(r_{1}\overline{t_{1}}+r_{2}\overline{t_{2}})=\overline{S_{1:2}}/(S+tS-
S_{1:2})$, so the run-time is polynomial in:
$T:=\frac{\overline{S_{1:2}}}{S+tS-S_{1:2}}$

The numerator is given by (1). We now give a lower bound the denominator.

By Lemma 4(d), in the not-almost-full machines $3,\dots,n$, there are
$m_{3},\dots,m_{n}$ big-jobs that are at least as large as $AM_{1:2}$ (in
addition to some small-jobs). Therefore, the sum $AS$ of all job lengths
satisfies $AS\geq(r_{1}+r_{2})S_{1:2}+\sum_{i=3}^{n}m_{i}\cdot AM_{1:2}$,
which implies that

$\displaystyle S-S_{1:2}$
$\displaystyle\geq\frac{(r_{1}+r_{2})S_{1:2}}{A}+\sum_{i=3}^{n}m_{i}M_{1:2}-S_{1:2}$
$\displaystyle=\frac{(r_{1}+r_{2})S_{1:2}-AS_{1:2}}{A}+\sum_{i=3}^{n}m_{i}M_{1:2}$
$\displaystyle=\frac{(r_{1}+r_{2}-A)S_{1:2}}{A}+\sum_{i=3}^{n}m_{i}M_{1:2}$
$\displaystyle=-\frac{\sum_{i=3}^{n}r_{i}S_{1:2}}{A}+\sum_{i=3}^{n}m_{i}M_{1:2}$
$\displaystyle=\frac{\sum_{i=3}^{n}m_{i}}{A}AM_{1:2}-\frac{\sum_{i=3}^{n}r_{i}}{A}S_{1:2}$

Therefore,

$\displaystyle S-S_{1:2}+tS$
$\displaystyle\geq\frac{\sum_{i=3}^{n}m_{i}}{A}AM_{1:2}-\frac{\sum_{i=3}^{n}r_{i}}{A}S_{1:2}+tS$
$\displaystyle\geq\frac{\sum_{i=3}^{n}m_{i}+(n-2)}{A}AM_{1:2}-\frac{\sum_{i=3}^{n}r_{i}}{A}S_{1:2}$
(since $d\geq n-2$, $tS=dM\geq(n-2)M_{1:2}$)
$\displaystyle=\frac{\sum_{i=3}^{n}(m_{i}+1)}{A}AM_{1:2}-\frac{\sum_{i=3}^{n}r_{i}}{A}S_{1:2}$
$\displaystyle=\frac{\sum_{i=3}^{n}\frac{r_{i}}{A}(m_{b}+n-2)}{A}AM_{1:2}-\frac{\sum_{i=3}^{n}r_{i}}{A}S_{1:2}~{}\text{(by
property \eqref{prop:litems})}$
$\displaystyle=\frac{(m_{b}+n-2)\cdot\sum_{i=3}^{n}r_{i}}{A}M_{1:2}-\frac{\sum_{i=3}^{n}r_{i}}{A}S_{1:2}$
$\displaystyle=\frac{\sum_{i=3}^{n}r_{i}}{A}\cdot\left((m_{b}+n-2)M_{1:2}-S_{1:2}\right).$

Now, we substitute the numerator and the lower bound for the denominator:

$\displaystyle T\leq$
$\displaystyle\frac{(m_{b}+n-2)M_{1:2}-S_{1:2}}{\frac{\sum_{i=3}^{n}r_{i}}{A}\cdot((m_{b}+n-2)M_{1:2}-S_{1:2})}=\frac{A}{\sum_{i=3}^{n}r_{i}},$

which is considered a fixed constant by assumption. So $T\in O(1)$ and the
sub-problem can be decided in time $O(\text{poly}(m,\allowbreak\log{S}))$.

####  3.2.5 Complete algorithm

We are now ready to present the complete algorithm for
IsMaxInIntervalD$[n,d,{\cal R}]$, in Algorithm 3.

Algorithm 3 IsMaxInIntervalD$[n,d,{\cal R}]$ (complete algorithm)

1:$t\longleftarrow dM/S$ and $\epsilon\longleftarrow t/(4An^{2}m^{2})$.

2:for $i\in\\{1,\dots,n\\}$ do

3: If FPTAS$($UniMinMaxCC$[n,t,i,{\cal R}]$$({\cal X})$,
$\epsilon)\leq(1+t)\cdot S$, return “yes”.

4:end for

5:$B\longleftarrow$ $\big{\\{}x\in{\cal X}\mid
x>AS(\frac{t}{n-2}-2\epsilon)\big{\\}}$ $\triangleright$ big jobs

6:$m_{b}\longleftarrow|B|$

7:for every pair $i,j$ of machines do $\triangleright$ we check whether there
is a partition in which $i$ and $j$ are the almost-full machines

8: $m_{1}\longleftarrow r_{i}\cdot(m_{b}+n-2)/A$, $m_{2}\longleftarrow
r_{j}\cdot(m_{b}+n-2)/A$. $\triangleright$ by property (e)

9: If $m_{1}$ or $m_{2}$ is not an integer, skip to next iteration.

10: $B_{1:2}\longleftarrow$ the $m_{1}+m_{2}$ smallest jobs in $B$.
$\triangleright$ break ties arbitrarily

11: $B_{3..n}\longleftarrow{\cal X}\setminus B_{1:2}$. $\triangleright$
$m_{k}=r_{k}\cdot(m_{b}+n-2)/A-1$ big jobs for $k\in\\{3,\dots,n\\}$ and
$m-m_{b}$ small jobs

12: $(b_{3},\ldots,b_{n})\longleftarrow$ FPTAS (UniMinMax$[n-2,{\cal
R}_{3..n}]$($B_{3..n}$), $\epsilon$) $\triangleright$ an $(n-2)-$way partition
of $B_{3..n}$

13: If $\max(b_{3},\ldots,b_{n})>(1+t)S$, skip to next iteration.

14: Look for a feasible partition for machines $i,j$ as explained in Section
3.2.4.

15: If a feasible partition is found, return “yes”.

16:end for

17:Return “no”.

######  Theorem 8 (Theorem 4).

For any fixed integer $n\geq 3$ and rational number $d\geq n-2$, Algorithm 3
solves IsMaxInIntervalD$[n,d,{\cal R}]$(${\cal X}$) in
$O(\text{poly}(m,\log{S}))$ time, where $m$ is the number of jobs in ${\cal
X}$, and $S$ is the average completion time.

###### Proof.

If Algorithm 3 answers “yes”, then clearly a $t$-feasible partition exists. To
complete the correctness proof, we have to show that the opposite is true as
well.

Suppose there exists a $t$-feasible partition of ${\cal X}$. If the partition
has at most one almost-full machine (say machine $i$), then by Lemma 3, it is
found by the FPTAS in step 3 in iteration $i$ of the for loop. Otherwise, the
partition must have at least two almost-full machines, and there exists a
$t$-feasible partition satisfying the properties of Lemma 4.

The for loop checks all possible pairs of machines, and checks whether these
two machines can be the two almost-full machines in a $t$-feasible partition.
By (e), the number of big-jobs in machine 1 and 2 is equal to
$r_{1}\cdot(m_{b}+n-2)/A$ and $r_{2}\cdot(m_{b}+n-2)/A$ and it must be an
integer. By properties (a) and (b), there exists a partition of $B_{3..n}$
into $n-2$ machines $3,\ldots,n$ which are not almost-full. By Lemma 2, the
FPTAS in step 12 finds a partition with $\max(b_{3},\ldots,b_{n})\leq(1+t)S$.
The final steps, regarding the partition of $B_{1:2}$, are justified by the
discussion at Section 3.2.2. The complete running time
$O(\text{poly}(m,\log{S}))$ of Algorithm 3 is justified by the running time of
the FPTAS for UniMinMax$[n,{\cal R}]$, UniMinMaxCC$[n,t,i,{\cal R}]$ and for
UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$. Note that $AS/AM\leq m$ since it is
the sum of all jobs divided by the longest job. Therefore,
$1/t=S/dM=AS/AM\cdot 1/d\leq m/d=O(m)$ since $d$ is fixed. Also, note that
$1/\epsilon$ depends on $A,n$ (which are fixed) $1/t$ and $m$ so,
$1/\epsilon=O(m)$. The exact running time, $O(m^{4}\log{S})$, is detailed in
Section B.3.3. ∎

###  3.3 Hardness for $n\geq 3$ machines and $d<n-2$

The following theorem complements the previous subsection.

######  Theorem 9 (=Theorem 5).

For any fixed $n\geq 3$ and positive rational number $d<n-2$, the
IsMaxInIntervalD$[n,d,{\cal R}]$(${\cal X}$) problem is NP-complete, and this
holds even for the special case of identical machines ($r_{i}=1$ for all $i$).

###### Proof.

Given an $n$-way partition of $m$ jobs, summing the job lengths in each
machine allows us to check whether the partition is $d$-possible in linear
time. So, the problem is in NP.

We prove that the special case of identical machines is NP-Hard by reduction
from the Equal-Cardinality Partition problem, proved to be NP-hard in [1]:
given a list with an even number of integers, decide if they can be
partitioned into two subsets with the same sum and the same cardinality. We
consider the items in the Equal-Cardinality Partition problem as jobs, and the
bins as machines.

Given an instance ${\cal X}_{1}$ of Equal-Cardinality Partition, denote the
number of jobs in ${\cal X}_{1}$ by $2m^{\prime}$. Define $M$ to be the sum of
job lengths in ${\cal X}_{1}$ divided by $2n(1-\frac{d}{n-2})$, so that the
sum of job lengths in ${\cal X}_{1}$ is $2n\left(1-\frac{d}{n-2}\right)M$
(where $n$ and $d$ are the parameters in the theorem statement). We assume
w.l.o.g. that all job lengths in ${\cal X}_{1}$ are at most
$n(1-\frac{d}{n-2})M$, since if some job is longer than the average completion
time, the answer is necessarily “no”.

Construct an instance ${\cal X}_{2}$ of the Equal-Cardinality Partition
problem by replacing each job $x$ in ${\cal X}_{1}$ by $nM-x$. So ${\cal
X}_{2}$ contains $2m^{\prime}$ jobs with lengths between $n(\frac{d}{n-2})M$
and $nM$. Their sum, which we denote by $2S^{\prime}$, satisfies

$\displaystyle 2S^{\prime}=2m^{\prime}\cdot
nM-2n\left(1-\frac{d}{n-2}\right)M=2n\left(m^{\prime}-1+\frac{d}{n-2}\right)M.$

Clearly, ${\cal X}_{1}$ has an equal-sum equal-cardinality partition (with
completion times $n\left(1-\frac{d}{n-2}\right)M$) if and only if ${\cal
X}_{2}$ has an equal-sum equal-cardinality partition (with completion times
$S^{\prime}=n\left(m^{\prime}-1+\frac{d}{n-2}\right)M$).

We now construct an instance ${\cal X}_{3}$ of IsMaxInIntervalD$[n,d,{\cal
R}]$, with $r_{i}=1$ for all $i\in[n]$, such that $A=n$. We add to ${\cal
X}_{2}$ some $(n-2)(m^{\prime}-1)$ jobs of size $nM$. Note that $nM$ is indeed
the longest job length in ${\cal X}_{3}$. Denote the sum of job lengths in
${\cal X}_{3}$ by $nS=AS$. Then

$\displaystyle nS$ $\displaystyle=2S^{\prime}+(n-2)(m^{\prime}-1)\cdot nM$
$\displaystyle=n\left(2(m^{\prime}-1)+\frac{2d}{n-2}+(n-2)(m^{\prime}-1)\right)\cdot
M$ $\displaystyle=n\left(n(m^{\prime}-1)+\frac{2d}{n-2}\right)M;$
$S+dM=\left(n(m^{\prime}-1)+\frac{2d}{n-2}+d\right)M=\left(n(m^{\prime}-1)+\frac{nd}{n-2}\right)M=S^{\prime},$

so a partition of ${\cal X}_{3}$ is $d$-possible if and only if the completion
time of each of the $n$ machines in the partition is at most
$S+dM=S^{\prime}$.

We now prove that if ${\cal X}_{2}$ has an equal-sum equal-cardinality
partition, then the corresponding instance (${\cal X}_{3},d$) has a
$d$-possible partition, and vice versa. If ${\cal X}_{2}$ has an equal-sum
partition, then the jobs of ${\cal X}_{2}$ can be partitioned into two
machines of sum $S^{\prime}$, and the additional $(n-2)(m^{\prime}-1)$ jobs
can be allocated into $n-2$ machines of $m^{\prime}-1$ jobs each. Note that
the sum of these jobs is

$\displaystyle(m^{\prime}-1)\cdot nM=n(m^{\prime}-1)M$
$\displaystyle=S-\frac{2}{n-2}dM<S+dM=S^{\prime},$ (2)

so the resulting partition is a $d$-possible partition of ${\cal X}_{3}$.
Conversely, suppose ${\cal X}_{3}$ has a $d$-possible partition. Let us
analyze its structure.

Since the partition is $d$-possible, the total length of jobs allocated to
every pair of machines is at most $2(S+dM)$. So the total length of jobs
allocated to every $n-2$ machines is at least $nS-2(S+dM)=(n-2)S-2dM$. Since
the longest $(n-2)(m^{\prime}-1)$ jobs in ${\cal X}_{3}$ sum up to exactly
$(n-2)S-2dM$ by (2), every $n-2$ machines must process at least
$(n-2)(m^{\prime}-1)$ jobs. Since ${\cal X}_{3}$ has
$(n-2)(m^{\prime}-1)+2m^{\prime}$ jobs overall, $n-2$ machines must process
exactly $(n-2)(m^{\prime}-1)$ jobs, such that each job length must be $nM$,
and their sum must be $(n-2)S-2dM$. The other two machines process together
$2m^{\prime}$ jobs with total length $2(S+dM)$, so each of these machines must
have a completion time of exactly $S+dM$. Since $(m^{\prime}-1)\cdot nM<S+dM$
by (2), each of these two machines must process exactly $m^{\prime}$ jobs.

These latter two machines contain an equal-sum equal-cardinality partition for
${\cal X}_{2}$. This construction is done in polynomial time, completing the
reduction. ∎

##  4 Partition with split jobs

We now return to the optimization problem UniMinMaxSplit$[n,s,{\cal R}]$. We
solve it using the following decision problem. For a fixed number $n\geq 2$ of
machines, given a list ${\cal X}$, the number of split jobs
$s\in\\{0,\ldots,m\\}$ and a rational number $t\geq 0$, define:
IsMaxInIntervalSplit$[n,s,t,{\cal R}]$(${\cal X}$): Decide if there exists a
partition of ${\cal X}$ among $n$ machines with speeds ${\cal R}$, in which at
most $s$ jobs are split, such that $\max(b_{1},\ldots,b_{n})\leq(1+t)S$. The
special case $t=0$ corresponds to the UniMinMaxSplit$[n,s,{\cal R}]$(${\cal
X}$) problem. The following Lemma shows that, w.l.o.g., we can consider only
the longest jobs for splitting.

######  Lemma 6.

For every partition with $s\in\mathbb{N}$ split jobs and completion times
$b_{1},\ldots,b_{n}$, there exists a partition with the same completion times
$b_{1},\ldots,b_{n}$ in which only the $s$ _longest_ jobs are split.

###### Proof.

Consider a partition in which some job with length $x$ is split between two or
more machines, whereas some job with length $y>x$ is allocated entirely to
some machine $i$. Construct a new partition as follows: first move job $x$ to
machine $i$; second remove from machine $i$, a fraction $\frac{x}{y}$ of job
$y$; and finally split that fraction of job $y$ among the other machines, in
the same proportions as the previous split of job $x$. Each machine processes
exactly the same total job length as before. Therefore, all completion times
remain the same. Repeat the argument until only the longest jobs are split. ∎

######  Theorem 10.

For any fixed integers $n\geq 2$ and $d\geq 0$, there is a polynomial-time
reduction from IsMaxInIntervalD$[n,d,r_{i}\equiv 1]$(${\cal X}$) to
IsMaxInIntervalSplit$[n,d,t=0,r_{i}\equiv 1]$(${\cal X}$) (that is,
IsMaxInIntervalSplit$[n,s,t,r_{i}\equiv 1]$(${\cal X}$) with $s=d$ and $t=0$).

###### Proof.

Given an instance ${\cal X}$ of IsMaxInIntervalD$[n,d,r_{i}\equiv 1]$(${\cal
X}$), construct an instance ${\cal X}^{\prime}$ of
IsMaxInIntervalSplit$[n,d,t=0,r_{i}\equiv 1]$(${\cal X}^{\prime}$) by adding
$d$ jobs of size $AM=nM$ (since $r_{i}\equiv 1$ implies $A=n$), where $nM$ is
the size of the longest job in ${\cal X}$.

First, assume that ${\cal X}$ has a $d$-possible partition. Then there are $n$
machines with completion time at most $S+dM$. Take the $d$ added jobs of size
$nM$ and add them to the machines, possibly splitting some jobs between
machines, such that the completion time of each machine becomes exactly
$S+dM$. This is possible because the sum of the jobs in ${\cal X}^{\prime}$ is
$nS+dnM=n(S+dM)$. The result is a $0$-feasible partition of ${\cal
X}^{\prime}$ with at most $d$ split jobs.

Second, assume that ${\cal X}^{\prime}$ has a $0$-feasible partition with at
most $d$ split jobs. Then there are $n$ machines with sum exactly $S+dM$. By
Lemma 6, we can assume the split jobs are the largest ones, which are the $d$
added jobs of size $nM$. Remove these jobs to get a partition of ${\cal X}$.
The completion time in each machine is now at most $S+dM$, so the partition is
$d$-possible. This construction is done in polynomial time, which completes
the proof. ∎

######  Corollary 1 (= Theorem 2).

For every fixed integers $n\geq 3$ and $s\in\\{0,\dots,n-3\\}$, the problem
IsPerfectSplit$[n,s,{\cal R}]$ is NP-hard, and
IsMaxInIntervalSplit$[n,s,t=0,{\cal R}]$(${\cal X}$) $\equiv$
IsPerfectSplit$[n,s,{\cal R}]$(${\cal X}$) is NP-complete, and this holds even
for the special case of identical machines ($r_{i}=1$ for all $i$).

###### Proof.

Theorem 9 and Theorem 10 together imply that both problems are NP-hard. The
problem IsPerfectSplit$[n,s,{\cal R}]$(${\cal X}$) is in NP since given a
partition, summing the sizes of the jobs (or jobs fractions) in each machine
lets us to check in linear time whether the partition has equal completion
times. ∎

######  Theorem 11.

For any fixed integers $n\geq 2,s\geq 0$ and rational $t\geq 0$, there is a
polynomial-time reduction from IsMaxInIntervalSplit$[n,s,t,{\cal R}]$(${\cal
X}$), to IsMaxInIntervalD$[n,d,{\cal R}]$(${\cal X}$) for some rational number
$d\geq s$.

###### Proof.

Given an instance ${\cal X}$ of IsMaxInIntervalSplit$[n,s,t,{\cal R}]$(${\cal
X}$), denote the sum of all job lengths in ${\cal X}$ by $AS$ and the longest
job length by $AM$ where $S,M\in\mathbb{Q}$. Construct an instance ${\cal
X}^{\prime}$ of IsMaxInIntervalD$[n,d,{\cal R}]$(${\cal X}^{\prime}$) by
removing the $s$ longest jobs from ${\cal X}$. Denote the sum of remaining
jobs by $AS^{\prime}$ for some $S^{\prime}\leq S$, and the longest remaining
job length by $AM^{\prime}$ for some $M^{\prime}\leq M$. Note that the size of
every removed job is between $AM^{\prime}$ and $AM$, so $sM^{\prime}\leq
S-S^{\prime}\leq sM$. Set $d:=(S+tS-S^{\prime})/M^{\prime}$, so
$S^{\prime}+dM^{\prime}=S+tS$. Note that $d\geq(S-S^{\prime})/M^{\prime}\geq
s$.

First, assume that ${\cal X}$ has a $t$-feasible partition with $s$ split
jobs. By Lemma 6, we can assume that only the $s$ longest jobs are split.
Therefore, removing the $s$ longest jobs results in a partition of ${\cal
X}^{\prime}$ with no split jobs, where the completion time in each machine is
at most $S+tS=S^{\prime}+dM^{\prime}$. This is a $d$-possible partition of
${\cal X}^{\prime}$.

Second, assume that ${\cal X}^{\prime}$ has a $d$-possible partition. In this
partition, each machine completion time is at most
$S^{\prime}+dM^{\prime}=S+tS$, so it is a $t$-feasible partition of ${\cal
X}^{\prime}$. To get a $t$-feasible partition of ${\cal X}$, take the $s$
previously-removed jobs and add them to the machines, possibly splitting some
jobs between machines, such that the completion time in each machine remains
at most $S+tS$. This is possible because the sum of all jobs is $AS\leq
A(S+tS)$. This construction is done in polynomial time, which completes the
proof. ∎

Combining Theorem 11 with Theorem 8 provides:

######  Corollary 2.

For any fixed $n\geq 3,s\geq n-2$ and rational $t\geq 0$,
IsMaxInIntervalSplit$[n,s,t,{\cal R}]$(${\cal X}$) can be solved in polynomial
time.

Finally, for any fixed integer $n\geq 2$ and $s\geq n-2$, we can solve the
UniMinMaxSplit$[n,s,{\cal R}]$(${\cal X}$) optimization problem by using
binary search on the parameter $t$ of IsMaxInIntervalSplit$[n,s,t,{\cal
R}]$(${\cal X}$). We first prove a property of the optimal completion time of
UniMinMaxSplit$[n,s,{\cal R}]$(${\cal X}$).

######  Lemma 7.

The optimal value of an UniMinMaxSplit$[n,s,{\cal R}]$(${\cal X}$) instance is
either a perfect partition (that is, all completion times are equal to the
average completion time $S$) or equal to $q/r_{i}$, where $q$ is an integer
and $r_{i}\in{\cal R}$.

###### Proof.

Let OPT be the maximum completion time in an optimal partition of ${\cal X}$
with $s$ split jobs. If OPT is not equal to $q/r_{i}$, where $q$ is an integer
and $r_{i}\in{\cal R}$, then the fractional part of OPT must come from a split
job (since the non-split jobs have integer sizes). Assuming that the partition
is not perfect, there is at least one machine with a completion time smaller
than OPT. Move a small fraction of the split job from all machines with
completion time OPT to a machine with sum smaller than OPT. This yields a
partition with a smaller maximum completion time and the same set of split
jobs — a contradiction to optimality. ∎

Now, we show how to use binary search in order to solve the
UniMinMaxSplit$[n,s,{\cal R}]$(${\cal X}$) problem. The idea is to execute the
IsMaxInIntervalSplit$[n,s,t,{\cal R}]$(${\cal X}$) algorithm several times,
trimming the parameter $t$ at each execution in a binary search style. When
$t=A-1$, the answer to IsMaxInIntervalSplit$[n,s,t,{\cal R}]$(${\cal X}$) is
always “yes”, since even if we process all jobs in a single machine, its sum
is $AS=(1+t)S$. Moreover, by Lemma 7, the optimal completion time value of
UniMinMaxSplit$[n,s,{\cal R}]$(${\cal X}$) is either equal to $q/r_{i}$, where
$q$ is an integer and $r_{i}\in{\cal R}$ or equal to $S$. Therefore, in
addition to considering the case where $t=0$, we only need to consider values
of $t$ that differ by at least $1/AS$, since if the completion times are not
equal to $S$ they are always equal to $q/r_{i}$, so they differ by at least
$1/A$. Therefore, at most $A^{2}S$ different values of $t$ have to be checked,
so the binary search requires at most $\log_{2}(A^{2}S)$ executions of
IsMaxInIntervalSplit$[n,s,t,{\cal R}]$(${\cal X}$). This is polynomial in the
size of the binary representation of the input.

######  Corollary 3 (=Theorem 1).

For any fixed integers $n\geq 3$ and $s\geq n-2$, the problem
UniMinMaxSplit$[n,s,{\cal R}]$(${\cal X}$) can be solved in polynomial time in
the size of the binary representation of its input.

###  4.1 An FPTAS for the case $s<n-2$

Although we provide a polynomial-time algorithm only for the case $s=n-2$, our
results suggest possible solutions for the general case too.

######  Theorem 12.

There exists an FPTAS for UniMinMaxSplit$[n,s,{\cal R}]$(${\cal X}$) for any
$n$ and $s$, given any rational $\epsilon$.

###### Proof.

Consider the following algorithm:

Algorithm 4 FPTAS(UniMinMaxSplit$[n,s,{\cal R}]$(${\cal X}$), $\epsilon$)

1:Let ${\cal X}_{1}:=$ the $s$ longest jobs in ${\cal X}$. Let ${\cal
X}_{2}:=$ the remaining jobs.

2:Solve FPTAS$($UniMinMax$[n,{\cal R}]$$({\cal X}_{2})$, $\epsilon)$.

3:Split the jobs in ${\cal X}_{1}$ among the machines such that the resulting
partition is as equal as possible.

The run time of the algorithm depends on FPTAS$($UniMinMax$[n,{\cal
R}]$$({\cal X}_{2})$, $\epsilon)$ so, it is polynomial in the length of the
input ${\cal X}$ and $1/\epsilon$. We now prove that Algorithm 4 is correct.
Let $OPT$ be the optimal solution of UniMinMaxSplit$[n,s,{\cal R}]$(${\cal
X}$) and $OPT_{2}$ be the optimal solution of UniMinMax$[n,{\cal R}]$$({\cal
X}_{2})$. By Lemma 6, we can assume that only the $s$ longest jobs are split.
By definition, FPTAS$($UniMinMax$[n,{\cal R}]$$({\cal X}_{2})$, $\epsilon)$
returns a partition of ${\cal X}_{2}$ where the largest completion time is at
most $(1+\epsilon)OPT_{2}$. After splitting the $s$ largest jobs in
${\mathcal{X}}$, if the algorithm outputs a perfect partition (with value
equal to $(\sum_{i\in{\cal X}}x_{i})/n$), then we are done. Otherwise, the
output of our algorithm must be equal to $(1+\epsilon)OPT_{2}$. This is
because, if the partition is not perfect, no part of the split jobs is
allocated to the machine with the largest completion time. Obviously,
$OPT_{2}\leq OPT$ since UniMinMaxSplit$[n,s,{\cal R}]$$({\cal X})$ has to
allocate the same whole jobs as UniMinMax$[n,{\cal R}]$$({\cal X}_{2})$, plus
$s$ additional split jobs. Therefore, Algorithm 4 returns a partition where
the largest completion time is at most $(1+\epsilon)OPT$. ∎

##  5 Experiments

What is the effect of the number of split jobs $s$ on the quality of the
optimal partition? We explored this question using experiments on random
instances. For simplicity, we used the identical machines version of the
problem, UniMinMaxSplit$[n,s,r_{i}\equiv 1]$(${\cal X}$). Since the problem is
NP-hard for $s<n-2$, we used a heuristic algorithm that we describe next.

###  5.1 An algorithm for every $n$ and $s$

Theorem 11 implies that we can solve any instance of
UniMinMaxSplit$[n,s,r_{i}\equiv 1]$$({\cal X})$ in the following way (see
Algorithm 5 for further details):

  1. 1.

Let ${\cal X}_{1}:=$ the $s$ longest jobs in ${\cal X}$. Let ${\cal X}_{2}:=$
the remaining jobs.

  2. 2.

Solve UniMinMax$[n,r_{i}\equiv 1]$$({\cal X}_{2})$.

  3. 3.

Split the jobs in ${\cal X}_{1}$ among the machines such that the resulting
partition is as equal as possible.

While UniMinMax$[n,r_{i}\equiv 1]$ is NP-hard, there are several heuristic
algorithms that can solve medium-sized instances in reasonable time [33]. We
are interested in algorithms based on state-space search, such as the Complete
Greedy Algorithm (CGA) [3]. This algorithm usually deals with bins and items,
in our work, equivalently, we use machines and jobs. CGA searches through all
partitions by adding to each machine the longest job not yet added to any
machine, so that machines with smaller completion time are prioritized. This
is done depth-first, meaning that the shorter jobs are shuffled between
different machines before longer jobs are. In addition to the heuristics that
make CGA run fast in practice, we add a new heuristic, specific to our
setting: we stop the search of a min-max partition of ${\cal X}_{2}$ whenever
it finds a solution in which the maximum completion time is at most
$S:=(\sum_{j\in{\cal X}}x_{j})/n$. This is because, by Lemma 6, we can then
divide the $s$ split jobs (the jobs in ${\cal X}_{1}$) among the machines and
get a perfect partition, in which every completion time equals $S$.

Algorithm 5 uses the following variant of Complete Greedy Algorithm (CGA): for
any input list $Y$ and upper bound $S$, it finds an $n$-way partition of $Y$
where the maximum completion time is at most $S$; if such a partition does not
exist, it finds a partition that minimizes the maximum completion time. While
its worst-case run-time is $O(2^{m})$, it runs fast on practical instances.
Note that other practical algorithms for optimal number partitioning could
also be used. Denote the $n$-way partition obtained by the CGA for a given $Y$
and a given upper bound $S$ by CGA($Y,S$).

Algorithm 5 UniMinMaxSplit$[n,s,r_{i}\equiv 1]$

1:Order the jobs such that $x_{1}\geq x_{2}\geq\cdots\geq x_{m}$

2:${\cal X}_{1}\longleftarrow\\{x_{1},\ldots,x_{s}\\}$ $\triangleright$ $s$
longest jobs in $\mathcal{X}$

3:$C\longleftarrow\sum_{j\in{\cal X}_{1}}x_{j}$

4:${\cal X}_{2}\longleftarrow X\setminus{\cal X}_{1}$.

5:$P_{2}\longleftarrow CGA({\cal X}_{2},S)$ $\triangleright$ optimal (min-max)
$n$-way partition of ${\cal X}_{2}$

6:The completion times in $P_{2}$ are $b_{1},\ldots,b_{n}$, and we order the
machines such that $b_{1}\leq\cdots\leq b_{n}$

7:for $i\longleftarrow 1$ to $n-1$ do

8: $B\longleftarrow i\cdot(b_{i+1}-b_{i})$ $\triangleright$ $B\geq 0$ since
$b_{i+1}\geq b_{i}$

9: if $C<B$ then $\triangleright$ Not enough split jobs to attain $b_{i+1}$

10: Break

11: else$\triangleright$ Use split jobs to increase $i$ lowest machines to
$b_{i+1}$

12: $C\longleftarrow C-B$

13: $b_{1},\cdots,b_{i}\longleftarrow b_{i+1}$

14: end if

15:end for

16:$b_{1},\cdots,b_{i}\longleftarrow b_{i}+C/i$

Based on Lemma 6, we may assume that only the $s$ longest jobs are split. We
remove these jobs from the instance, and keep their sum in the variable $C$.
Then we compute a min-max partition of the remaining jobs. Then, we try to
split the amount $C$ among the machines, such that the maximum completion time
remains as small as possible. In each iteration $i$, we use some of the split
jobs for increasing the sums in the $i$ smallest-completion-time machines such
that their completion-time becomes equal to the $(i+1)$-th machine. Finally,
we divide the remaining amount of split jobs equally among the lowest-
completion-time machines.

###  5.2 Experiments

In Figure 1 we show that the possibility of splitting brings the optimal
partition closer to the perfect partition, even when $s$ is much smaller than
$n-1$. We ran several instances of the UniMinMaxSplit$[n,s,r_{i}\equiv
1]$(${\cal X}$) optimization problem on random inputs drawn from an
exponential distribution, and from a uniform distribution with values between
$rM$ and $M$, for $r\in\\{0,0.5,0.9,0.99\\}$. The number of jobs was
$m\in\\{10,13,15\\}$, and number of bits in the job sizes was $16$ or $32$.
Finally, the number of machines was between 2 and 10, each one represented by
one curve in Figure 1. We ran seven different instances of each combination
and plotted the mean of all instances. The $x$-axis of the plot represents the
number of split jobs, the $y$-axis denotes the difference between the optimal
and the perfect partition in percent: $100\cdot(OPT-S)/S$.

Figure 1: Difference between the optimal and the perfect partition, in
percent. The plots show results for uniform distribution with $r=0$ (left
plot) and exponential distribution (right plot). In both plots $m=13$ and the
job lengths have 16 bits. The results for other values of the parameters are
qualitatively similar; we present them in Appendix D.

##  6 Conclusion and future directions

We presented two variants of the uniform machines scheduling problem. In the
language of machine scheduling, UniMinMaxSplit$[n,s,{\cal R}]$ corresponds to
find a schedule that minimizes the makespan on $n$ uniform machines when $s$
jobs can be split between the machines; IsMaxInIntervalD$[n,d,{\cal R}]$
corresponds to find a schedule in which the makespan is in a given interval.
It may be interesting to study these two variants for more general scheduling
problems, such as _unrelated machines_ , or for different objectives, such as
_max-min_ or _min-diff_.

In the language of fair item allocation, we have solved the problem of finding
a fair allocation among $n$ agents with the same valuations but different
entitlements, when the ownership on some $s$ items may be split between
agents. When agents may have different valuations, there are various fairness
notions, such as _proportionality_ , _envy-freeness_ or _equitability_. A
future research direction is to develop algorithms for finding such
allocations with a bounded number of shared items.

Our analysis shows the similarities and differences between these two variants
and the more common notion of FPTAS. One may view our results as introducing
two alternative kinds of approximation.

The first keeps the objective value optimal and allows a bounded number of
items to become fractional, instead of keeping the items discrete and allowing
a bounded deviation in the objective value. More generally, consider any
optimization problem that can be solved by a mixed-integer program, where some
of the problem variables are rationals and some are integers. Instead of
deciding in advance (in the problem definition) which of the variables must be
integers, one can consider a variant in which only the _number_ of the integer
variables is fixed in advance, whereas the solver can decide _which_ variables
are integers after receiving the input.

The second approximates a decision problem by returning “yes” iff there exists
a solution between $PER$ and $(1+t)\cdot PER$, where $PER$ represents the
value of a perfect solution. For the uniform machines scheduling problem, a
perfect solution is easy to define: it is a partition with equal completion
times. A more general definition of $PER$ could be the solution to the
fractional relaxation of an integer linear program representing the problem.
As we have shown, NP-hard decision problems may become tractable when $t$ is
sufficiently large.

Acknowledgments

The paper started from discussions in the stack exchange network 1 2. The case
of IsPerfectSplit$[n=3,s=1,r_{i}\equiv 1]$(${\cal X}$) was first solved by
Mikhail Rudoy using case analysis. The relation to FPTAS was raised by Chao
Xu. We are also grateful to John L. 3.

Funding This work was funded by Israel Science Foundation grant no. 712/20.

## Declarations

Conflict of interest No potential conflict of interest.

##  Appendix A Hardness proofs

###  A.1 Strong hardness for non-fixed $n$

In this section, we prove that when $n$ is part of the input (and not a fixed
parameter), the problems IsMaxInIntervalD$[d,{\cal R}]$$({\cal X},n)$ and
IsPerfectSplit$[s,{\cal R}]$$({\cal X},n)$ are strongly NP-hard, even for
identical machines.

First, we prove that IsMaxInIntervalD$[d,r_{i}\equiv 1]$$({\cal X},n)$ is
strongly NP-hard. Then, we show that IsPerfectSplit$[s,r_{i}\equiv 1]$$({\cal
X},n)$ is strongly NP-hard by reduction from IsMaxInIntervalD$[d,r_{i}\equiv
1]$$({\cal X},n)$.

######  Theorem 13.

For every fixed rational number $d\geq 0$, IsMaxInIntervalD$[d,r_{i}\equiv
1]$$({\cal X},n)$ is strongly NP-hard.

###### Proof.

We apply a reduction from the 3${-}$Partition problem: given a list ${\cal
X}_{1}$ of $3m^{\prime}$ positive integers with sum equal to
$m^{\prime}S^{\prime}$, decide if they can be partitioned into $m^{\prime}$
triplets such that the sum of each triplet is $S^{\prime}$. 3${-}$Partition is
proved to be strongly NP-hard in Garey and Johnson [1].

Given an instance ${\cal X}_{1}$ of 3${-}$Partition with $3m^{\prime}$
integers, define $n:=\lceil 2(m^{\prime}+d)\rceil$, where $d$ is the parameter
of the problem IsMaxInIntervalD$[d,r_{i}\equiv 1]$. Define $M$ to be the sum
of numbers in ${\cal X}_{1}$ divided by
$m^{\prime}n(1-\frac{d}{n-m^{\prime}})$, so that the sum of numbers in ${\cal
X}_{1}$ is $m^{\prime}n(1-\frac{d}{n-m^{\prime}})M$. Since $n=\lceil
2(m^{\prime}+d)\rceil$, it follows that $1-\frac{d}{n-m^{\prime}}>0$, so $M$
is positive. The 3${-}$Partition problem decides if the items can be
partitioned into $m^{\prime}$ triplets such that the sum of each triplet is
$n(1-\frac{d}{n-m^{\prime}})M$. We can assume w.l.o.g. that all items in
${\cal X}_{1}$ are at most $n(1-\frac{d}{n-m^{\prime}})M$, since if some item
is larger than $n(1-\frac{d}{n-m^{\prime}})M$, the answer is necessarily “no”.

Construct an instance ${\cal X}_{2}$ of the 3${-}$Partition problem by
replacing each item $x$ in ${\cal X}_{1}$ by $nM-x$. So ${\cal X}_{2}$
contains $3m^{\prime}$ items between $n(\frac{d}{n-m^{\prime}})M$ and $nM$.
Their sum, which we denote by $m^{\prime}S^{\prime}$, satisfies

$\displaystyle m^{\prime}S^{\prime}=3m^{\prime}\cdot
nM-m^{\prime}n\left(1-\frac{d}{n-m^{\prime}}\right)M=m^{\prime}n\left(2+\frac{d}{n-m^{\prime}}\right)M.$

Clearly, ${\cal X}_{1}$ has a three-partition (with sum
$n\left(1-\frac{d}{n-m^{\prime}}\right)M$) if and only if ${\cal X}_{2}$ has a
three-partition (with sum
$S^{\prime}=n\left(2+\frac{d}{n-m^{\prime}}\right)M$). The construction is
done in time polynomial in the size of ${\cal X}_{1}$.

Construct an instance $({\cal X}_{3},n)$ of IsMaxInIntervalD$[d,r_{i}\equiv
1]$ by adding, to the jobs (items) in ${\cal X}_{2}$, some $2(n-m^{\prime})$
jobs of size $nM$. Note that $nM$ is indeed the longest job length in ${\cal
X}_{3}$. Denote the sum of job lengths in ${\cal X}_{3}$ by $nS$. So

$\displaystyle nS$ $\displaystyle=m^{\prime}S^{\prime}+2(n-m^{\prime})\cdot
nM=n\left(2m^{\prime}+\frac{m^{\prime}d}{n-m^{\prime}}+2(n-m^{\prime})\right)\cdot
M$ $\displaystyle=n\left(2n+\frac{m^{\prime}d}{n-m^{\prime}}\right)M;$
$S+dM=\left(2n+\frac{m^{\prime}d}{n-m^{\prime}}+d\right)M=\left(2n+\frac{nd}{n-m^{\prime}}\right)M=S^{\prime},$

so a partition of ${\cal X}_{3}$ is $d$-possible if and only if the completion
time of each of the $n$ machines in the partition is at most
$S+dM=S^{\prime}$.

We now prove that if ${\cal X}_{2}$ has a three-partition then the
corresponding instance (${\cal X}_{3},n$) has a $d$-possible partition, and
vice versa.

If ${\cal X}_{2}$ has a three-partition, then the items of ${\cal X}_{2}$ can
be partitioned into $m^{\prime}$ bins of sum $S^{\prime}$, and the additional
$2(n-m^{\prime})$ items can be divided into $n-m^{\prime}$ bins of 2 items
each. Note that the sum of 2 additional items is

$\displaystyle 2\cdot nM$
$\displaystyle=\left(2n+\frac{nd}{n-m^{\prime}}\right)M-\frac{nd}{n-m^{\prime}}M=S^{\prime}-\frac{nd}{n-m^{\prime}}M<S^{\prime},$
(3)

Since $n>m^{\prime}$.

Conversely, suppose ${\cal X}_{3}$ has a $d$-possible partition. Let us
analyze its structure.

  * –

Since the partition is $d$-possible, the every $m^{\prime}$ machines process
together jobs with a total length of at most $m^{\prime}(S+dM)$.

  * –

So every $n-m^{\prime}$ machines process jobs with total length at least
$nS-m^{\prime}(S+dM)=(n-m^{\prime})S-m^{\prime}dM$.

  * –

The largest $2(n-m^{\prime})$ jobs in ${\cal X}_{3}$ sum up to exactly
$(n-m^{\prime})\cdot 2nM=(n-m^{\prime})S^{\prime}-ndM$ by (3), which equals
$=(n-m^{\prime})(S+dM)-ndM=(n-m^{\prime})S-m^{\prime}dM$.

  * –

Hence, every $n-m^{\prime}$ machines must together process _at least_
$2(n-m^{\prime})$ jobs.

  * –

Let $C$ be the set of $n-m^{\prime}$ machines with the fewest jobs. We claim
that machines in $C$ must process together _exactly_ $2(n-m^{\prime})$ jobs.
Suppose by contradiction that machines in $C$ processed $2(n-m^{\prime})+1$ or
more jobs. By the pigeonhole principle, there was a machine in $C$ that
processed at least $3$ jobs. By minimality of $C$, the $m^{\prime}$ machines
not in $C$ also processed at least $3$ jobs each. The total number of jobs
were $2(n-m^{\prime})+1+3m^{\prime}$. This is a contradiction, since the total
number of jobs in ${\cal X}_{3}$ is only $2(n-m^{\prime})+3m^{\prime}$.

  * –

The sum of job lengths in $C$ must still be at least
$(n-m^{\prime})S-m^{\prime}dM=2(n-m^{\prime})\cdot nM$, so each job in $C$
must have the maximum length of $nM$.

  * –

The other $m^{\prime}$ machines process together $3m^{\prime}$ jobs with total
length $m^{\prime}(S+dM)$, so each of these machines must have a completion
time of exactly $S+dM$. Since $2\cdot nM<S+dM$ by (3), each of these
$m^{\prime}$ machines must process exactly 3 jobs.

These latter $m^{\prime}$ machines correspond to the bins in a three-partition
of ${\cal X}_{2}$. This construction is done in time polynomial in the size of
${\cal X}_{2}$, since we added $2(n-m^{\prime})$ jobs to the initial
$3m^{\prime}$ items (jobs), so the new number of jobs is
$m^{\prime}+2n<m^{\prime}+4(m^{\prime}+d)+1=5m^{\prime}+4d+1$. For every
constant $d$, this number is linear in the size of ${\cal X}_{2}$. ∎

######  Theorem 14.

For any fixed integer $s=d\geq 0$, there is a polynomial-time reduction from
IsMaxInIntervalD$[d,r_{i}\equiv 1]$$({\cal X},n)$ to
IsPerfectSplit$[s,r_{i}\equiv 1]$$({\cal X},n)$.

###### Proof.

Given an instance $({\cal X},n)$ of IsMaxInIntervalD$[d,r_{i}\equiv 1]$$({\cal
X},n)$, construct an instance $({\cal X}^{\prime},n^{\prime})$ of
IsPerfectSplit$[s,r_{i}\equiv 1]$$({\cal X}^{\prime},n^{\prime})$ by setting
$n^{\prime}=n$ and adding $d=s$ jobs of size $nM$, where $nM$ is the size of
the biggest job in ${\cal X}$ (note that with identical machines, $A=n$).

First, assume that (${\cal X},n)$ has a $d$-possible partition. Then there are
$n$ machines with a completion time at most $S+dM$, where $S$ is the total
length of jobs in ${\cal X}$ divided by $n$. Take the $d$ added jobs of size
$nM$ and add them to the machines, possibly splitting some jobs between
machines, such that the completion time of each machine becomes exactly
$S+dM$. This is possible because the total length of the jobs in $({\cal
X}^{\prime},n^{\prime})$ is $nS+dnM=n(S+dM)$. The result is a perfect
partition of $({\cal X}^{\prime},n^{\prime})$ with at most $d=s$ split jobs.

Second, assume that $({\cal X}^{\prime},n^{\prime})$ has a perfect partition
with at most $s$ split jobs. Then there are $n^{\prime}$ machines with
completion time exactly $S+dM$. By Lemma 6 we can assume that the split jobs
are the largest ones, which are the $d$ added jobs of size $nM$. Remove these
jobs to get a partition of (${\cal X},n)$. The completion time in each machine
is now at most $S+dM$, so the partition is $d$-possible.

This construction is done in polynomial time, which completes the proof. ∎

Combining Theorem 13 and Theorem 14 gives:

######  Corollary 4.

For every fixed integer $s\geq 0$, the problem IsPerfectSplit$[s,{\cal
R}]$$({\cal X},n)$ is strongly NP-hard, even in the case of identical
machines.

###  A.2 Hardness with splitting count

In this section we analyze the complexity of partitioning when the parameter
$s$ denotes the number of _splittings_ , rather than the number of _split
jobs_.

######  Theorem 15.

For any fixed integer $n\geq 2$ and fixed $s\in\mathbb{N}$ such that $s\leq
n-2$, the problem IsPerfectSplittings$[n,s,{\cal R}]$(${\cal X}$) is NP-
complete, even in the special case of identical machines.

###### Proof.

Given a partition with $n$ machines, $m$ jobs and $s$ splittings, summing the
length of each jobs (or fraction of job) in each machine allows us to check
whether or not the partition is perfect in linear time. So, the problem is in
NP.

To prove that IsPerfectSplittings$[n,s,r_{i}\equiv 1]$ is NP-Hard, we apply a
reduction from the Subset Sum problem. We are given an instance ${\cal X}_{1}$
of Subset Sum with $m$ items summing up to $S$ and target sum $T<S$. We build
an instance ${\cal X}_{2}$ of IsPerfectSplittings$[n,s,{\cal R}]$(${\cal
X}_{2}$), by adding two jobs to the items (jobs) in ${\cal X}_{1}$,
$x_{1},x_{2}$, such that $x_{1}=S+T$ and $x_{2}=2S(s+1)-T$ and $n-2-s$
auxiliary jobs of size $2S$. Notice that the sum of the jobs in ${\cal X}_{2}$
equals

$\displaystyle S+(S+T)+2S(s+1)-T+2S(n-2-s)$
$\displaystyle=2S+2S(s+1)+2S(n-2-s)$ $\displaystyle=2S\cdot(1+s+1+n-2-s)$
$\displaystyle=2Sn.$

The goal is to partition the jobs into $n$ machines with a sum of $2S$ per
machine, and at most $s$ splittings.

First, assume that there is a subset of items $W_{1}$ in ${\cal X}_{1}$ with
sum equal to $T$. Define a set, $W_{2}$, of items that contains all jobs
(items) in ${\cal X}_{1}$ that are not in $W_{1}$, plus $x_{1}$. The sum of
$W_{2}$ is $(S-T)+x_{1}=S+T+S-T=2S$. Assign the jobs of $W_{2}$ to the first
machine. Assign each auxiliary job to a different machine. There are
$n-(n-2-s+1)=s+1$ machines left. The sum of the remaining jobs is $2S(s+1)$.
Using the “line-cutting” algorithm described in the introduction, these jobs
can be partitioned into $s+1$ machines of equal sum $2S$, with at most $s$
splittings. All in all, there are $n$ machines with a sum of $2S$ per machine,
and the total number of splittings is at most $s$.

Second, assume that there exists a perfect partition for $n$ machines with $s$
splittings. Since $x_{2}=2S(s+1)-T=2S\cdot s+(2S-T)>2S\cdot s$, this job must
be split between $s+1$ machines, which makes the total number of splittings at
least $s$. Also, the auxiliary jobs must be assigned without splittings into
$n-2-s$ different machines. There is $n-s-1-n+2+s=1$ machine remaining, say
machine $i$, containing only whole jobs, not containing any part of $x_{2}$,
and not containing any auxiliary job. Machine $i$ must processes $x_{1}$,
otherwise its completion time is at most $S$ (sum of items (jobs) in ${\cal
X}_{1}$). Let $W_{1}$ be the jobs of ${\cal X}_{1}$ that are not processed by
machine $i$. The sum of $W_{1}$ is $S-(2S-x_{1})=x_{1}-S=T$, so $W_{1}$
corresponds to a set with a sum of exactly $T$, which is a solution to ${\cal
X}_{1}$. ∎

Note that a weaker result was presented in [34], that
IsPerfectSplittings$[n,s,{\cal R}]$(${\cal X}$) is NP-complete for $s<n-2$,
even for identical machines.

##  Appendix B FPTAS-s for various partitioning problems

Our algorithms use FPTAS-s for several variants of the machines scheduling
problem. These FPTAS-s are developed using a general technique described by
[2]. In this section we briefly describe this technique.

The first step is to develop a dynamic programming (DP) algorithm that solves
the problem exactly. The algorithm should have a specific format called
_simple DP_ , defined by the following parameters:

  * –

The size of the input vectors, $\alpha\in\mathbb{N}$ (in our settings, usually
$\alpha=1$ since each input is a single integer);

  * –

The size of the _state vectors_ , $\beta\in\mathbb{N}$ (in our settings, each
state represents a partition of a subset of the inputs);

  * –

A set of initial states $V_{0}$ (in our settings, $V_{0}$ usually contains a
single state — the zero vector — representing the empty partition);

  * –

A set of _transition functions_ $F$; each function in $F$ accepts a state and
an input, and returns a new state (in our settings, each function in $F$
corresponds to putting the new input in one of the machines);

  * –

A set of _filter functions_ $H$; each function $h_{j}\in H$ corresponds to a
function $f_{j}\in F$. It accepts a state and an input, and returns a positive
value if the new state returned by $f_{j}$ is infeasible (infeasible states
are kept out of the state space).

  * –

An _objective function_ $G$, that maps a state to a numeric value.

The DP algorithm processes the inputs one by one. For each input $k$, it
applies every transition function in $F$ to every state in $V_{k-1}$, to
produce the new state-set $V_{k}$. Finally, it picks the state in $V_{m}$ that
minimizes the objective function. Formally:

  1. 1.

Let $V_{0}$ be the set of initial states.

  2. 2.

For $k:=1,\ldots,m$:

$\displaystyle V_{k}:=\\{f_{j}(s,x)|f_{j}\in F,~{}s\in
V_{k-1},~{}h_{j}(s,x)\leq 0\\}$

  3. 3.

Return

$\displaystyle\min\\{G(s)|s\in V_{m}\\}$

Every DP in this format can be converted to an FPTAS if it satisfies a
condition called _critical-coordinate-benevolence_ (CC-benevolence). To prove
that a dynamic program is CC-benevolent, we need to define a _degree vector_
$D$ of size $\beta$, which determines how much each state is allowed to
deviate from the optimal state. The functions in $F$, $G$, $H$ and the vector
$D$ should satisfy several conditions listed in Lemma 6.1 of [2]. These
conditions use the term _$[D,\Delta]$ -close_, defined as follows.

For a real number $\delta>1$ and two vectors $V=[v_{1},\dots,v_{\beta}]$ and
$V^{\prime}=[v^{\prime}_{1},\dots,v^{\prime}_{\beta}]$, we say that $V$ is
$[D,\Delta]-$close to $V^{\prime}$ if

$\Delta^{-d_{\ell}}\cdot
v_{\ell}~{}\leq~{}v^{\prime}_{\ell}~{}\leq~{}\Delta^{d_{\ell}}\cdot
v_{\ell},\text{ for all }\ell=1,\dots,\beta,$

that is, each coordinate in $V^{\prime}$ deviates from the corresponding
coordinate in $V$ by a multiplicative factor determined by $\Delta$ and by the
degree vector $D$. The $\Delta$ is a factor determined by the required
approximation accuracy $\epsilon$. Note that if some coordinate $\ell$ in $D$
is $0$, then the definition of $[D,\Delta]$-close requires that the coordinate
$\ell$ in $V^{\prime}$ is equal to coordinate $\ell$ in $V$ (no deviation is
allowed).

We now use Lemma 6.1 of [2] to prove that the problems
UniMinMaxCC$[n,t,i,{\cal R}]$ and UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$
are CC-benevolent, and therefore there is an FPTAS for solving these problems.

###  B.1 UniMinMaxCC$[n,t,i,{\cal R}]$

Recall that the objective of UniMinMaxCC$[n,t,i,{\cal R}]$(${\cal X}$) is to
find an $n$-way partition of ${\cal X}$ minimizing the makespan, subject to
the constraint that the completion time of machine $i$ is at most $(1+t)\cdot
S$, where $t\in\mathbb{Q}$ and $S=(\sum_{x\in{\cal X}}x)/A$ is the average
completion time.

###### Proof.

The dynamic program. We define a simple DP with $\alpha=1$ (the size of the
input vectors) and $\beta=n$ (the size of the state vectors). For
$k=1,\dots,m$ define the $k$-th input vector as $[x_{k}]$, where $x_{k}$ is
the length of job $k$. A state $V=[b_{1},b_{2},\dots,b_{n}]$ in $V_{k}$
encodes a partial allocation of the first $k$ jobs, where $b_{j}$ is the
completion time of machine $j\in\\{1,2\dots,n\\}$ in the partial allocation.
The set $F$ contains $n$ transition functions $f_{1},\dots,f_{n}$:

$\displaystyle
f_{1}(x_{k},b_{1},b_{2},\ldots,b_{n})=[b_{1}+x_{k}/r_{1},b_{2},\dots,b_{n}]$
$\displaystyle
f_{2}(x_{k},b_{1},b_{2},\dots,b_{n})=[b_{1},b_{2}+x_{k}/r_{2},\dots,b_{n}]$
$\displaystyle\dots$ $\displaystyle
f_{n}(x_{k},b_{1},b_{2},\dots,b_{n})=[b_{1},b_{2},\dots,b_{n}+x_{k}/r_{n}]$

Intuitively, the function $f_{j}$ corresponds to allocating job $k$ (with
length $x_{k}$) to machine $j$. The set $H$ contains a function
$h_{i}(x_{k},b_{1},b_{2},\dots,b_{n})=b_{i}+x_{k}/r_{i}-(1+t)\cdot S$, and
functions $h_{j}(x_{k},b_{1},b_{2},\dots,b_{n})\equiv 0$ for
$j\in\\{n\\}\setminus i$. These functions represent the fact that the
completion time of the machine $i$ must always be at most $(1+t)\cdot S$ (if
it becomes larger than $(1+t)\cdot S$, then $h_{i}$ will return a positive
value and the new state will be filtered out). There are no constraints on the
completion time of machines that are not $i$.

The initial state space $V_{0}$ contains a single vector
$\\{[0,0,\dots,0]\\}$. The minimization objective is

$\displaystyle G(b_{1},b_{2},\dots,b_{n})=\max\\{b_{1},b_{2},\dots,b_{n}\\}.$

Benevolence. We show that our problem is _CC-benevolent_ , as defined at
[2][Section 6]. We use the degree vector $D=[1,1,\dots,1]$, where $i$ is the
critical coordinate.

All the transition functions are polynomials of degree 1. The value of the
function $f_{1}(U,V)$ only depends on $x_{k}$ which is on $U$, and $i$ which
is our critical-coordinate. So, C.1(i) on the function set $F$ is fulfilled.

The functions $h_{1},h_{2},\dots,h_{n}$ are polynomials; the monomials do not
depend on completion times that are not $b_{i}$, and the monomial that depends
on $b_{i}$ has a positive coefficient. So, C.2(i) on the function set $H$ is
fulfilled.

If a state $[b_{1},b_{2},\dots,b_{n}]$ is $[D,\Delta]$-close to another state
$[b_{1}^{\prime},b_{2}^{\prime},\dots,b_{n}^{\prime}]$, then by
$[D,\Delta]$-close definition, we have $v^{\prime}_{1}\leq\Delta\cdot v_{1}$,
$v^{\prime}_{2}\leq\Delta\cdot v_{2}$, …, $v^{\prime}_{n}\leq\Delta\cdot
v_{n}$, so

$\max\\{b_{1}^{\prime},b_{2}^{\prime},\dots,b_{n}^{\prime}\\}\leq\Delta\cdot\max\\{b_{1},b_{2},\dots,b_{n}\\},$

and $G(V^{\prime})\leq\Delta\cdot G(V)$ Therefore, C.3(i) on the function $G$
is fulfilled (with degree $g=1$).

The definition in [2] also allows a _domination relation_ , but we do not need
it in our case (formally, our domination relation $\preceq_{dom}$ is the
trivial relation). So, the statement conditions C.1(ii), C.2(ii), C.3(ii) are
fulfilled.

Condition C.4 (i) holds since all functions in $F$ can be evaluated in
polynomial time. C.4 (ii) holds since the cardinality of $F$ is $n$, which is
considered a constant. C.4 (iii) holds since the cardinality of $V_{0}$ is a
constant. C.4(iv) is satisfied since the value of the coordinates is upper
bounded by the sum of the jobs $AS$, so their logarithm is bounded by the size
of the input. Hence, our problem is CC-benevolent. By the main theorem of [2],
it has an FPTAS. ∎

###  B.2 UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$

Recall that the objective is to find a $2$-way partition of ${\cal X}$
minimizing the largest completion time, subject the the constraint that the
completion time of machine $i$ is at most $(1+t_{i})\cdot S$, and
additionally, machine $q$ must process exactly $m_{q}$ jobs.

###### Proof.

The dynamic program. We define a simple DP with $\alpha=1$ (the size of the
input vectors) and $\beta=4$ (the size of the state vectors). For
$k=1,\dots,m$ define the input vector $U_{k}=[x_{k}]$ where $x_{k}$ is the
length of job $k$. A state $V=[b_{1},b_{2},l_{1},l_{2}]$ in $V_{k}$ encodes a
partial allocation for the first $k$ jobs, where $b_{j}$ is the completion
time of machine $j\in\\{1,2\\}$ in the partial allocation and $l_{j}$ is the
number of jobs processed by machine $j$. The set $F$ contains two transition
functions $f_{1},f_{2}$:

$\displaystyle
f_{1}(x_{k},b_{1},b_{2},l_{1},l_{2})=[b_{1}+x_{k}/r_{1},b_{2},l_{1}+1,l_{2}]$
$\displaystyle
f_{2}(x_{k},b_{1},b_{2},l_{1},l_{2})=[b_{1},b_{2}+x_{k}/r_{2},l_{1},l_{2}+1]$

Intuitively, the function $f_{j}$ corresponds to allocating job $k$ to machine
$j$. The set $H$ contains a function
$h_{i}(x_{k},b_{1},b_{2},l_{1},l_{2})=b_{i}+x_{k}/r_{i}-(1+t_{i})\cdot S$, and
a function $h_{j}(x_{k},b_{1},b_{2},l_{1},l_{2})\equiv 0$ for
$j\in[2]\setminus i$. These functions represent the fact that the completion
time of machine $i$ must always be at most $(1+t_{i})\cdot S$ (if it becomes
larger than $(1+t_{i})\cdot S$, then $h_{i}$ will return a positive value and
the new state will be filtered out). There are no constraints on the
completion time of machines that are not $i$.

The initial state space $V_{0}$ contains a single vector $\\{[0,0,0,0\\}$. The
minimization objective is

$\displaystyle
G(b_{1},b_{2},l_{1},l_{2})=\begin{cases}\max\\{b_{1},b_{2}\\},&\text{if
}l_{1}=m_{1}\text{ and }l_{2}=m_{2}\\\ \infty,&\text{otherwise}\end{cases}$

Benevolence. We define the degree vector as $D=[1,1,0,0]$. Note that the third
and fourth coordinates correspond to the number of jobs processed by each
machine, for which we need an exact number and not an approximation.

Lemma 4.1(i) is satisfied since if a state $[b_{1},b_{2},l_{1},l_{2}]$ is
$[D,\Delta]$-close to another state
$[b_{1}^{\prime},b_{2}^{\prime},l_{1}^{\prime},l_{2}^{\prime}]$, by definition
of $[D,\Delta]$-close [Section 2](2.1), we must have $l_{1}=l_{1}^{\prime}$
and $l_{2}=l_{2}^{\prime}$ because the degree of coordinates 3 and 4 is $0$.
At coordinates 1 and 2, both transition functions are polynomials of degree 1.
Furthermore, the value of the function $f_{1}(U,V)$ only depends on $x_{k}$
which is on $U$ and $b_{1}$ which is our critical-coordinate. So, C.1(i) on
the function set $F$ is fulfilled.

The functions $h_{1}$ and $h_{2}$ are polynomials; the monomials do not depend
on $b_{2}$, and the monomial that depends on $b_{1}$ has a positive
coordinate. So, C.2(i) on the function set $H$ is fulfilled.

If a state $[b_{1},b_{2},l_{1},l_{2}]$ is $[D,\Delta]$-close to another state
$[b_{1}^{\prime},b_{2}^{\prime},l_{1}^{\prime},l_{2}^{\prime}]$ (where
$\Delta$ is a factor determined by the required approximation accuracy
$\epsilon$), by $[D,\Delta]$-close definition, we have $l_{1}=l_{1}^{\prime}$
and $l_{2}=l_{2}^{\prime}$ because the degree of coordinates 3 and 4 is $0$,
also $b^{\prime}_{1}\leq\Delta b_{1}$ and $b^{\prime}_{2}\leq\Delta b_{2}$, so
$\max\\{b_{1}^{\prime},b_{2}^{\prime}\\}\leq\Delta\max\\{b_{1},b_{2}\\}$, so
$G(V^{\prime})\leq\Delta^{g}G(V)$. Therefore, C.3(i) on the function $G$ is
fulfilled (with degree $g=1$).

Again we do not need a domination relation, so we use the trivial relation
$\preceq_{dom}$. Then the statement conditions C.1(ii), C.2(ii), C.3(ii) are
fulfilled.

Condition C.4 (i) holds since all functions in $F$ can be evaluated in
polynomial time. C.4 (ii) holds since the cardinality of $F$ is a constant.
C.4 (iii) holds since the cardinality of $V_{0}$ is a constant. C.4(iv) is
satisfied for coordinates 1, 2 since their value is upper bounded by the sum
of the jobs $AS$, so their logarithm is bounded by the size of the input. For
coordinates 3, 4 (whose degree is 0), the condition is satisfied since their
value is upper bounded by the number of jobs $m$. Hence, our problem is CC-
benevolent. By the main theorem of [2], it has an FPTAS. ∎

###  B.3 Running time

We compute in this section the running time of Algorithm 1, algorithm 2 and
Algorithm 3. The running time of each FPTAS is linear in the number of states
in the dynamic program. The number of states in the dynamic program is bounded
by $L^{n}$, where $L$ is the number of possible values in every element of the
vector. In [2][Section 3], Woeginger proves that
$L\leq\lceil(1+\frac{2gm}{\epsilon})\pi_{1}(m,\log_{2}\bar{x})\rceil$, where
$m\in\mathbb{N}$ is the number of jobs, $\bar{x}$ is the sum of all job
lengths (which in our case is just $AS$), and $\pi_{1}$ is a function
describing the binary length of the values in the state vectors (in our case
it is a linear function).

In each FPTAS settings, $g=1$,
$\bar{x}=\sum_{k=1}^{m}\sum_{i=1}^{\alpha}x_{i,k}$, where $\alpha=1$, then,
$\bar{x}$ is the sum of all the jobs. Because every value in the state-vectors
is at most the sum of all values, we have the linear function
$\pi_{1}(m,\log_{2}\bar{x})=\log_{2}\bar{x}$.

####  B.3.1 Algorithm 1 running time

Algorithm 1 runs an FPTAS for UniMinMaxCC$[n=2,t,i,{\cal R}]$. In
UniMinMaxCC$[n=2,t,i,{\cal R}]$, $\epsilon=t/2$ and the sum of the jobs
$\bar{x}$, is equal to $AS$. Therefore, we have the following:
$L\leq\lceil(1+\frac{2m}{t/2})\log_{2}(AS)\rceil=\lceil(1+\frac{4m}{t})\log_{2}(AS)\rceil\in
O(\frac{m}{t}\log{S})$.

Therefore, Algorithm 1 running time is $O(\frac{m}{t}\log{S})$.

####  B.3.2 Algorithm 2 running time

Algorithm 2 runs an FPTAS for UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$. In
UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$,
$\epsilon=(r_{1}t_{1}+r_{2}t_{2})/(r_{1}+r_{2})$ and the sum of the jobs
$\bar{x}$, is equal to $AS$. Therefore, we have the following:
$L\leq\lceil(1+\frac{2m}{(r_{1}t_{1}+r_{2}t_{2})/(r_{1}+r_{2})})\log_{2}(AS)\rceil=\lceil(1+\frac{2(r_{1}+r_{2})m}{(r_{1}t_{1}+r_{2}t_{2})})\log_{2}(AS)\rceil\in
O(\frac{m}{r_{1}t_{1}+r_{2}t_{2}}\log{S})$.

Therefore, Algorithm 2 running time is
$O(\frac{m}{r_{1}t_{1}+r_{2}t_{2}}\log{S})$.

####  B.3.3 Algorithm 3 running time

Algorithm 3 runs three FPTAS, one for UniMinMax$[n,{\cal R}]$, one for
UniMinMax$[n,{\cal R}]$ and one for UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$
with different settings:

  * •

For UniMinMax$[n,{\cal R}]$ and UniMinMaxCC$[n,t,i,{\cal R}]$,
$\epsilon=t/(4An^{2}m^{2})$ and the sum of the jobs $\bar{x}$, is equal to
$AS$.

  * •

For UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$,
$\epsilon=(r_{1}t_{1}+r_{2}t_{2})/(r_{1}+r_{2})$ and the sum of the jobs
$\bar{x}$, is equal to $AS$.

Therefore, we have the following:

  * •

For UniMinMax$[n,{\cal R}]$ and UniMinMaxCC$[n,t,i,{\cal R}]$,
$L\leq\lceil(1+\frac{2m}{t/(4An^{2}m^{2})})\log_{2}(AS)\rceil=\lceil(1+\frac{8An^{2}m^{3}}{t})\log_{2}(AS)\rceil\allowbreak\in
O(\frac{m^{3}}{t}\log{S})$, resulting in the running time

$\displaystyle O(\frac{m^{3}}{t}\log{S})$ $\displaystyle=O(\frac{m^{3}\cdot
S}{dM}\log{S})$ since $t=dM/S$ $\displaystyle=O(\frac{m^{3}\cdot
S}{M}\log{S})$ since $d\geq n-2$ $\displaystyle=O(\frac{m^{3}\cdot
mM}{M}\log{S})$ since $mM\geq S$ $\displaystyle=O(m^{4}\log{S}).$

  * •

For UniMinMaxCC$[n=2,t_{1},t_{2},i,{\cal R}]$, the running time is computed in
Section B.3.2 and it is $O(\frac{m}{r_{1}t_{1}+r_{2}t_{2}}\log{S})$.

Therefore, Algorithm 3 running time is $O(m^{4}\log{S})$.

##  Appendix C Properties of instances with at least two almost-full machines

In this section we provide a detailed proof of Lemma 4.

Recall that, by the lemma assumption, there exists a $t$-feasible partition
with some $u\geq 2$ almost-full machines $1,\ldots,u$. We take an arbitrary
such partition and convert it using a sequence of transformations to another
$t$-feasible partition satisfying properties stated in the lemma, as explained
below.

###### Proof of Lemma 4, property (a).

Pick a $t$-feasible partition with some $u\geq 3$ almost-full machines.
Necessarily $u\leq n-1$, otherwise each machine has a completion time larger
than $S$ (since it is an almost-full machine), implying that the total length
of the jobs is larger than $AS$ which is a contradiction. It is sufficient to
show that there exists a $t$-feasible partition with $u-1$ almost-full
machines; then we can proceed by induction down to 2. Call the almost-full
machines $1,\dots,u$ and the not-almost-full machines $u+1,\dots,n$. By
definition of almost-full machines,

$\displaystyle
r_{1}b_{1}+\dots+r_{u}b_{u}\geq(r_{1}+\dots+r_{u})(1+t-2\epsilon)\cdot S,$

so,

$\displaystyle r_{u+1}b_{u+1}+\dots+r_{n}b_{n}$
$\displaystyle=AS-(r_{1}b_{1}+\dots+r_{u}b_{u})$
$\displaystyle<AS-(r_{1}+\dots+r_{u})(1+t-2\epsilon)\cdot S$
$\displaystyle=(r_{u+1}+\dots+r_{n}-(r_{1}+\dots+r_{u})(t-2\epsilon))\cdot S.$

Let $\Delta$ be the total free space in the not-almost-full machines:

$\displaystyle\Delta$
$\displaystyle=\sum^{n}_{i=u+1}{r_{i}(1+t)S}-(r_{u+1}b_{u+1}+\dots+r_{n}b_{n})$
$\displaystyle>(1+t)S(r_{u+1}+\dots+r_{n})-(r_{u+1}+\dots+r_{n}-(r_{1}+\dots+r_{u})(t-2\epsilon))\cdot
S$
$\displaystyle=((1+t)(r_{u+1}+\dots+r_{n})+(r_{1}+\dots+r_{u})(t-2\epsilon)-(r_{u+1}+\dots+r_{n}))\cdot
S$ $\displaystyle=((r_{u+1}+\dots+r_{n})\cdot
t+(r_{1}+\dots+r_{u})(t-2\epsilon))\cdot S$
$\displaystyle=(At-(r_{1}+\dots+r_{u})2\epsilon)\cdot S$

Denote by $\Delta_{k}$ the maximum free space in a non-almost-full machine
(breaking ties arbitrarily). By the pigeonhole principle,

$\displaystyle\Delta_{k}$
$\displaystyle\geq\frac{(At-(r_{1}+\dots+r_{u})2\epsilon)\cdot S}{n-u}$
$\displaystyle\geq\frac{(At-(r_{1}+\dots+r_{u})2\epsilon)\cdot S}{n-3}$ (since
$u\geq 3$) $\displaystyle\geq\frac{(At-(r_{1}+\dots+r_{n-1})2\epsilon)\cdot
S}{n-3}$ (since $u\leq n-1$)

Assume that machine $k$ is the machine with the largest free space
$\Delta_{k}$. By assumption, the length of each job is at most $AM$. Suppose
we take one job from machine $u$, and move it to machine $k$. Then after the
transformation:

$\displaystyle b_{k}r_{k}$ $\displaystyle\leq r_{k}(1+t)S-\Delta_{k}+AM$
$\displaystyle=r_{k}(1+t)S-\frac{(At-(r_{1}+\dots+r_{n-1})2\epsilon)\cdot
S}{n-3}+AM$ $\displaystyle\leq
r_{k}(1+t)S-\frac{(At-(r_{1}+\dots+r_{n-1})2\epsilon)\cdot
S}{n-3}+\frac{AtS}{n-2}$ (since $dM=tS$ and $d\geq n-2$ )
$\displaystyle=(r_{k}(1+t)-\frac{(At-(r_{1}+\dots+r_{n-1})2\epsilon)}{n-3}+\frac{At}{n-2})\cdot
S$
$\displaystyle=(r_{k}(1+t)-\frac{At}{(n-3)(n-2)}+\frac{r_{1}+\dots+r_{n-1}}{n-3}2\epsilon)\cdot
S$
$\displaystyle=r_{k}(1+t-\frac{At}{r_{k}(n-3)(n-2)}+\frac{r_{1}+\dots+r_{n-1}+r_{k}(n-3)}{r_{k}(n-3)}2\epsilon-2\epsilon)\cdot
S$ $\displaystyle\leq
r_{k}(1+t-\frac{At}{r_{k}(n-3)(n-2)}+\frac{t}{r_{k}(n-3)(n-2)}-2\epsilon)\cdot
S$ (since
$\epsilon=\frac{t}{4An^{2}m^{2}}\leq\frac{t}{2(r_{1}+\dots+r_{n-1}+r_{k}(n-3))(n-2)}$)
$\displaystyle<r_{k}(1+t-2\epsilon)\cdot S.$

So, machine $k$ remains not-almost-full. If machine $u$ is still almost-full,
then we are in the same situation: we have exactly $u$ almost-full machines.
So we can repeat the argument, and move another job from machine $u$ to the
(possibly different) machine with the largest free space. Since the number of
jobs in machine $u$ decreases with each step, eventually it becomes not-
almost-full. ∎

###### Proof of Lemma 4, property (b).

For proving the lower bound, suppose there is some not-almost-full machine
$i\in\\{3,\ldots,n\\}$ with
$b_{i}<\left(r_{i}+\left(r_{i}-\frac{A}{n-2}\right)t-r_{i}2\epsilon\right)\cdot
S$. Move a job from one almost-full machine to machine $i$. Its new sum
satisfies

$\displaystyle r_{i}b_{i}$
$\displaystyle<\left(r_{i}+\left(r_{1}-\frac{A}{n-2}\right)t-r_{i}2\epsilon\right)\cdot
S+AM$
$\displaystyle=\left(r_{i}+\left(r_{i}-\frac{A}{n-2}\right)t-r_{i}2\epsilon\right)\cdot
S+\frac{AtS}{n-2}$ (Since $d\leq n-2$)
$\displaystyle\leq\left(r_{i}+\left(r_{i}-\frac{A}{n-2}+\frac{A}{n-2}\right)t-r_{i}2\epsilon\right)\cdot
S$ $\displaystyle=r_{i}(1+t-2\epsilon)\cdot S,$

so machine $i$ is still not almost-full. Assumption (1) implies that machines
$1$ and $2$ must still be almost-full. So we are in the same situation and can
repeat the argument until the lower bound is satisfied.

The upper bound on $r_{i}b_{i}$ is proved by subtracting the lower bounds of
the other $n-1$ machines from the sum of all jobs. The total length of jobs
allocated to the $n-3$ other not-almost-full machines is at least:

$\displaystyle\sum_{j\in R\setminus\\{1,2,i\\}}$
$\displaystyle\left(\left(r_{j}+\left(r_{j}-\frac{A}{n-2}\right)t-r_{j}2\epsilon\right)\cdot
S\right)$ $\displaystyle=S\left(\sum_{j\in
R\setminus\\{1,2,i\\}}\left(r_{j}+\left(r_{j}-\frac{A}{n-2}\right)t-r_{j}2\epsilon\right)\right)$
$\displaystyle=S\left(\sum_{j\in
R\setminus\\{1,2,i\\}}(r_{j}+r_{j}t-r_{j}2\epsilon)-\sum_{j\in
R\setminus\\{1,2,i\\}}\frac{At}{n-2}\right)$ $\displaystyle=S\left(\sum_{j\in
R\setminus\\{1,2,i\\}}r_{j}(1+t-2\epsilon)-(n-3)\frac{At}{n-2}\right)$
$\displaystyle=(1+t-2\epsilon)\cdot S\sum_{j\in
R\setminus\\{1,2,i\\}}r_{j}-(n-3)\frac{At}{n-2}\cdot S$
$\displaystyle=(1+t-2\epsilon)\cdot
S\cdot(A-r_{1}-r_{2}-r_{i})-(n-3)\frac{At}{n-2}\cdot S$

And the total length of jobs allocated to the two almost-full machines is:

$\displaystyle r_{1}b_{1}+r_{2}b_{2}>(r_{1}+r_{2})(1+t-2\epsilon)\cdot S$ (by
almost-full machine size)

Therefore,

$\displaystyle r_{i}b_{i}$ $\displaystyle\leq
AS-(r_{1}+r_{2})(1+t-2\epsilon)\cdot S+(n-3)\frac{At}{n-2}\cdot
S-(1+t-2\epsilon)(A-(r_{1}+r_{2}+r_{i}))\cdot S$
$\displaystyle=(A-(r_{1}+r_{2})(1+t-2\epsilon)+(n-3)\frac{At}{n-2}-(1+t-2\epsilon)(A-(r_{1}+r_{2}+r_{i})))\cdot
S$
$\displaystyle=(A-(r_{1}+r_{2}+A-(r_{1}+r_{2}+r_{i}))(1+t-2\epsilon)+(n-3)\frac{At}{n-2})\cdot
S$ $\displaystyle=(A-(A-r_{i})(1+t-2\epsilon)+(n-3)\frac{At}{n-2})\cdot S$
$\displaystyle=(r_{i}+(r_{i}-A+\frac{(n-3)A}{n-2})t+(A-r_{i})2\epsilon)\cdot
S$
$\displaystyle=(r_{i}+\left(r_{i}-\frac{A}{n-2}\right)t+(A-r_{i})2\epsilon)\cdot
S,$

so property (b) is satisfied. ∎

###### Proof of Lemma 4, property (c).

Suppose machine 1 or 2 processes a job of length at most
$(\frac{t}{n-2}-2\epsilon)\cdot AS$. We move it to some not-almost-full
machine $i$, $i\geq 3$. By property (b), the new sum of job lengths allocated
to machine $i$ satisfies

$\displaystyle r_{i}b_{i}$
$\displaystyle\leq\left(r_{i}+\left(r_{i}-\frac{A}{n-2}\right)t+(A-r_{i})2\epsilon\right)\cdot
S+(\frac{t}{n-2}-2\epsilon)\cdot AS$
$\displaystyle=\left(r_{i}+\left(r_{i}-\frac{A}{n-2}+\frac{A}{n-2}\right)t+(A-A-
r_{i})2\epsilon\right)\cdot S$ $\displaystyle=(1+t-2\epsilon)S,$

so machine $i$ remains not-almost-full. Assumption (1) implies that machines 1
and 2 remain almost-full. So properties (a), (b) still hold, and we can repeat
the argument. Each move increases the number of jobs on the not-almost-full
machines, so the process must end, and eventually all jobs of length at most
$(\frac{t}{n-2}-2\epsilon)\cdot AS$ are allocated to machines $3,\ldots,n$. ∎

###### Proof of Lemma 4, property (d).

Suppose there exists some $i\in\\{3,\dots,n\\}$ for which machine $i$
processes a job $x$ such that $x\geq 2\epsilon AS$, but $x<y$ for some job $y$
processed by machine $1$ or $2$. We exchange $x$ and $y$. The total length of
jobs allocated to machine $i$ increases by at most $AM-2\epsilon AS$:

$\displaystyle r_{i}b_{i}$
$\displaystyle\leq(r_{i}+\left(r_{i}-\frac{A}{n-2}\right)t+(A-r_{i})2\epsilon)\cdot
S+AM-2\epsilon AS$
$\displaystyle\leq(r_{i}+\left(r_{i}-\frac{A}{n-2}\right)t+(A-r_{i})2\epsilon)\cdot
S+\frac{AtS}{n-2}-2AS\epsilon$ (since $M=tS/d$ and $d\geq n-2$)
$\displaystyle=(r_{i}+\left(r_{i}-\frac{A}{n-2}+\frac{A}{n-2}\right)t+(A-r_{i}-A)2\epsilon)\cdot
S$ $\displaystyle=r_{i}\cdot(1+t-2\epsilon)\cdot S,$

so machine $i$ is still not almost-full. So by (1), machines $1$ and $2$ must
remain almost-full, and we can repeat the argument. Each move decreases the
total length of jobs at machines $1,2$, so the process must end. ∎

###### Proof of Lemma 4, property (e).

By definition of almost-full, the total length of jobs at machine $i$ is at
least:

$\displaystyle
r_{i}(1+t-2\epsilon)S=r_{i}(S+(n-2)(\frac{t}{n-2}-\frac{2\epsilon}{n-2})S)\geq
r_{i}(S+(n-2)(\frac{t}{n-2}-2\epsilon)S).$

The sum of all jobs must be at least the number of big-jobs times the smallest
length of a big-job, so,

$\displaystyle S\geq m_{b}\cdot(\frac{t}{n-2}-2\epsilon)S.$

Substituting above gives that the total length of jobs at an almost full
machine is at least:

$\displaystyle
r_{i}(m_{b}\cdot(\frac{t}{n-2}-2\epsilon)S+(n-2)(\frac{t}{n-2}-2\epsilon)S)=r_{i}(\frac{t}{n-2}-2\epsilon)(m_{b}+n-2)S.$

Since the largest job length is $AM\leq\frac{tAS}{n-2}$, the number of jobs
processed by an almost full machine is at least:

$\displaystyle m_{i}\geq$
$\displaystyle\frac{r_{i}(\frac{t}{n-2}-2\epsilon)(m_{b}+n-2)S}{\frac{tAS}{n-2}}=\frac{r_{i}(t-2\epsilon(n-2))}{tA}(m_{b}+n-2)$
$\displaystyle=$
$\displaystyle\frac{r_{i}}{A}(1-\frac{n-2}{2An^{2}m^{2}})(m_{b}+n-2)~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(since
$t=4\epsilon An^{2}m^{2}$)}$ $\displaystyle=$
$\displaystyle\frac{r_{i}}{A}(m_{b}+n-2)-\frac{r_{i}}{A}\frac{(m_{b}+n-2)(n-2)}{2An^{2}m^{2}}$
$\displaystyle\geq$
$\displaystyle\frac{r_{i}}{A}(m_{b}+n-2)-\frac{r_{i}}{A}\frac{1}{Am}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{(since
$m_{b}+n-2\leq 2m$ and $n-2\leq n^{2}$)}$

Multiplying by $A$ gives:

$\displaystyle m_{i}A$ $\displaystyle\geq r_{i}(m_{b}+n-2)-r_{i}/Am$
$\displaystyle>r_{i}(m_{b}+n-2)-1$ since $r_{i}<A$.

In the latter inequality, both sides are integers, so $m_{i}A\geq
r_{i}(m_{b}+n-2)$, which implies $m_{i}\geq r_{i}(m_{b}+n-2)/A$.

Based on the previous properties, we know that every not-almost-full machine
will become almost-full if we add into it a single big-job. Therefore,

$\displaystyle m_{1}$ $\displaystyle\geq r_{1}(m_{b}+n-2)/A$ $\displaystyle
m_{2}$ $\displaystyle\geq r_{2}(m_{b}+n-2)/A$ $\displaystyle m_{i}+1$
$\displaystyle\geq r_{i}(m_{b}+n-2)/A$ (for every $i\in\\{3,\dots,n\\}$)

Summing up all these inequalities gives:

$\displaystyle m_{b}+n-2$
$\displaystyle=m_{1}+m_{2}+(m_{3}+1)+\dots+(m_{n}+1)$
$\displaystyle\geq(r_{1}+r_{2}+r_{3}+\dots+r_{n})(m_{b}+n-2)/A=m_{b}+n-2.$

Therefore, all the above inequalities must in fact be equations. Hence,

$\displaystyle\frac{m_{1}}{r_{1}}=\frac{m_{2}}{r_{2}}=\frac{m_{3}+1}{r_{3}}=\dots=\frac{m_{n}+1}{r_{n}}=\frac{m_{b}+n-2}{A}.$

∎

##  Appendix D Additional plots

We present the plots obtained for different values of the parameters presented
in the Section 5. All the plots behave similarly, showing that the difference
between the optimal and the perfect partition decreases when the number of
split jobs increases.

Figure 2: Uniform distribution with $m=10$ and 16 bits.  Figure 3: Uniform
distribution with $m=10$ and 16 bits.  Figure 4: Uniform distribution with
$m=13$ and 16 bits.  Figure 5: Uniform distribution with $m=15$ and 16 bits.
Figure 6: Uniform distribution with $m=15$ and 32 bits.  Figure 7: Uniform
distribution with $m=15$ and 32 bits.  Figure 8: Exponential distribution with
$m=10$.  Figure 9: Exponential distribution with $m=13$.  Figure 10:
Exponential distribution with $m=15$.

## References

  *   * Garey and Johnson [1979] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
  * Woeginger [2000] Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. 12(1), 57–74 (2000)
  * Korf [1998] Korf, R.E.: A complete anytime algorithm for number partitioning. Artif. Intell. 106(2), 181–203 (1998) https://doi.org/10.1016/S0004-3702(98)00086-1
  * McNaughton [1959] McNaughton, R.: Scheduling with deadlines and loss functions. Management Science 6(1), 1–12 (1959). Accessed 2022-12-11
  * Xing and Zhang [2000] Xing, W., Zhang, J.: Parallel machine scheduling with splitting jobs. Discret. Appl. Math. 103(1-3), 259–269 (2000) https://doi.org/10.1016/S0166-218X(00)00176-1
  * Shchepin and Vakhania [2005] Shchepin, E., Vakhania, N.: New tight np-hardness of preemptive multiprocessor and open-shop scheduling (2005)
  * Gonzalez and Sahni [1978] Gonzalez, T.F., Sahni, S.: Preemptive scheduling of uniform processor systems. J. ACM 25(1), 92–101 (1978) https://doi.org/10.1145/322047.322055
  * Shachnai et al. [2005] Shachnai, H., Tamir, T., Woeginger, G.J.: Minimizing makespan and preemption costs on a system of uniform machines. Algorithmica 42(3-4), 309–334 (2005) https://doi.org/10.1007/s00453-005-1171-0
  * Soper and Strusevich [2019] Soper, A.J., Strusevich, V.A.: Schedules with a single preemption on uniform parallel machines. Discrete Applied Mathematics 261, 332–343 (2019). GO X Meeting, Rigi Kaltbad (CH), July 10–14, 2016
  * Liu and Cheng [2002] Liu, Z., Cheng, T.C.E.: Scheduling with job release dates, delivery times and preemption penalties. Inf. Process. Lett. 82(2), 107–111 (2002) https://doi.org/10.1016/S0020-0190(01)00251-4
  * Serafini [1996] Serafini, P.: Scheduling jobs on several machines with the job splitting property. Oper. Res. 44(4), 617–628 (1996) https://doi.org/10.1287/opre.44.4.617
  * Krysta et al. [2003] Krysta, P., Sanders, P., Vöcking, B.: Scheduling and traffic allocation for tasks with bounded splittability. In: Rovan, B., Vojtás, P. (eds.) Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings. Lecture Notes in Computer Science, vol. 2747, pp. 500–510. Springer, Bratislava (2003). https://doi.org/10.1007/978-3-540-45138-9_44 . https://doi.org/10.1007/978-3-540-45138-9_44
  * Son et al. [2021] Son, T.H., Lang, T.V., Tuong, N.H., Soukhal, A.: Resolution for bounded-splitting jobs scheduling problem on a single machine in available time-windows. J. Ambient Intell. Humaniz. Comput. 12(1), 1179–1196 (2021) https://doi.org/10.1007/s12652-020-02162-0
  * Shim and Kim [2008] Shim, S., Kim, Y.: A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property. Comput. Oper. Res. 35(3), 863–875 (2008) https://doi.org/10.1016/j.cor.2006.04.006
  * Yalaoui and Chu [2003] Yalaoui, F., Chu, C.: An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times. IIE Transactions 35(2), 183–190 (2003) https://doi.org/10.1080/07408170304382 https://doi.org/10.1080/07408170304382
  * Kim et al. [2004] Kim, Y.-D., Shim, S.-O., Kim, S.-B., Choi, Y.-C., Yoon, H.M.: Parallel machine scheduling considering a job-splitting property. International Journal of Production Research 42(21), 4531–4546 (2004) https://doi.org/10.1080/00207540410001720745 https://doi.org/10.1080/00207540410001720745
  * Kim [2018] Kim, H.: Bounds for parallel machine scheduling with predefined parts of jobs and setup time. Ann. Oper. Res. 261(1-2), 401–412 (2018) https://doi.org/10.1007/s10479-017-2615-z
  * Wang et al. [2016] Wang, C., Liu, C., Zhang, Z., Zheng, L.: Minimizing the total completion time for parallel machine scheduling with job splitting and learning. Comput. Ind. Eng. 97, 170–182 (2016) https://doi.org/10.1016/j.cie.2016.05.001
  * Kim and Lee [2021] Kim, H., Lee, J.: Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers. Comput. Oper. Res. 126, 105115 (2021) https://doi.org/10.1016/j.cor.2020.105115
  * Brams and Taylor [1996] Brams, S.J., Taylor, A.D.: Fair Division: From Cake Cutting to Dispute Resolution. Cambridge University Press, Cambridge UK (1996)
  * Brams and Taylor [2000] Brams, S.J., Taylor, A.D.: The Win-win Solution - Guaranteeing Fair Shares to Everybody. W. W. Norton & Company, New York (2000)
  * Brams and Togman [1996] Brams, S.J., Togman, J.M.: Camp David: Was The Agreement Fair? Conflict Management and Peace Science 15(1), 99–112 (1996)
  * Massoud [2000] Massoud, T.G.: Fair Division, Adjusted Winner Procedure (AW), and the Israeli-Palestinian Conflict. Journal of Conflict Resolution 44(3), 333–358 (2000)
  * Schneider and Krämer [2004] Schneider, G., Krämer, U.S.: The Limitations of Fair Division. Journal of Conflict Resolution 48(4), 506–524 (2004)
  * Daniel and Parco [2005] Daniel, T., Parco, J.: Fair, Efficient and Envy-Free Bargaining: An Experimental Test of the Brams-Taylor Adjusted Winner Mechanism. Group Decision and Negotiation 14(3), 241–264 (2005)
  * Wilson [1998] Wilson, S.J.: Fair division using linear programming. preprint, Departement of Mathematics, Iowa State University (1998)
  * Pazner and Schmeidler [1978] Pazner, E.A., Schmeidler, D.: Egalitarian Equivalent Allocations: A New Concept of Economic Equity. Quarterly Journal of Economics 92(4), 671–687 (1978)
  * Goldberg et al. [2022] Goldberg, P.W., Hollender, A., Igarashi, A., Manurangsi, P., Suksompong, W.: Consensus halving for sets of items. Math. Oper. Res. 47(4), 3357–3379 (2022) https://doi.org/10.1287/moor.2021.1249
  * Sandomirskiy and Segal-Halevi [2022] Sandomirskiy, F., Segal-Halevi, E.: Efficient fair division with minimal sharing. Oper. Res. 70(3), 1762–1782 (2022) https://doi.org/10.1287/opre.2022.2279
  * Bei et al. [2021] Bei, X., Li, Z., Liu, J., Liu, S., Lu, X.: Fair division of mixed divisible and indivisible goods. Artif. Intell. 293, 103436 (2021)