Parallel Machine Scheduling by Column Generation (Revised)

摘要

Parallel machine scheduling problems concern the scheduling of n jobs on m211u001emachines to minimize some function of the job completion times. If preemption is 211u001enot allowed, then most problems are not only NP-hard, but also very hard from a 211u001epractical point of view. In this paper, the authors show that strong and fast 211u001elinear programming lower bounds can be computed for an important class of machine 211u001escheduling problems with additive objective functions. Characteristic of these 211u001eproblems is that on each machine the order of the jobs in the relevant part of 211u001ethe schedule is obtained through some priority rule. To that end, the authors 211u001eformulate these parallel machine scheduling problems as a set covering problem 211u001ewith an exponential number of binary variables, n covering constraints, and a 211u001esingle side constraint.