Scheduling a shared resource among parallel dedicated machines: a red-blue knapsack modeling approach
研究了并行专用机环境下共享资源的调度问题，将问题建模为带额外约束的多背包问题，并提出了混合整数线性规划模型和列生成方法，以快速求解最优调度方案。
Abstract 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.