Shifts and swaps are already good neighborhoods for the Generalized Assignment Problems:
- Shift: move a task to another worker
- Swap: swap the workers of two tasks
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:
- Yagiura M, Ibaraki T, Glover F (2006) A path relinking approach with ejection chains for the generalized assignment problem. European Journal of Operational Research 169:548–569. https://doi.org/10.1016/j.ejor.2004.08.015
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