  Premier cloud service providers (CSPs) offer two types of purchase options,
namely on-demand and spot instances, with time-varying features in availability
and price. Users like startups have to operate on a limited budget and
similarly others hope to reduce their costs. While interacting with a CSP,
central to their concerns is the process of cost-effectively utilizing
different purchase options possibly in addition to self-owned instances. A job
in data-intensive applications is typically represented by a directed acyclic
graph which can further be transformed into a chain of tasks. The key to
achieving cost efficiency is determining the allocation of a specific deadline
to each task, as well as the allocation of different types of instances to the
task. In this paper, we propose a framework that determines the optimal
allocation of deadlines to tasks. The framework also features an optimal policy
to determine the allocation of spot and on-demand instances in a predefined
time window, and a near-optimal policy for allocating self-owned instances. The
policies are designed to be parametric to support the usage of online learning
to infer the optimal values against the dynamics of cloud markets. Finally,
several intuitive heuristics are used as baselines to validate the cost
improvement brought by the proposed solutions. We show that the cost
improvement over the state-of-the-art is up to 24.87% when spot and on-demand
instances are considered and up to 59.05% when self-owned instances are
considered.
