  We present an approach to task scheduling in heterogeneous multi-robot
systems. In our setting, the tasks to complete require diverse skills. We
assume that each robot is multi-skilled, i.e., each robot offers a subset of
the possible skills. This makes the formation of heterogeneous teams
(\emph{coalitions}) a requirement for task completion. We present two
centralized algorithms to schedule robots across tasks and to form suitable
coalitions, assuming stochastic travel times across tasks. The coalitions are
dynamic, in that the robots form and disband coalitions as the schedule is
executed. The first algorithm we propose guarantees optimality, but its
run-time is acceptable only for small problem instances. The second algorithm
we propose can tackle large problems with short run-times, and is based on a
heuristic approach that typically reaches 1x-2x of the optimal solution cost.
