This paper proposes and evaluates a new airline disruption management policy using agent-based modelling, simulation, and verification. The new policy is based on a multi-agent negotiation protocol and is compared with three airline policies based on established industry practices. The application concerns Airline Operations Control whose core functionality is disruption management. In order to evaluate the new policy, a rule-based agent-based model of the AOC and crew processes has been developed. This model is used to assess the effects of multi-agent negotiation on airline performance in the context of a challenging disruption scenario. For the specific scenario considered, the multi-agent negotiation policy outperforms the established policies when the agents involved in the negotiation are experts. Another important contribution is that the paper presents a logic-based ontology used for formal modelling and analysis of AOC workflows.