A percentile search heuristic for generalized assignment problems with a very large number of jobs

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.