© 2016 IEEE.Web-based service-oriented grid computing refers to a distributed computing system comprising a collection of interconnected and virtual computers that provides web-based services via the Internet. These services are based on Service Level Agreements (SLAs) established by negotiation between service providers and consumers. SLAs are contractual obligations that define the mutually agreed understandings and expectations in terms of Quality of Service (QoS) values for the provision of services. How to automatically conduct the service level agreement negotiations between service providers and consumers so as to successfully achieve the desired QoSs is one of the significant research challenge in web-based service-oriented grid computing. In this paper, we proposed a graph-based approach to model service level agreement negotiations by considering their interdependency relationships and concurrency. A Colour Petri Net-based service level agreement negotiation protocol was also proposed to concurrently conduct multiple service level agreement negotiations. With the proposed approach and protocol, service level agreement negotiations can be efficiently and concurrently processed and the service level agreements can be efficiently achieved. Experimental results also indicate the effectiveness and efficiency of the proposed approach and protocol in terms of the negotiation success rate, the negotiation time and the negotiation outcome.