### Help me prove (or disprove) the following problem NP-hard

Posted:

**Sat Jun 09, 2018 9:42 am UTC**This came up when I was thinking about something in a video game (Starcraft 2 to be exact), but I've modified the description to be simpler to understand.

Given a set of jobs that each have a fixed start and end time (a, b), and a set of workers that each have a shift during which they are available to work (x, y), find a valid assignment of jobs to workers such that all jobs are completed and a worker never has two jobs at the same time. For a worker to perform a job the job must be entirely within the worker's shift. Jobs cannot be performed at times other than what is given, they cannot be paused and resumed later, nor can they be handed off to a different worker.

Examples:

Jobs:

j1=(1, 3)

j2=(4, 6)

Workers:

w1=(0, 6)

Solution:

w1={j1, j2}

Jobs:

j1=(1, 3)

j2=(2, 4)

Workers:

w1=(0, 5)

No valid solution (only one worker but the two jobs overlap)

Jobs:

j1=(1, 3)

j2=(2, 4)

Workers:

w1=(0, 5)

w2=(2, 6)

Solution:

w1={j1}

w2={j2}

Jobs:

j1=(0, 3)

j2=(1, 4)

j3=(2, 5)

j4=(3, 6)

j5=(4, 6)

j6=(5, 7)

Workers:

w1=(0, 7)

w2=(1, 7)

w3=(2, 6)

No valid solution. This is the simplest non-trivial example of no solution I could come up with, where it can't be shown just by comparing the number of workers to the number of jobs at any single time. But j1 can only be assigned to w1, which forces j2 to be assigned to w2, forcing j3 to be assigned to w3, then j4 must be assigned to w1, j5 to w2, then finally only w3 is available, but j6 cannot be assigned because it is outside of their shift.

So far I have shown that the problem can be reduced to graph coloring: The jobs are vertices, and two jobs have an edge if they are in conflict with each other (overlapping times). Workers correspond to colors, and worker shifts can be encoded by adding an extra vertex of the worker's color with an edge going to each job outside of their shift, ensuring that those vertices cannot have that worker's color. However, this reduction goes the opposite direction of what I need. What I need is to show that some NP-hard problem can be encoded in my problem. I feel like graph coloring or some kind of set cover will have the most promise, but I haven't been able to get it yet. I also looked for other NP-hard problems that might be similar to mine, but did not find any that were obviously so.

Given a set of jobs that each have a fixed start and end time (a, b), and a set of workers that each have a shift during which they are available to work (x, y), find a valid assignment of jobs to workers such that all jobs are completed and a worker never has two jobs at the same time. For a worker to perform a job the job must be entirely within the worker's shift. Jobs cannot be performed at times other than what is given, they cannot be paused and resumed later, nor can they be handed off to a different worker.

Examples:

Jobs:

j1=(1, 3)

j2=(4, 6)

Workers:

w1=(0, 6)

Solution:

w1={j1, j2}

Jobs:

j1=(1, 3)

j2=(2, 4)

Workers:

w1=(0, 5)

No valid solution (only one worker but the two jobs overlap)

Jobs:

j1=(1, 3)

j2=(2, 4)

Workers:

w1=(0, 5)

w2=(2, 6)

Solution:

w1={j1}

w2={j2}

Jobs:

j1=(0, 3)

j2=(1, 4)

j3=(2, 5)

j4=(3, 6)

j5=(4, 6)

j6=(5, 7)

Workers:

w1=(0, 7)

w2=(1, 7)

w3=(2, 6)

No valid solution. This is the simplest non-trivial example of no solution I could come up with, where it can't be shown just by comparing the number of workers to the number of jobs at any single time. But j1 can only be assigned to w1, which forces j2 to be assigned to w2, forcing j3 to be assigned to w3, then j4 must be assigned to w1, j5 to w2, then finally only w3 is available, but j6 cannot be assigned because it is outside of their shift.

So far I have shown that the problem can be reduced to graph coloring: The jobs are vertices, and two jobs have an edge if they are in conflict with each other (overlapping times). Workers correspond to colors, and worker shifts can be encoded by adding an extra vertex of the worker's color with an edge going to each job outside of their shift, ensuring that those vertices cannot have that worker's color. However, this reduction goes the opposite direction of what I need. What I need is to show that some NP-hard problem can be encoded in my problem. I feel like graph coloring or some kind of set cover will have the most promise, but I haven't been able to get it yet. I also looked for other NP-hard problems that might be similar to mine, but did not find any that were obviously so.