As the compression efficiency of HEVC comes at the cost of high complexity, especially in the encoder’s side, improved parallelization techniques that will speedup the encoding process are essential. One of the parallelization granules offered by HEVC is the tile level, whereby a frame is split into a grid like fashion with each resulting rectangular area (tile) being independently encoded. While tile parallelism has attracted research interest, the primary focus was to characterize performance and develop load balancing schemes assuming a one on one tile processor assignment. In this paper we target the problem of adaptively defining tile sizes (upon each frame) based on CTU cost estimation, under the assumption that the number of processors might be less than the number of tiles. It turns out that aside from the tile load balancing aspect, the problem has a processor scheduling sub-component that plays equal role. A fast algorithm is proposed that decides both tile sizing and tile processor assignment in an adaptive per frame fashion. Through experiments with common test sequences, the algorithm is shown to outperform the static tile sizing (one thread per tile) approach, by more than 30% (depending on the evaluation scenario) in terms of running time, without affecting video quality.