On the complexity of multi-criteria scheduling problems for workflow applications. 

Anne Benoit (LIP, Lyon)

In this talk I will give an overview of recent results concerning the
mapping and scheduling of workflow applications.
First, I will introduce the application model, and in
particular pipelined linear chain applications: distinct data sets can
be processed in parallel for different application stages.
Second, I will describe several common platform models,
and in particular the one-port and multi-port models,
with or without communication/computation overlap.
The scheduling problem can then be introduced: we need to map the
application onto the target platform, in order to optimize some
criteria. For such workflow applications, common criteria are the
throughput (number of data sets that can be processed per time unit),
the latency (time needed for a data set to be processed entirely), and
also the reliability (if the platform is subject to failures).
Depending on the communication model, the definition of these criteria
may differ, in particular the latency. Finally, I will summarize
recent complexity results for these scheduling problems, and
illustrate how the complexity depends on the communication model.