Execution of parallel and interactive applications on a Grid environment is a challenging problem that requires the cooperation of several middleware tools and services. In this paper, we present our experiences in the development of CrossBroker, a job management service that provides transparent and reliable support for such types of applications. We outline the main components of CrossBroker and how they interact with other middleware services. We also describe specific features of the scheduler used to guarantee resource co-allocation for running MPI jobs remotely over multiple machines spread across several Grid sites or to start interactive applications as fast as possible. These features include a simple time-sharing mechanism that allows fast execution of interactive applications even under heavy occupancy of Grid resources.