Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores

We consider a scheduling problem with machine dependent intervals, where each job consists of m fixed intervals, one on each of the m machines. To schedule a job, exactly one of the m intervals needs to be selected, making the corresponding machine busy for the time period equal to the selected interval. The objective is to schedule a maximum number of jobs such that no two selected intervals from the same machine overlap. This problem is np-hard and admits a deterministic 1 / 2-approximation. The problem remains np-hard even if all intervals have unit length, and all m intervals of any job have a common intersection. We study this special case and show that it is apx-hard, and design a 501 / 1000-approximation algorithm