Interval Scheduling problems present several intervals that may overlap and the usual goal is to find the greater set of non overlapping intervals.

Variations of the problem on wikipedia and such add groups/machines/resources. Groups are sets of intervals, the final result may only have one element of the each group. Machines/resources add extra sets to gather intervals(jobs) in (eg. two machines can consume intervals separately, so the final result will have two sets, one for each machine).

But I can't find the definition/name for a problem where, instead of just $i$ intervals, we are presented with $q$ choices of $i$ intervals (+none if no interval is possible); upon selecting one of the intervals, the other $i-1$ are not available anymore. The goal is to make all $q$ choices and obtain the greatest set of non-overlapping intervals and/or the maximum number of non-"none" choices made.

If you still can't understand, then John the carpenter loves to work, and also loves money. He has to prepare $q$ varied furniture frames, but he also has other matters to attend on his daily life, so he can't just decide to finish them all in a single batch. He has checked his schedule for the week and opened up different time slots he can use to finish each of the frames, a) Help him decide on his final schedule so he can finish the most frames b) so he can stay working the longest.

frame1 1-4 2-5 6-7
frame2 2-3 1-2 5-6
framen 1-7 200-208 5-12

I don't need the problem (which I just made up) solved, just the topic that studies this specific type of problem, if it exists.

  • $\begingroup$ edited, btw by m-machines, g-groups and so on, you mean there is a number of "m" machines (machine1 to machine-m). Upon editing, it looks more like job scheduling (with one machine in the case of the carpenter), but if you can confirm it would be nice. $\endgroup$ – gia Sep 26 '16 at 17:26

Your Answer

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

Browse other questions tagged or ask your own question.