Many applications adopt multithreading to increase the concurrency or computational efficiency. In this scenario, the active threads are often much more than the cores of a server, and are scheduled with the operating system. However, we observe that the current load balancing mechanism based on scheduling domains leads to poor performance on asymmetric NUMA machines. Our investigation shows that the poor performance is due to the unnecessary “far” scheduling with high cost, because the current algorithm of building scheduling domains neglects the physical relevance of NUMA nodes in a machine. We therefore propose a physical relevance-based algorithm to construct scheduling domains on asymmetric NUMA machines to reduce the scheduling cost. Experimental results show that the proposed scheduling domains improve the real-world applications by 14.94% on average (up to 22.33%).