A PERCENTILE SEARCH HEURISTIC FOR GENERALIZED ASSIGNMENT PROBLEMS WITH A VERY LARGE NUMBER OF JOBS

A. J. Higgins ()
Additional contact information
A. J. Higgins: CSIRO Sustainable Ecosystems, Level 3, QBP, 306 Carmody Road, St. Lucia 4067, Australia

Asia-Pacific Journal of Operational Research (APJOR), 2005, vol. 22, issue 02, 171-188

Abstract: This article presents a new heuristic for generalized assignment problems with a very large number of jobs. The heuristic applies a probabilistic acceptance of a move, based on a percentile threshold, using information from recent moves. This percentile search heuristic (PSH) is compared to tabu search, simulated annealing, and threshold accepting using a rigorous computational experimentation with randomly generated problem instances of up to 50,000 jobs and 40 agents. The PSH did find the best solution among the heuristics for 45% of the instances, particularly larger size problems, versus 30% for tabu search, but required more fine-tuning of the heuristic parameters.

Keywords: Heuristics; generalized assignment; randomized search (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595905000492
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:22:y:2005:i:02:n:s0217595905000492

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595905000492

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().