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

Titre du sujet
Fournées
Établissement
Collège Georges Pompidou (Cajarc)
Année
2014-2015
Etablissement(s) jumelé(s)
Lycée Raymond Savignac (Villefranche de Rouergue)
Résumé
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.