Relation with the perfect partition problem and the single machine task schedule problem Perfect partition problem (PPP): given $x_1,...,x_n\in \mathbb{N}$ we want to know if there's a set $S\subset \{1,2,...,n\}$ such that $$\sum_{i\in S}x_i=\sum_{j\notin S}x_j.$$
Single machine task schedule problem (SMP): A machine can perform only one task $T_i$ with duration $d_i$ at a time and we want to know if all tasks can be done, given that $T_i$ can't start before the time $a_i$ or be finished after the time $b_i$ with $i\in \{1,2,3,...,n\}$.
I want to know how to reduce PPP to SMP.
I tried modelling SMP using the constraints and the existence a bijection $f:\{1,2,3,...,n\} \rightarrow \{1,2,3,...,n\}$ such that $$a_{f(i)}\leq \sum_{j=1}^i d_{f(i)}\leq b_{f(i)}$$ for all $i\in \{1,2,3,...,n\}$. And I tried to make $x_i=d_i$ and get the conditions of the SMP to make the sum be equal to que complementary $\left (\frac{\sum_{i=1}^{n} x_i}{2}\right)$ at some point, but I got stuck as I can't find how to relate $f$ to $S$ from the PPP, that's not really working.
 A: Here's a way to perform the reduction: given $n$ nonnegative integers $x_1,\ldots, x_n$, create $n$ events with duration $d_i = x_i$. Let $T$ denote half the sum of the $x_i$—this is the sum of a perfect partition.
Create a new event of duration $d_0=1$.  Impose the constraint that it must occur in $[T,T+1]$ (i.e. there's only one scheduling solution for this event). For all other events, let them start anywhere in the range $[0, 2T+1]$. 
The zeroth event acts as a separator: it must occur in exactly one place. It occurs exactly at the midtime, forcing all events to occur completely before or completely after the separator event (because events can't occur at the same time.)  Except for the time that the machine is busy doing the zeroth event, there's exactly $2T$ time left over to fit all the other events in.  
Hence if you can schedule the remaining events, they'll occur back-to-back (because there's no spare time for idleness) and each event will occur completely before or completely after time $T$, giving you a partition. If there's a solution to this reduced SM problem, then there's a solution to the original PP problem..
Moreover, if you have a solution to the original PP problem, you can easily convert it into a solution to this modified problem: choose an order for the numbers in each partition. Schedule the first partition in the time $[0,T]$ and the second partition in the time $[T+1, 2T+1]$. This is possible because the sum of the integers in each partition is exactly $T$.

Here's the thought process that led to this solution, which I think can be more helpful than just the final result itself.
Given integers $x_1,\ldots,x_n$, create $n$ new tasks with duration $d_i = x_i$. The clever part will come from choosing the required start and end times.
Let $T = \frac{1}{2}\sum_i x_i$. Then $T$ is the sum of a perfect partition. What you'd like is that an arrangement of tasks will perfectly divide the elements $x_1,\ldots,x_n$ into those that start and end completely before time $T$, and those that start and end completely after time $T$. Altogether, the events should take exactly time $2T$ to complete. Then the perfect partitions correspond to the events before and after time $T$, respectively.
There are several tricks we can use. 
First, what we would really like to do is enforce a constraint like this: event $x_1$ can either occur in the first half, between time $[0,x_1]$, or in the second half, between time $[T, T+x_1]$. If we could impose "broken interval" constraints like this, the reduction would be easy enough because the constraints would force all events  to occur either completely before or completely after the midtime $T$. If that were our problem, we would order our events from shortest to longest and impose constraints of the form:
$$x_k\text{ must occur in }([a_k,a_k+x_k]\cup[T+a_k, T+a_k+x_k])\cap [0,2T]$$
where $a_k \equiv \sum_{i=1}^{k-1} x_i$.
Second, we can sort of achieve that effect for the original problem using symmetric intervals around the midtime: instead of scheduling $x_1$ in $[0,x_1]\cup[T,T+x_1]$, instead we schedule $x_1$ in $[T-x_1, T+x_1]$, $x_2$ in $[T-x_1-x_2, T+x_1+x_2]$, and so on (with a maximum range of $[0,2T]$.)
Now these put the constraints in legal single-interval form for SMP.
Third: unfortunately, these symmetric constraints don't actually enforce the desired PPP constraints completely: if you think about it, you can still get a solution where an event starts before $T$ and ends after $T$.  To force a complete separation, we will introduce a new event.
The new event acts as a separator. Its exact duration is irrelevant—let's say $d_0 = 2$. We impose the constraint that it must start at $T-1$, and it must end at $T+1$. Hence there is absolutely one place that the event can fit, and it's right in the middle. Because events can't overlap, this separator event cleanly divides the left and right partitions with no possibility of an event starting before $T$ and ending after $T$.
Accordingly, we must change the interval constraints a little bit: now the total time to complete all events is $[0,2T+2]$. Event $x_1$ may occur in $[T-1-x_1, T+1+x_1]$, and so on. Event $x_k$ may occur in $[T-1-a_k, T+1+a_k]$ .
