Scheduling a shared resource among parallel dedicated machines: a red-blue knapsack modeling approach

We consider a scheduling problem with dedicated parallel machines and a shared resource. Each job to be scheduled is assigned to a specific machine and can possibly be rejected if it cannot be scheduled within a predetermined time frame. Some of the jobs need an additional shared resource to be processed: this resource has to be conservatively scheduled, i.e must be assigned to each machine in a single non-overlapping time window. The goal is to schedule the largest possible amount of jobs (weighted by priority) in the given time frame. The problem originates from an operating room scheduling application and can be modelled as a multiple knapsack problem with additional constraints related to the scheduling of the shared resource. We establish the complexity of the problem, develop an effective MILP model and a non standard column generation approach that considerably shorten the computation times required to compute optimal solutions.