I have trouble with the following modeling exercise in Combinatorial Optimisation:
You want to schedule $n$ flights with as few planes as possible. For each flight $i$ the travel time $t_i$ and the start time $d_i$ are given. Let further be $\delta(i,j)$ the time for all flights $i,j$ be the time required to prepare a plane for the flight $j$ after it is finished with flight $i$.
Find a flight schedule that ensures all flights are done with as few planes as possible.
We are currently learnig about network flows in the lecture, so I suppose we should use this here.
My current attempt would be as follows. Start with a directed graph $G(V,E)$ with $\lvert V(G) \rvert = n$, where each edge $(i,j)$ connects two nodes $i$ and $j$ if the corresponding flights are viable to be performed after another, i.e. $d_i + \delta_{ij} + t_i \le d_j$. To use a network flow algorithm it would now be natural to define a capacity fucntion on this graph, but I do not see how this could help to solve the problem.
Could you help me?
A flight schedule corresponds to a path cover in your directed (acyclic!) graph. Finding a schedule that uses the minimum number of planes then corresponds to the so-called minimum path cover problem. This can be solved by reduction to the maximum matching problem in bipartite graphs, as sketched here. If you want, you can unpack this and write the maximum matching problem as a network flow problem.