Self-organising multi-agent systems provide a suitable paradigm for developing autonomic computing systems that manage themselves. Towards this goal, we demonstrate a robust, decentralised approach for structural adaptation in explicitly modelled problem solving agent organisations. Based on self-organisation principles, our method enables the agents to modify their structural relations to achieve a better allocation of tasks in a simulated task-solving environment. The agents reason on when and how to adapt using only their history of interactions as guidance. We empirically show that, in both closed and dynamic organisations, the performance of organisations using our method is close to that of an upper bound centralised allocation method and considerably better than a random adaptation method.