7
$\begingroup$

Given is a positive integer integer $n$, and integers $a_1,b_1,\dots,a_n,b_n$ with $ a_i\leq b_i$ for each $i$. What is the complexity of deciding whether there exist integers $c_1,\dots,c_n$ such that $a_i\leq c_i\leq b_i$ for all $i$ and $|c_i-c_j|\geq 2$ for all $i,j$?

What can be observed is that a greedy algorithm, wherein we assume that $a_1\leq\dots\leq a_n$ and choose $c_i$ according to this order, does not necessarily work. For example, we may have $a_1=1, b_1=4, a_2=b_2=2$. Putting $c_1=1$ does not work (it leaves no room for $c_2$), but what works is putting $c_1=4$ and $c_2=2$. Is the problem perhaps NP-hard?

$\endgroup$
  • 1
    $\begingroup$ Have you considered dynamic programming? $\endgroup$ – Apass.Jack Jun 28 at 12:55
  • $\begingroup$ Yes. The problem is that we don't know the order of the $c_i$'s, so we could not store, for example, the "best" solution using $c_1,\dots,c_k$ on the left-hand side. $\endgroup$ – pi66 Jun 28 at 13:15
  • $\begingroup$ Could you add a reference to the original problem? $\endgroup$ – Apass.Jack Jun 28 at 20:52
  • $\begingroup$ I don’t have a reference. I’d be interested if anyone knows one. $\endgroup$ – pi66 Jun 28 at 21:45
5
$\begingroup$

As shown in the previous answer, this problem can be modeled as a scheduling problem with release and due dates. However, Schrage's heuristic works only for the case $p_j=1$ (all processing times are $1$) or when release and due dates agree (i.e. there is an order such that $r_1\leq\cdots\leq r_n$ and $d_1\leq\cdots\leq d_n$).

For the case $p_j=p$ polynomial algorithms have been found by Simons (1978), Carlier (1981), and Garey et al. (1981), running in time $O(n^2\log n)$, $O(n^2\log n)$, and $O(n\log n)$, respectively.

The algorithm of Garey et al. schedules unit-time tasks, but allows arbitrary release and due dates. The above problem can be reduced to this setting by dividing all dates and processing times by $p$. The main idea of the algorithm is to find a set of forbidden regions where no task is allowed to start. They show that Schrage's heuristic when respecting forbidden regions finds a feasible schedule of minimal makespan. When constructing the forbidden regions their algorithm may also detect infeasibility.

To see how the algorithm works, first look at a simpler problem: schedule $n$ unit-time tasks between a release date $r$ and a deadline $d$ respecting forbidden regions $F=\bigcup_i (a_i,b_i)$, where each region $(a_i,b_i)$ is an open interval. (Note here we're not concerned with release and due dates of individual tasks.)

This problem can be solved by Backscheduling: define a sentinel starting time $s_{n+1}=d$, and for $i=n,n-1,\ldots,1$ set starting time $s_i$ to the latest time not later than $s_{i+1}-1$ that is not forbidden.

Write $B(r,d,n,F)$ for an application of Backscheduling for the above inputs, and define the return value as $s_1$, the latest possible starting date for scheduling the $n$ tasks. Now, if $B(r,d,n,F)<r$ there is no feasible schedule for the $n$ tasks. Further, if $r\leq B(r,d,n,F)<r+1$ no other task can start in $(B(r,d,n,F)-1,r)$ since otherwise there is again no feasible schedule for the $n$ tasks, and thus $(B(r,d,n,F)-1,r)$ can be declared a forbidden region.

It turns out that this logic is sufficient to find all forbidden regions that are required to make Schrage's heuristic work. Assume that tasks are ordered such that $r_1\leq r_2\leq\cdots\leq r_n$ and write $n(r,d)$ for the number of tasks which are released and due in the closed interval $[r,d]$.

  1. set $F=\emptyset$
  2. for tasks $i=n,n-1,\ldots,1$:
  3.   $c=\min \{ B(r_i,d_j,n(r_i,d_j),F) \mid \forall j: d_j\geq d_i\}$
  4.   if $c<r_i$: return "no feasible schedule"
  5.   else if $r_i\leq c<r_i+1$: set $F=F\cup\{(c-1,r_i)\}$

A straightforward implementation as above would take time $O(n^4)$. Garey et al. show (besides correctness) that by updating the times obtained by Backscheduling, joining overlapping forbidden regions, and making "forbidden" queries $O(1)$ time can be brought down to $O(n^2)$, and by using even better datastructures to $O(n\log n)$.

$\endgroup$
  • 1
    $\begingroup$ Looks promising, but the first and last links go to paywalls, and the second leads to a broken certificate and "500 Internal Server Error" page for me. Could you summarise one of the algorithms, or give a publically accessible link? Thanks! $\endgroup$ – j_random_hacker Jun 30 at 13:00
  • $\begingroup$ Sorry, these articles seems to be hard to come by. Carlier's article is on Research Gate but is in French. I'll see if I can provide a brief summary. $\endgroup$ – Marcus Ritt Jun 30 at 13:13
  • $\begingroup$ That would be great, thanks :) $\endgroup$ – j_random_hacker Jun 30 at 16:46
0
$\begingroup$

Your problem is known as non-preemptive single-machine scheduling with release times and deadlines, with tasks of identical length, and can be solved efficiently using Schrage's greedy heuristic.

Let us first describe the problem more formally. We are given a sequence of time intervals $[r_i,d_i]$ and a sequence of job lengths $p_i$. We want to schedule each job within its interval, so that no two jobs intersect.

In our case $r_i = a_i$, $d_i = b_i + 2$, and $p_i = 2$. The starting time of each job $c_i$ thus satisfies $a_i \leq c_i \leq b_i$, and two jobs conflict if $(c_i,c_i+2)$ intersects $(c_j,c_j+2)$, which is the same as $|c_i - c_j| < 2$. (Without loss of generality, all jobs are scheduled at integer times.)

Schrage's heuristic is a common heuristic which is optimal in some cases, though not necessarily this one. However, other algorithms exist in the literature which do solve this problem efficiently.

$\endgroup$
  • 2
    $\begingroup$ Schrage's heuristic is only optimal for $p_j=1$ not for $p_j=p$ (take $r=(0\:1)$, $d=(5\:3)$, $p=(2\:2)$). Polynomial algorithms for $p_j=p$ have been given by Simons (1978), Carlier (1981), and Garey et al. (1981), the latter in $O(n\log n)$. $\endgroup$ – Marcus Ritt Jun 29 at 1:44
  • $\begingroup$ @MarcusRitt I agree that the heuristic doesn't work. Could you give the links (or at least the titles) for your references? $\endgroup$ – pi66 Jun 29 at 8:56
  • $\begingroup$ I don’t see how the value of $p$ enters the picture. You can divide everything by $p$ to get unit length jobs. $\endgroup$ – Yuval Filmus Jun 29 at 15:12
  • 1
    $\begingroup$ @YuvalFilmus Yes, but then release and due dates may not be integer any more which makes the problem harder. Actually Garey et al. (1981) solve the unit-time problem with non-integer dates, and their algorithm can be applied after dividing everything by $p$. $\endgroup$ – Marcus Ritt Jun 29 at 15:37
0
$\begingroup$

Let A be the smallest of the $a_i$. Then there are two choices for the first $c_i$ to pick that cannot obviously be improved: One, find the i such that $a_i = A$ and $b_i$ is as small as possible, then let $c_i = a_i$. Two, pick j such that $a_j = A+1$, $b_j<b_i$, and $b_j$ as small as possible, then let $c_j=b_j$ (this may not be possible). Then remove that item from the list of intervals, update all $a_i$ to be greater by two than the $c_i$ that was picked, and check that no $b_i$ is too small. Depth first search and backtracking will find a solution.

There is a good chance that this is fast, since the first choice is not bad as a heuristic.

If there are exactly k intervals with $a_i < A$ for some A, and we find k values $c_i <= A-2$ then these $c_i$ are optimal and backtracking for these k items cannot help and will never be needed. On the other hand, if there are too many values $b_i$ too close together, that can be used to prove there is no solution.

Finally, the problem can be approached from the smallest $a_i$, or equally well from the largest $b_i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.