problem. This work does not consider whether a task could be finish within its deadline.

Some existing work studied on minimizing cost with deadline constraints in hybrid clouds. Van den Bossche et al. [@BOT1; @BOT2; @BOT3] proposed a set of algorithms to cost-efficiently schedule the deadline-constrained BoT applications on both public cloud providers and private infrastructure while taking into account data constraints, data locality and inaccuracies in task runtime estimates. The Hybrid Cloud Optimized Cost (HCOC) scheduling algorithm[@HCOC1; @HCOC2] tried to optimize the monetary execution costs resulting from the public nodes only while maintaining the execution time fitting deadline. HCOC first made an initial schedule using the Path Clustering Heuristic (PCH) algorithm [@PCH] to schedule the tasks to the private cloud and then rescheduled some tasks to the public cloud if the deadline is missed. The algorithm can achieve cost optimization for workflow scheduling. Genez et al. [@UCC13] presented an integer linear program model. The numbers of each type of VM instances in both private and public clouds are obtained by solving this model to minimize cost without missing its deadline for a workflow. In this work, the authors considered the VM instances with same type being homogeneous, which is 