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

Huan Jin, Barrett W. Thomas, Mike Hewit

Research output: Journal PublicationArticlepeer-review

15 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)202-211
Number of pages10
JournalComputers and Industrial Engineering
Volume97
DOIs
Publication statusPublished - 1 Jul 2016
Externally publishedYes

Keywords

  • Integer programming
  • Learning curves
  • Makespan
  • Non-linear programming
  • Task assignment

ASJC Scopus subject areas

  • Computer Science (all)
  • Engineering (all)

Fingerprint

Dive into the research topics of 'Integer programming techniques for makespan minimizing workforce assignment models that recognize human learning'. Together they form a unique fingerprint.

Cite this