Nowadays, the Earth observation systems involve multiple satellites, multiple ground stations, and multiple end-users that formulate various observation requests. These requests might be heterogeneous (stereoscopic observations, periodic observations, systematic observations, etc.), and one difficulty is that the search space defined by the possible ways of performing the requests given the multiple satellites and ground stations available is huge. This paper studies several combinatorial optimization techniques for solving such an operational problem, including a constraint programming approach and parallel scheduling techniques that take advantage of the problem structure. These algorithms are evaluated on realistic instances involving various request types and objective functions depending on the cloud cover conditions, that highly impact the quality of the images collected.