Using Column Generation to Solve Parallel Machine Scheduling problems With Minmax Objective Functions

We present a solution framework for a number of scheduling problems in which the goal is to find a feasible schedule that minimizes some objective function of the minimax type on a set of parallel, identical machines, subject to release dates, deadlines, and/or generalized precedence constraints.

After having derived the lower bound on the objective function by column generation, we try to find a matching upper bound by identifying a feasible schedule with objective function value equal to this lower bound. Our computational results show that our lower bound is so strong that this is almost always possible.

We present applications to resource constrained project scheduling and to crew assignment within vehicle routing.

• Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars