Grid computing systems are being positioned as a computing infrastructure of the future that will enable the usage of wide-area network computing systems for a variety of challenging applications. The multimedia enabled Grid (MEG) is an extension of the Grid concept to support the deployment of multimedia services to meet the ever increasing demand for multimedia from users engaging in a wide range of activities such as scientific research, education, commerce, and entertainment. The MEG will provide several new services and sustain several enabling technologies to support multimedia. To provide an adequate level of service to multimedia applications, it is often necessary to simultaneously allocate the resources including predetermined capacities from the interconnecting networks to the applications. The simultaneous allocation of resources is often referred to as co-allocation in the Grid literature. In this thesis, I propose a novel scheme called synchronous queuing (SQ) for implementing co-allocation with quality of service (QoS) assurances in Grids. The SQ does not require advance reservation capabilities at the resources, which is a fundamental difference between SQ and the other existing schemes. I formally define the co-allocation problem and classify existing approaches based on a taxonomy that is presented here. Based on the taxonomy, I discuss the situations under which SQ can be used for co-allocation in MEGs. The SQ scheduler introduces new scheduling concepts such as the notion of accounting for the previous work, the notion of introducing intraQueue and interQueue schedulers and the notion of calculating the co-allocation skew. Simulation studies performed to evaluate SQ indicate that it outperforms admission control-based scheme by a significant margin.