Fournées - Collège Georges Pompidou (Cajarc) Lycée Raymond Savignac (Villefranche de Rouergue)

On dispose d’un four et d’un certain nombre n d’objets à cuire dans ce four. Numérotons les objets de 1 à n. L’objet numéro j doit être cuit pendant une durée comprise entre deux nombres dj et Dj, avec dj ≤ Dj. Ainsi, si un objet j est cuit pendant une fournée i, alors la durée fi de la fournée i doit être telle que dj ≤fi≤Dj. De plus, chaque objet j a une certaine taille tj, et le four a une certaine capacité k. La somme des tj des objets d’une fournée doit être inférieure ou égale à k. L’objectif est de minimiser la somme des fi de toutes les fournées.