In an embodiment for deploying a new virtual appliance (225) on a data processing center (100) structure information of the new virtual appliance is determined (509-521). The structure information of the new virtual appliance includes an indication of the new virtual machines and an indication of the new software programs of each new virtual machine. Configuration information indicative of a current configuration of the data processing center is retrieved (527). License condition information indicative of license conditions applicable to the data processing center is also retrieved (530-533). A deployment scheme of the virtual appliance on the data processing center is then determined (539,548). The determination of the deployment scheme is performed by optimizing a cost function based on the license condition information, the configuration information and the structure information, and the new virtual appliance may be deployed (551) according to the deployment scheme.