The first sentence is actually just incorrect...
Having done his homework, George went out and had a long-awaited beer.
You don't need the "after" because the idea of completeness exists in the choice of the tense.
You'd use "having done" to connect the completeness of the homework to the action that comes next -- the beer. This is connecting past action to present conditions.
Having won some money, I started thinking about which car to buy.
For the second sentence, the "doing his homework" is a gerund (a noun phrase made from verbs in different forms)...