1. A computer program product for deploying a new virtual appliance on one or more computers configured to each host one or more virtual machines, the new virtual appliance including one or more new virtual machines which each includes one or more new software programs, said computer program product comprising a non-transitory computer readable medium embodying a computer program which includes code directly loadable into a working memory of a data processing system and configured to cause the data processing system to perform steps comprising: determining structure information of the new virtual appliance including verifying an inclusion of the structure information of the new virtual appliance in an appliance repository that comprises structure information of each one of a plurality of known virtual appliances previously deployed on the one or more computers and retrieving the structure information of the new virtual appliance from the appliance repository in response to the inclusion, or discovering of the structure information from an image of the new virtual appliance and saving the structure information of the new virtual appliance into the appliance repository, the structure information of the new virtual appliance including an indication of the one or more new virtual machines and an indication of the one or more new software programs; retrieving configuration information indicative of a current configuration of the one or more computers; retrieving license condition information indicative of license conditions applicable to the one or more computers including creating a first hash table including the license conditions for the virtual appliances each one being directly accessible through an identifier of a corresponding virtual appliance and creating a second hash table including the license conditions for the software programs each one being directly accessible through an identifier of the corresponding software program, wherein the license condition information includes an indication of a first set of license conditions each one for the corresponding virtual appliance and an indication of a second set of license conditions each one for a corresponding software program; determining a deployment scheme of the virtual appliance on the one or more computers, the determination of the deployment scheme being performed by optimizing a cost function based on the license condition information, the configuration information and the structure information; and deploying the new virtual appliance according to the deployment scheme.