DAG scheduling is a challenging combinatorial optimization problem of executing a graph of computational tasks so as to minimize certain execution metrics, such as makespan and cost. In this paper, we consider the problem of computing lower bounds for bi-objective DAG scheduling in the cloud. While in the single-objective DAG scheduling the lower bounds are often used to estimate the quality of heuristics, there is little work on the lower bounds in case of two or more objectives. We adapt standard scalarization algorithms based on the LP relaxation to our problem and propose an advanced column generation lower bound. The quality of the algorithms is evaluated on real-world data from WfCommons project. We found that on most DAGs the column generation approach is more than 4x better than the standard LP lower bound, and on certain applications, such as 1000Genome and SRA Search, the state-of-the-art scheduling algorithms are within 5% of the column generation lower bound, meaning that there is little room for improvement.