You’re given a set of jobs and integers $$$x$$$ and $$$y$$$. Each job is represented by a time interval $$$[l, r]$$$ (integral endpoints, $$$0 \leq l \lt r \leq y$$$). The goal is to find an assignment of jobs to machines (assume that we have an infinite number of identical machines) which minimizes the number of machines used, while also satisfying the following:
- Each job is assigned to some machine.
- No two jobs assigned to the same machine intersect (but their endpoints can touch, so $$$[a, b]$$$ and $$$[b, c]$$$ can be assigned to the same machine).
- Every used machine has some contiguous “break interval” of length $$$x$$$, which doesn’t intersect with any job assigned to that machine (once again, endpoints can touch). In other words, there is some contiguous time period of length $$$x$$$ where no job is being executed on it.
I’m pretty sure there isn’t an exact solution in P, so I’m looking for decent approximation algorithms.
I could only think of a simple approximation algorithm with a bad approximation factor that's heavily dependent on the input data (although I'm pretty sure I could make a cursed div-2 D out of it).
There are also some pretty easy exact solutions which are exponential in the number of machines (which, unlike those exponential in the number of jobs, can occasionally be practical to run), but they're not interesting.
Are there any assumptions on the input data that would make this problem solvable in an interesting manner?
I would also be grateful if someone could direct me towards existing work on related problems if they know of it.








I don't understand the third bullet point, can you explain it?
Consider the set of jobs/intervals assigned to some machine. Then for every machine: after we assign the given intervals, it should be possible to assign an additional interval (not present in the original set) of length $$$x$$$ somewhere within the timeline $$$[0, y]$$$, such that it doesn't intersect with any of the old intervals on this machine (boundaries can touch).
is it correct to say that for 2 jobs/intervals to be assigned into the same machine(which was empty) they have to:
this is what I understand from 3rd point.
No that's not what it means.
Consider the following setup:
The assignment on this machine is valid because we can place a contiguous length-4 interval in some gap after this assignment (in this case, we can place one at $$$[3, 7], [12, 16], [13, 17]$$$). We do not need to be able to place a break between every pair of adjacent intervals, just once somewhere.
So in this case, it doesn't matter that we cannot place a break between $$$[7, 9]$$$ and $$$[10, 12]$$$.
I see, thanks.
I thought the problem was easy, turns out I just read 3rd point wrong.
Unfortunately I most likely won't solve your problem. Though, I will learn about the standard machine assignment problem soon.
How did you prove that there isn't an exact solution in P?
If i understood your question correctly, then i have an idea. So, let us try to do binary function on the minimum no of machines. Cause if job can be done in m machines then for sure can be done with m+1, m+2 ... machines.
Now, how my check function will look? i will do something like sweep line with sorting the ranges with there l parameter also i will maintain two sets, lets name them, working and idle.
working set will store end pos, machine id of the machine which are currently working.
idle set will store three info -> GotBreak, last ended job pos, machine id.
ok so GotBreak is a (0,1) which tells whether the machine got that x length break or not, last job ended position is just the endpoint of job which the machine did and lastly the machine id.
by updating GotBreak of every idle machine(i.e. when we reach a point where its last job done is atleast x position behind) and these sets. Now the last part left is how to assign the job to a machine. i say that the last element of idle set is best why?
so first if you have a machine which already have break nothing issue. now if no machine have break so assigning the job to machine which has finished its job latest is optimal ig?
and if set is empty then for sure return false, and at end if everyone got break then return true. I am not able to find whats incorrect in this approach. compression and all i can get this in nlog^2n ig maybe.
I, on the other hand, am not able to find what’s correct in this approach.
umm, can you explain what?
can you explain your idea through code or at least pseudo-code? in its current (extremely ambiguous) form, it just feels incorrect at worst and doubtful at best
i will do binary search on machines. code might be buggy but idea is more or less same.
This is obviously incorrect. Consider $$$x = 1, y = 3$$$, with intervals $$$[0, 1], [1, 2], [1, 3]$$$.
We can use 2 machines in the following way:
Your algorithm does not find this configuration, and requires 3 machines instead.
ohh right right, got my mistake thankss. will think over it
can you provide few test cases so that i can test if i get some logic?
I believe there is a trivial 2-approximate algorithm (btw, I'm not sure that this problem is NP-hard, do you have any proof?).
Solve the problem with $$$x = 0$$$ exactly, then consider each machine in the optimal solution. I claim that each task $$$[l, r]$$$ is such that either $$$r \le y - x$$$ or $$$l \ge x$$$, otherwise $$$[l, r]$$$ can't even be placed alone on one machine, and the answer is NO. Now consider the optimal answer for $$$x = 0$$$ and split each machine into two: the first will have tasks such that $$$r \le y - x$$$ (break interval $$$[y - x, y]$$$), and the second will have tasks such that $$$l \ge x$$$ (break interval $$$[0, x]$$$). This way we have $$$ans \le 2opt_{x = 0} \le 2opt$$$.
obvious and worse than the one in the blog
I don't understand what's the point of creating a blog to ask people to solve an open problem for you and respond comments with "obvious", "extremely ambiguous".
Dude... CP community is sometimes the worst.
It is NP-hard because Job Scheduling Problem is NP-hard and infact this problem is a more general form of Job Scheduling problem, so if one can solve this is polynomial time then the former won't be a NP-hard.
The problem can be solved using integer linear programming and applying some traditional ILP solvers.
It is NP-hard because Job Scheduling Problem is NP-hard
this problem is a more general form of Job Scheduling problem
Not really, job scheduling usually assumes that job start times are not fixed
Isn't it not guaranteed that a solution even exists? If some job's time interval doesn't allow a break interval even if it's the only one on its machine, for example.
yes