A two-stage approach to solving large capacitated task allocation problems
type: Item
instance of: scholarly article
title: A two-stage approach to solving large capacitated task allocation problems
zbMATH Open document ID: 1209.90272
DOI: 10.1504/IJMMNO.2010.035425
author: Mark W. Lewis
author: Gary A. Kochenberger
published in: International Journal of Mathematical Modelling and Numerical Optimisation
publication date: 2010-12-27T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 5829525
zbMATH Keywords: task allocation
zbMATH Keywords: integer programming
zbMATH Keywords: heuristics
zbMATH Keywords: approximation programming
zbMATH Keywords: quadratic program
zbMATH Keywords: Excel solver
zbMATH Keywords: spreadsheet modelling
zbMATH Keywords: mathematical modelling
describes a project that uses: Excel
MaRDI profile type: Publication
full work available at URL: ijmmno.2010.035425
OpenAlex ID: W2039017711
description: scientific article; zbMATH DE number 5829525