In enterprise application environments, hardware resources show averagely low utilization rates due to a provisioning practice that is based on peak demands. Therefore, the consolidation of orthogonal workloads can improve energy efficiency and reduce total cost of ownership. In this paper, we address existing workload consolidation potential by solving a bin packing problem, where the number of servers is to be minimized. Since dynamic workloads, gathered from historical traces, and priorities of running services are considered, we formulate the Dynamic Priority-based Workload Consolidation Problem (DPWCP) and develop solution algorithms using heuristics and metaheuristics. Relevance is pointed out by an analysis of service resource demands and server capacities across four studied cases from productively operating enterprise application service providers. After a classification of related work, seven algorithms were developed and evaluated regarding their exploited optimization potential and computing time. Best results were achieved by a best-fit approach that uses a genetic algorithm to optimize its input sequence (GA_BF). When applying the GA_BF onto the four studied cases, average utilization rates could be increased from 23 to 63 percent within an average computing time of 22.5 seconds. Therefore, the overall server capacity was reduced significantly by up to 83%.