Given the variety of resources available in public clouds and locally (hybrid clouds), it can be very difficult to determine the best number and type of resources to allocate (and where) for a given activity. In order to solve this problem we first define the requested computation in terms of an Integer Linear Programming (ILP) problem and then use an efficient ILP solver to make a provisioning decision in a few milliseconds. Our approach is based on the two most important metrics for the user: cost and job execution time. Thus, based on the user’s preferences we can favor solutions that optimize speed or cost or a certain combination of both (e.g. cheapest solution that meets a certain deadline). We evaluate our approach with two classes of cloud applications: MapReduce applications, and Monte Carlo simulations. A significant advantage in our approach is that our solution has been proved optimal by the ILP solver; the set of the scheduling decisions based on our model are plotted on a time vs. cost graph that forms a Pareto efficient frontier. This way,we can avoid the pitfalls of a naïve strategy that can lead to a great increase in cost (91%) or job running time (21%) compared to optimal.