Integer programming techniques for makespan minimizing workforce assignment models that recognize human learning

We study optimization techniques for makespan minimizing workforce assignment problems wherein human learning is explicitly modeled. The key challenge in solving these problems is that the learning functions that map experience to worker productivity are usually nonlinear. This paper presents a set of techniques that enable the solution of much larger instances of such problems than seen in the literature to date. The first technique is an exact linear reformulation for the general makespan minimizing workforce assignment models with learning. Next, we introduce a computationally efficient means for generating an initial feasible solution (which our computational experiments indicate is often near-optimal). Finally, we present methods for strengthening the formulation with cover inequalities and a lower bound on the objective function value of the optimal solution. With an extensive computational study we demonstrate the value of these techniques and that large instances can be solved much faster than have previously been solved in the literature. To focus the paper on the presented methodology, we solve a makespan minimizing workforce assignment problem that has few complicating constraints. However, the techniques can be adapted to speed up the solution of most any makespan minimizing workforce assignment problem.