The single-processor scheduling problem with time restrictions: complexity and related problems (Q2304117)

The authors consider the single machine scheduling problem without preemptions supposing that all feasible solutions are restricted to the schedules where any time interval of length \(\alpha\) can intersect at most \(B\) jobs. The purpose is to find a schedule with the minimal completion time. It is proved that the considered problem is binary NP-hard by giving a reduction from the two parallel machines scheduling problem with a single server and equal processing times. Two mixed integer programming models are developed: ``time-indexed'' and ``assignment and positional date variables''. The performance of both models is compared on instances of up to 50 jobs. It is shown that the second model can find optimal solutions for instances of up to 500 jobs for \(B=10\), \(\alpha =100\) with the CPU time limit of one hour.