ABSTRACT
This chapter reviews heuristic and metaheuristic algorithms for generalized assignment problem and explores the problem formally and introduces some related problems and their complexities. It explains basic strategies of greedy method and local search and describes Lagrangian relaxation problems. The chapter provides some basic ideas of Lagrangian heuristics and also describes the basics of branch-and-bound. It analyses some computational results of various metaheuristic algorithms and branch-and-bound methods. The chapter focuses on polynomial-time approximation algorithms with performance guarantees. There are several useful tools used to design approximation algorithms. Metaheuristic algorithms are widely recognized as one of the most practical approaches for hard combinatorial optimization problems. Algorithm path relinking with ejection chains applies ejection chains probes to solutions generated by path relinking, which is a methodology to generate solutions from two or more solutions.
