Many domains, such as disaster response, agriculture, construction, and mining, require the coordination of teams of robots and humans to accomplish a collection of spatially distributed tasks. Each agent (robotic or human) has specific capabilities that make that agent particularly suited to certain tasks. While some tasks are independent of each other, other tasks may be related by different constraints. These constraints are in some cases a result of the complementary capabilities of robots and humans which require them to cooperate to achieve certain goals. Many tasks may have a fixed pre-specified location at which they must be performed, but others may require movement from one location to another, and yet others may have a choice of locations where they may take place. In the face of this complexity, the problem of coordinating a team of robots and humans to achieve the desired goals is an important one. This vision of effective human-robot teams working together efficiently and seamlessly in uncertain and dynamic environments motivates our work. We build on five years of experience in this domain, working together with the Boeing Company, to enhance the state of the art in coordination mechanisms that will realize the vision of effective human-robot team operations in a variety of real-world settings.