Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
If I want to try a greedy randomized adaptive search procedure for the generalized assignment problem (assign N tasks to N workers to minimize the total costs), the GRASP method requires 2 parts
For my local search function N(S), what are some other methods to try instead of doing 2 random assignment swaps?
Shifts and swaps are already good neighborhoods for the Generalized Assignment Problems:
Another neighborhood found in some good approaches for the Generalized assignment Problem based on local search is the ejection chain neighborhood.
An additional improvement is to reduce the size of the neighborhoods based on lagrangian multipliers.
For more details about these components, you can look at the following article:
Note that a "raw" GRASP scheme is not likely to work very well for the Generalized Assignment Problem since finding a good solution requires a lot of moves and requires to often get out of local optima. If a full restart is performed at the first local optimum found, the initial solution might not have improved enough
