4
$\begingroup$

There are $n$ jobs where each job $i$ has an arrival time $r_i$, a deadline $d_i$ and a cost $c_i$. The problem is to find a scheduling time $t_i$ (where $r_i\leq t_i\leq d_i$) for each job $i$ in order to minimize $$\sum_i\max_{j\in S_i}(c_j),$$ where $S_i$ is the set of jobs scheduled at time $t_i$.

Can we solve this problem in polynomial-time or is it NP-hard?

For example, if all jobs can be scheduled at the same time $t$, then the objective will be $\max(c_1,c_2,\ldots,c_n)$. The issue is that all jobs cannot always be scheduled at the same time $t$ because of their arrival times and deadlines. If I schedule the jobs as they arrive, I may end up with the objective of $\sum_{i=1}^nc_i$, which is the largest possible. So, the problem is somehow how to partition the jobs into sets $S_i$ (where jobs in $S_i$ are scheduled at the same time) for which we obtain the minimum objective. As such, I am trying to reduce Partition to this scheduling problem but still did not find the right reduction. Do you have any hints?

$\endgroup$
  • $\begingroup$ Do jobs have a length as well? How many jobs can performed at the same time? The information given seems strange to me. $\endgroup$ – gnasher729 Jul 24 '18 at 20:01
  • $\begingroup$ Jobs have the same length (say 1). You can schedule as many jobs as you want in a single time. $\endgroup$ – zdm Jul 24 '18 at 20:03
1
$\begingroup$

The following observation enables a polynomial-time algorithm:

Whenever the time slot $t_i$ for a job $i$ has been chosen, it's optimal to assign the same time slot for all lower-cost jobs that overlap $t_i$, as doing so will incur zero additional cost. Therefore, choosing the time slot for the most costly job "magnetises" all the jobs that can be assigned the same time slot, and partitions the remaining jobs into two sets: those whose intervals are completely to the left of this time slot, and those whose intervals are completely to the right. The subproblems for these two sets of jobs can then be solved independently.

A general subproblem can be described by an interval $(a, b)$ and a maximum cost $c$: the jobs in this subproblem consist of all those jobs whose intervals fall within $(a, b)$ and which have cost at most $c$. The optimal solution for a subproblem can be found by trying every possible time slot for the most costly job in the subproblem, and solving the corresponding 2 subproblems for each attempt. A plain recursive strategy would take exponenential time, but there are only $O(n^3)$ distinct subproblems to solve: There are only $O(n)$ "basic intervals" (maximal intervals that do not cross the beginning or end of any job interval) to consider, so there are at most $O(n^2)$ possible intervals (blocks) of these, and $O(n)$ possible different job costs. Thus dynamic programming can be applied. It should be possible to test each of the $O(n)$ possible time slots available for the most costly job in $O(1)$ time each, excluding the time needed to solve subproblems, for $O(n^4)$ time and $O(n^3)$ space overall -- not fast, but certainly polynomial.

$\endgroup$
  • 3
    $\begingroup$ It seems $c$ is needless for your subproblem. How can you test each time slot in $O(1)$ since you need to partition all the jobs? $\endgroup$ – xskxzr Jul 25 '18 at 6:07
  • $\begingroup$ @xskxzr: I think you're right about $c$ being unnecessary. I should have written $O(1)$ amortised time for testing each time slot -- this shouldn't be hard, since the changes in the two sets can be easily found by walking a sorted list of endpoints. You don't need to start partitioning afresh for each slot. $\endgroup$ – j_random_hacker Jul 25 '18 at 7:27
  • $\begingroup$ Can you apply your algorithm to some example? I did this on the following 3-jobs instance. Job $i$ is denoted as $(r_i,d_i,c_i)$. Job 1 is given by $(1, 2, 1)$. Job 2 is given by $(2, 3, 3)$. And job 3 is given by $(3, 3, 2)$. Your algorithm (if I am not mistaken) schedules job 1 and job 2 at $2$ and job 3 at $3$, which gives the total cost of $\max(1,3)+2=5$. However, if job 1 is scheduled at $2$ and job 2 and job 3 are scheduled at $3$, then the total cost will be $1+\max(2,3)=4$. $\endgroup$ – zdm Jul 25 '18 at 14:03
  • $\begingroup$ Also, how do you find the scheduling time of the most costly job? $\endgroup$ – zdm Jul 26 '18 at 14:20
  • 2
    $\begingroup$ Hi @j_random_hacker. I tried to compute the complexity of your algorithm but I didn't understand the following: If I split the $n$ jobs equally in each time, I will have $n/2$ and $n/2$, etc. So, finally I will have $O(n)$ subproblems, right? Why do you said $O(n^2)$? Thanks. $\endgroup$ – zdm Aug 20 '18 at 0:56

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.