Title: A two-stage approach to solving large capacitated task allocation problems

Authors: Mark Lewis, Gary Kochenberger

Addresses: Craig School of Business, Missouri Western State University, 4525 Downs Dr., Saint Joseph, Missouri, 4507, USA. ' School of Business, University of Colorado, 1250 14th St., Suite 215, Colorado, 80217 Denver, USA

Abstract: This paper presents a simple, two-stage method, implemented in the commonly available Excel spreadsheet program, for quickly finding high quality solutions to larger, more difficult instances of the capacitated task allocation problem (CTAP) than have been previously reported. In Stage 1, an innovative modification of the approximation method of Griffith and Stewart is used to reformulate CTAP and find a near-integer solution. Based on the partial solution from Stage 1, the remaining tasks are allocated in a greatly reduced quadratic CTAP solved in Stage 2. Our results show that this approach yields very good solutions relatively quickly to very large problems (1,000 binary variables and 49,500 quadratic terms in the objective function). Ours is the first paper to modify the continuous approximation method of Griffith and Stewart to solve 0/1 problems and the first article to demonstrate the successful use of an Excel-based approach for solving very large CTAP problems.

Keywords: capacitated task allocation; integer programming; heuristics; approximation programming; quadratic program; Excel Solver; spreadsheet modelling; mathematical modelling.

DOI: 10.1504/IJMMNO.2010.035425

International Journal of Mathematical Modelling and Numerical Optimisation, 2010 Vol.1 No.4, pp.259 - 273

Published online: 30 Sep 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article