Is this problem NP-hard?
in [Math]
|
Prev: Question about maximality principles, lattices, AC and its equivalents
Next: Energy of whole atom radiates at fusion/fission
From: Shinchiro Izumi on 25 Jul 2010 16:42 Hello, I've run across the following combinatorial optimization problem, and while it's a very straightforward problem I haven't been able to find it discussed in the literature. Can anyone suggest any thoughts or references on the matter? The input to my problem is a collection of "jobs", each with a start time s_i and an end time t_i. I have a collection of N workers, each who can work for a consecutive duration D (so if a worker starts at time t, he must finish at time t + D). We know that t_i - s_i <= D, so that any job can be covered by one worker. However, each worker can only work on one job at a time, and also we can split a job between two workers. For example, if my jobs have start and end times [1, 3], [3, 5], and [5,7], and my duration constraint is D = 3, then I can cover all three jobs by having one worker start at time 1 (ending at time 4) and the other starting at time 4 (ending at time 7). Thus, my question is: what's the maximum number of jobs I can satisfy with these workers? Alternatively, what's the maximum total time (of all jobs) that I can satisfy (while fully satisfying all those jobs that I choose to satisfy)? Does this become easier if all jobs have the same duration? This problem is well-studied (and known to be NP-hard) if I require that the jobs be un-splittable, but the question "can I satisfy all jobs with N workers" is in P when the jobs are splittable. Thus, this problem seems to land right in between those two, and I'm not sure what the complexity of the problem is. Thank you! SI
From: Ray Vickson on 25 Jul 2010 18:07 On Jul 25, 1:42 pm, Shinchiro Izumi <shinchiroiz...(a)hotmail.com> wrote: > Hello, > I've run across the following combinatorial optimization problem, and > while it's a very straightforward problem I haven't been able to find > it discussed in the literature. Can anyone suggest any thoughts or > references on the matter? > > The input to my problem is a collection of "jobs", each with a start > time s_i and an end time t_i. I have a collection of N workers, each > who can work for a consecutive duration D (so if a worker starts at > time t, he must finish at time t + D). We know that t_i - s_i <= D, > so that any job can be covered by one worker. However, each worker > can only work on one job at a time, and also we can split a job > between two workers. For example, if my jobs have start and end times > [1, 3], [3, 5], and [5,7], and my duration constraint is D = 3, then I > can cover all three jobs by having one worker start at time 1 (ending > at time 4) and the other starting at time 4 (ending at time 7). Thus, > my question is: what's the maximum number of jobs I can satisfy with > these workers? Alternatively, what's the maximum total time (of all > jobs) that I can satisfy (while fully satisfying all those jobs that I > choose to satisfy)? Does this become easier if all jobs have the same > duration? > > This problem is well-studied (and known to be NP-hard) if I require > that the jobs be un-splittable, but the question "can I satisfy all > jobs with N workers" is in P when the jobs are splittable. Thus, this > problem seems to land right in between those two, and I'm not sure > what the complexity of the problem is. > > Thank you! SI If the satisfiability problem ("can we do all jobs with N workers?") is in P, and if the s_i, t_i and D are all integers, you can solve the optimization problem in polynomial time. You know maximum and minimum N values (N_max = n = number of jobs and N_min = 1). Now do a bisecting search on N, each time answering the satisfiability question. When the resulting N-interval is < 1 you will have identified the optimal integer value of N. The number of needed yes/no questions is polynomial in n, so the entire algorithm runs in polynomial time. (This is a standard trick in complexity theory for converting an optimization problem into a sequences of yes/no questions.) R.G. Vickson
From: Sayaka Fujisaki on 25 Jul 2010 19:37 Hi, I think that what Shinchiro is asking is, given a fixed number of workers N, to determine the maximum number of jobs they can complete (or the maximum number of hours of jobs one can complete, subject to the constraint that we get no "partial credit" for doing only half a job). The fact that the decision problem of whether we can satisfy all jobs with N workers is in P only tells us that if we _can_ satisfy all jobs, then the problem becomes easy. Cheers, SF On Jul 25, 5:07 pm, Ray Vickson <RGVick...(a)shaw.ca> wrote: > On Jul 25, 1:42 pm, Shinchiro Izumi <shinchiroiz...(a)hotmail.com> > wrote: > > > > > Hello, > > I've run across the following combinatorial optimization problem, and > > while it's a very straightforward problem I haven't been able to find > > it discussed in the literature. Can anyone suggest any thoughts or > > references on the matter? > > > The input to my problem is a collection of "jobs", each with a start > > time s_i and an end time t_i. I have a collection of N workers, each > > who can work for a consecutive duration D (so if a worker starts at > > time t, he must finish at time t + D). We know that t_i - s_i <= D, > > so that any job can be covered by one worker. However, each worker > > can only work on one job at a time, and also we can split a job > > between two workers. For example, if my jobs have start and end times > > [1, 3], [3, 5], and [5,7], and my duration constraint is D = 3, then I > > can cover all three jobs by having one worker start at time 1 (ending > > at time 4) and the other starting at time 4 (ending at time 7). Thus, > > my question is: what's the maximum number of jobs I can satisfy with > > these workers? Alternatively, what's the maximum total time (of all > > jobs) that I can satisfy (while fully satisfying all those jobs that I > > choose to satisfy)? Does this become easier if all jobs have the same > > duration? > > > This problem is well-studied (and known to be NP-hard) if I require > > that the jobs be un-splittable, but the question "can I satisfy all > > jobs with N workers" is in P when the jobs are splittable. Thus, this > > problem seems to land right in between those two, and I'm not sure > > what the complexity of the problem is. > > > Thank you! SI > > If the satisfiability problem ("can we do all jobs with N workers?") > is in P, and if the s_i, t_i and D are all integers, you can solve the > optimization problem in polynomial time. You know maximum and minimum > N values (N_max = n = number of jobs and N_min = 1). Now do a > bisecting search on N, each time answering the satisfiability > question. When the resulting N-interval is < 1 you will have > identified the optimal integer value of N. The number of needed yes/no > questions is polynomial in n, so the entire algorithm runs in > polynomial time. (This is a standard trick in complexity theory for > converting an optimization problem into a sequences of yes/no > questions.) > > R.G. Vickson
From: Sayaka Fujisaki on 26 Jul 2010 17:00
Hi Shinchiro, Rob Pratt showed that the problem is in P when no two jobs overlap, or when all jobs have integer start and end points and have length 1. It comes from the natural formulation of the problem as an integer program as the constraint matrix is totally unimodular. The link to the thread for google groups is http://groups.google.com/group/sci.math/browse_thread/thread/4c2330ac4115f3ee# However, I don't see an obvious reduction from your problem to these, so hopefully someone smarter than me can help for the general case. SF On Jul 25, 3:42 pm, Shinchiro Izumi <shinchiroiz...(a)hotmail.com> wrote: > Hello, > I've run across the following combinatorial optimization problem, and > while it's a very straightforward problem I haven't been able to find > it discussed in the literature. Can anyone suggest any thoughts or > references on the matter? > > The input to my problem is a collection of "jobs", each with a start > time s_i and an end time t_i. I have a collection of N workers, each > who can work for a consecutive duration D (so if a worker starts at > time t, he must finish at time t + D). We know that t_i - s_i <= D, > so that any job can be covered by one worker. However, each worker > can only work on one job at a time, and also we can split a job > between two workers. For example, if my jobs have start and end times > [1, 3], [3, 5], and [5,7], and my duration constraint is D = 3, then I > can cover all three jobs by having one worker start at time 1 (ending > at time 4) and the other starting at time 4 (ending at time 7). Thus, > my question is: what's the maximum number of jobs I can satisfy with > these workers? Alternatively, what's the maximum total time (of all > jobs) that I can satisfy (while fully satisfying all those jobs that I > choose to satisfy)? Does this become easier if all jobs have the same > duration? > > This problem is well-studied (and known to be NP-hard) if I require > that the jobs be un-splittable, but the question "can I satisfy all > jobs with N workers" is in P when the jobs are splittable. Thus, this > problem seems to land right in between those two, and I'm not sure > what the complexity of the problem is. > > Thank you! SI |