A two-stage approach to solving large capacitated task allocation problems Online publication date: Thu, 30-Sep-2010
by Mark Lewis, Gary Kochenberger
International Journal of Mathematical Modelling and Numerical Optimisation (IJMMNO), Vol. 1, No. 4, 2010
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Mathematical Modelling and Numerical Optimisation (IJMMNO):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook