FACULTÉ & RECHERCHE

Cet article étudie la complexité de la planification d’une seule machine avec une ressource externe, qui est louée pour une période ininterrompue. Les travaux qui ont besoin de cette ressource externe sont exécutés uniquement lorsque la ressource externe est disponible. Il y a un coût associé à la planification des travaux et un coût associé à la durée de la période de location de la ressource externe. Nous examinons quatre catégories de problèmes avec une ressource externe: une classe de problèmes où la période de location est budgétisée et le coût de planification doit être minimisé, une classe de problèmes où le coût de planification est budgétisé et la période de location doit être minimisée, une classe de problèmes à deux objectifs où les deux, la période de location et le coût de planification, doivent être minimisés, et une classe de problèmes où une combinaison linéaire du coût de planification et de la période de location est minimisée. Nous fournissons une analyse approfondie de la complexité (preuves de dureté NP et algorithmes (pseudo-)polynomiaux) pour différents membres de ces quatre classes.