Natural human interaction is characterized by interpersonal coordination: interlocutors converge in their speech rates, smoothly switch speaking turns with virtually no delay, provide their interlocutors with verbal and nonverbal backchannel feedback, wait for and react to such feedback, execute physical tasks in tight synchrony, etc. If virtual humans are to achieve such interpersonal coordination they require very flexible behavior plans that are adjustable on-the-fly. In this paper we discuss how such plans are represented, maintained and constructed in our BML realizer Elckerlyc. We argue that behavior scheduling for Virtual Humans can be viewed as a constraint satisfaction problem, and show how Elckerlyc uses this view in its flexible behavior plan representation that allows one to make on-the-fly adjustments to behaviors while keeping the specified constraints between them intact.