Paul ouvre deux places sur la table pour préparer quatre cartes d'activité. Elles ne se partagent pas entre les places : chacune doit recevoir une première avance sur le poste de gauche, puis une seconde sur celui de droite. Nora compare deux ordres qui passent par les mêmes postes et demandent les mêmes quantités de travail. Les fins diffèrent, parce que le second poste ne peut pas commencer une carte que le premier n'a pas encore terminée. Une nouvelle règle interdisant l'attente entre les étapes modifiera encore leur calendrier.
Toutes les cartes et leurs durées sont inventées. Chaque étape occupe entièrement son poste pendant la durée inscrite, sans interruption. Une carte ne commence sa seconde étape qu'après la fin de la première. Les quatre sont disponibles à zéro et suivent le même ordre sur les deux postes. Au départ, une carte peut attendre entre ses deux étapes, sans occuper le premier poste après y avoir terminé. Les deux postes restent ouverts. Aucun temps de fabrication, consigne physique ou capacité d'un jouet réel n'est renseigné.
Les sources situent seulement des catégories de jeux et jouets. Les cartes, durées et files sont créées ici ; aucune méthode de fabrication ou performance des marques n'est reprise.
GRIMM'S : matériel de jeu.
Grapat : jouets.
Londji : jeux et jouets.
Une même carte doit passer deux fois, sans faire travailler deux fois le même poste
A demande trois unités de temps sur le premier poste et huit sur le second. B demande sept puis deux, C quatre puis six, D cinq puis une. Paul commence par l'ordre A, B, C, D. Sur le premier poste, les fins sont trois, dix, quatorze et dix-neuf. Le second prend A de trois à onze, puis B de onze à treize. C n'est prête qu'à quatorze ; le poste attend une unité, puis la traite jusqu'à vingt. D, prête depuis dix-neuf, le prend enfin jusqu'à vingt et un. Les quatre cartes sont terminées à vingt et un.
Nora remplace l'ordre par A, C, B, D sur les deux lignes. Le premier finit A à trois, C à sept, B à quatorze et D à dix-neuf. Le second prend A de trois à onze, C de onze à dix-sept, B de dix-sept à dix-neuf, puis D de dix-neuf à vingt. Les quatre sont terminées une unité plus tôt. C a attendu quatre entre ses étapes, B trois, et D aucune. Ces attentes ne sont pas des heures de poste supplémentaire : le premier travaille déjà sur les cartes suivantes tandis qu'elles attendent leur seconde étape.
Le premier poste demande au total dix-neuf unités, quel que soit l'ordre des cartes. La dernière qu'il termine doit encore recevoir une seconde étape dont la durée est au moins une. Aucune fin commune ne peut donc précéder vingt. La feuille A, C, B, D atteint cette borne. Nora la retient comme optimale pour cette commande, plutôt que simplement meilleure que la première feuille. Le second poste n'a travaillé que dix-sept unités, mais son premier début à trois porte sa fin à vingt ; annoncer dix-sept comme fin aurait retiré le temps où aucune carte n'était prête pour lui.
Paul avait placé dans sa première feuille B avant C parce que B ne demande que deux au second poste. Il revoit le manque concret produit par ce choix. B consomme d'abord sept au premier poste ; pendant ces sept unités, la fin de A occupe encore le second et C n'avance pas encore à gauche. Le second termine B à treize, mais C ne sort à gauche qu'à quatorze. Lorsque C passe avant B, ses quatre unités la rendent prête dès sept, et ses six unités à droite couvrent ensuite la préparation plus longue de B. Nora garde cette articulation remplie plutôt qu'une préférence générale pour la plus petite seconde étape.
Écrire le début réel d’une seconde étape
Pour refaire une feuille, Nora écrit deux fins après chaque carte. La fin du premier poste augmente de la première durée. Le début de la seconde étape est le plus tardif de deux moments : cette nouvelle fin du premier, et la fin laissée par la carte précédente au second. Elle ajoute alors la seconde durée pour obtenir la nouvelle fin à droite. Dans la feuille A, C, B, D, C est prête à sept mais attend la fin onze de A ; B est prête à quatorze mais attend dix-sept ; D est prête à dix-neuf et trouve justement le second libre. Chacun des trois débuts répond à ces deux contraintes.
Paul essaie de commencer C à sept au second poste, en recopiant directement sa fin sur le premier. Cela la ferait terminer à treize, mais elle occuperait le second pendant les quatre dernières unités de A. Les deux cartes ne disposent pas de deux postes de seconde étape. Nora retire le début sept et remet onze, puis refait les fins suivantes à partir de cette correction. Elle refuse aussi de débuter B à onze dans la même feuille : à cet instant, C commence à droite, et B n'est pas encore prête à gauche. Le calendrier doit conserver ensemble l'arrivée de chaque carte et la disponibilité du poste où elle arrive.
La même règle s'applique lorsque Paul avance le premier poste aussi vite que possible. Ajouter volontairement un vide à gauche ne rend aucune carte prête plus tôt ; pour un ordre fixé et une attente intermédiaire permise, cela ne peut donc avancer la fin commune. Nora commence chaque première étape après la précédente et chaque seconde dès que ses deux conditions sont satisfaites. Cette propriété permet de comparer les ordres par leurs feuilles les plus précoces. Elle ne suppose pas que toute consigne future permettra la même attente : une autre branche retirera précisément cette permission et pourra nécessiter un vide avant une première étape.
Le retard du second poste se lit dans les préfixes de l’ordre
Paul veut retrouver vingt sans recopier tous les intervalles de la feuille retenue. Pour chaque place de l'ordre, il additionne les premières durées jusqu'à cette carte, puis retire les secondes durées des seules cartes précédentes. Avec A, C, B, D, il obtient successivement trois ; sept moins huit, soit moins un ; quatorze moins quatorze, soit zéro ; dix-neuf moins seize, soit trois. Le plus grand de ces quatre nombres est trois. En lui ajoutant les dix-sept unités de seconde étape, il retrouve la fin vingt. Il ne retire pas la seconde durée de la carte courante dans le calcul de son propre préfixe.
Pour A, B, C, D, les mêmes nombres sont trois, deux, quatre et trois. Leur maximum vaut quatre ; avec le travail de droite dix-sept, la fin vaut vingt et un. Le maximum quatre apparaît avec C, dont la préparation se termine à quatorze alors que les deux secondes étapes précédentes ne totalisent que dix. Nora repère ainsi le manque qui avait placé un vide de treize à quatorze dans sa feuille. Les deux ordres n'ont changé ni le total de droite ni celui de gauche. Leur différence se trouve dans le maximum de ces écarts de préfixes, où la carte courante attend encore d'entrer au second poste.
Nora vérifie cette formule à partir des deux contraintes de début. Pour une première carte, sa fin à droite est sa première durée plus sa seconde. Pour ajouter la suivante, soit l'ancienne fin à droite la retarde, soit sa propre fin à gauche la retarde ; la plus grande des deux est conservée. En développant ce maximum de proche en proche, chaque préfixe fournit sa fin à gauche suivie de toutes les secondes durées qui restent, y compris celle de sa carte. La fin commune est le maximum de ces sommes. Retirer le même total des secondes durées dans chacune laisse exactement les écarts calculés par Paul.
Paul ne cherche donc pas à minimiser séparément chaque première durée ou chaque seconde. Une première durée courte peut libérer une carte dont la longue seconde étape absorbera la préparation suivante. À l'inverse, une carte longue à gauche et brève à droite peut être avantageusement gardée vers la fin. Ces observations décrivent la feuille A, C, B, D, mais Nora veut une règle de comparaison capable de justifier un déplacement. Elle conserve la formule complète, car un ordre qui semble bon sur ses deux premières cartes peut créer son plus grand manque au troisième préfixe.
Comparer deux cartes adjacentes sans effacer les autres
Nora appelle x le moment où le premier poste devient libre avant deux cartes voisines, et y celui où le second devient libre. Une carte i demande aᵢ puis bᵢ, l'autre j demande aⱼ puis bⱼ. Dans l'ordre i puis j, la fin commune après ces deux cartes vaut le plus grand de y plus bᵢ plus bⱼ, et de x plus les quatre durées moins le plus petit de aⱼ et bᵢ. Dans l'ordre inverse, le premier terme est inchangé ; le second retire maintenant le plus petit de aᵢ et bⱼ. La comparaison porte donc sur deux retraits à une même somme, plutôt que sur deux totaux différents.
L'ordre i puis j n'est pas plus tardif si le plus petit de aᵢ et bⱼ est inférieur ou égal au plus petit de aⱼ et bᵢ. Le retrait de son second terme est alors au moins aussi grand. Après les deux cartes, la fin du premier poste est identique dans les deux ordres, puisqu'il a effectué les mêmes premières durées. La fin du second ne s'est pas élevée. Nora peut donc conserver toutes les cartes suivantes dans leur ordre : en reprenant la règle des deux disponibilités, aucune ne sera forcée de finir plus tard. La comparaison locale s'étend ainsi à la fin de la feuille, avec son préfixe et son suffixe conservés.
Pour B et C, leurs durées sont sept et deux, puis quatre et six. Mettre C avant B compare le plus petit de quatre et deux, soit deux, au plus petit de sept et six, soit six. Deux est inférieur à six ; cet ordre n'est donc pas plus tardif que B avant C dans toute feuille remplissant les mêmes permissions. Nora applique cette comparaison au milieu de A, B, C, D et obtient A, C, B, D. Les disponibilités particulières donnent ici une amélioration de vingt et un à vingt, mais la comparaison ne dépendait pas de choisir une arrivée favorable pour ces deux cartes avant d'effectuer leur échange.
Choisir une petite durée à gauche ou à droite ne signifie pas la mettre toujours devant
Paul cherche la plus petite durée parmi toutes celles des cartes encore à placer. Si cette durée appartient à la première étape de i, elle n'est supérieure ni à une première durée aⱼ ni à une seconde bⱼ. Le plus petit de aᵢ et bⱼ vaut donc aᵢ, et ne dépasse pas le plus petit de aⱼ et bᵢ. La comparaison autorise i avant chacune des autres cartes restantes. Paul peut la déplacer vers la première place encore ouverte par des échanges adjacents qui n'allongent pas la fin. Nora fixe alors cette place et poursuit sur celles qui restent, sans reprendre les cartes déjà placées.
Si la plus petite durée est au contraire la seconde étape bᵢ, la même comparaison autorise chacune des autres cartes j avant i. Paul place donc i dans la dernière place encore ouverte. Il ne la met pas au début sous prétexte qu'elle possède la durée la plus courte de la feuille. Cette différence de côté est la règle qui distingue ses deux choix. Les échanges qui la repoussent ne changent pas la fin du premier poste après chaque paire et n'augmentent pas celle du second. Le suffixe déjà fixé peut être conservé, puis Paul continue avec les cartes non placées au milieu.
Sur les quatre cartes, la plus petite durée est une, seconde étape de D : Paul réserve à D la dernière place. La suivante est deux, seconde étape de B : il lui réserve la dernière place encore libre, juste avant D. Parmi A et C, trois est la première étape de A ; A prend la première place. C remplit celle qui reste. Nora reçoit A, C, B, D avec ce choix des deux bords. Elle vérifie ensuite son calendrier de vingt déjà retenu, plutôt que confondre une réservation de places et l'exécution des deux étapes aux heures nécessaires.
La règle fournit un ordre optimal pour cette commande avec attente permise et même ordre aux deux postes. En partant d'un ordre optimal quelconque, chaque déplacement autorisé par la comparaison peut fixer le premier ou le dernier emplacement retenu sans augmenter sa fin. Refaire ce choix sur les places restantes mène à l'ordre construit par Paul avec une fin toujours optimale. Nora ne prétend pas que l'ordre des deux côtés se justifierait encore si une carte pouvait dépasser une autre au second poste, si une durée dépendait de la carte précédente ou si le transfert exigeait une ressource supplémentaire. Aucun de ces changements n'appartient à la preuve donnée.
La fin de l’ensemble et les fins additionnées peuvent demander deux remises
Une commande séparée préfère la plus petite somme des heures auxquelles les quatre cartes terminent leur seconde étape. L'hôte la confirme avant le choix de Nora. La feuille A, C, B, D finit ses cartes à onze, dix-sept, dix-neuf et vingt, soit soixante-sept ensemble. Nora prépare plutôt A, D, C, B. À gauche, les fins sont trois, huit, douze et dix-neuf ; à droite, les fins sont onze, douze, dix-huit et vingt et un. Leur somme vaut soixante-deux. D termine beaucoup plus tôt dans cette feuille, tandis que la fin commune perd une unité.
Paul énumère les vingt-quatre ordres communs possibles et remplit chacun par la règle des deux disponibilités. Soixante-deux est la plus petite somme, obtenue seulement par A, D, C, B ; vingt reste la plus petite fin commune, obtenue seulement par A, C, B, D. Nora conserve deux feuilles répondant à deux commandes différentes. Elle n'attribue pas à la règle des petits bords une preuve sur les sommes de fins qu'elle n'avait pas donnée. La commande suivante reviendra à la fin de l'ensemble, mais changera cette fois la permission d'attendre entre les étapes plutôt que le critère annoncé.
Interdire l’attente après la première étape change les débuts nécessaires
L'hôte exige maintenant que chaque carte passe immédiatement de la première étape à la seconde. Une attente avant le début de sa première étape reste permise. Les étapes demeurent entières et les deux postes suivent toujours le même ordre. A, C, B, D ne peut donc plus reprendre ses débuts initiaux : C avait fini à gauche à sept et commencé à droite à onze, B avait attendu de quatorze à dix-sept. Paul doit produire un autre calendrier pour le même ordre avant de le comparer aux autres, et non supprimer quatre unités d'attente en avançant une seconde étape dans un poste encore occupé.
Il appelle sᵢ le début à gauche de i, suivie de j. Pour ne pas chevaucher leurs premières étapes, le début sⱼ doit être au moins sᵢ plus aᵢ. Pour ne pas chevaucher les secondes étapes, le début de j à droite, sⱼ plus aⱼ, doit être au moins la fin de i à droite, sᵢ plus aᵢ plus bᵢ. Il faut donc séparer les débuts à gauche d'au moins le plus grand de aᵢ et de aᵢ plus bᵢ moins aⱼ. Ce calcul répond aux deux postes ensemble, tout en imposant le passage immédiat de chaque carte entre ses deux étapes.
Pour A suivie de C, cette séparation vaut le plus grand de trois et de trois plus huit moins quatre, soit sept. Si A commence à zéro, C commence au plus tôt à sept à gauche, finit à onze et passe immédiatement à droite. Pour C suivie de B, la séparation vaut quatre ; B commence à onze à gauche et passe à droite à dix-huit. Pour B suivie de D, elle vaut sept ; D commence à dix-huit à gauche, et passe à droite à vingt-trois. Le même ordre termine désormais à vingt-quatre, avec la seconde étape de D. Les attentes entre étapes ont bien disparu, mais des vides ont été déplacés avant des premières étapes.
Nora remplace maintenant l'ordre par A, B, C, D. Entre A et B, la séparation minimale vaut quatre : A occupe gauche de zéro à trois puis droite de trois à onze ; B occupe gauche de quatre à onze puis droite de onze à treize. C commence à gauche à onze, après la première étape de B, et finit à quinze ; sa seconde va de quinze à vingt et un. D commence à gauche à seize, finit à vingt et un puis passe immédiatement à droite jusqu'à vingt-deux. Les deux vides à gauche, de trois à quatre et de quinze à seize, rendent les passages immédiats possibles.
Paul voudrait combler le premier vide en commençant B à trois. B finirait alors à gauche à dix. Pour passer immédiatement à droite, elle devrait y commencer à dix, pendant la dernière unité de A. La condition de séparation lui demandait quatre, et la tentative lui donne seulement trois. Nora remet le début quatre. Elle refuse également D à quinze : D finirait à gauche à vingt, alors que C y occupe encore le second poste jusqu'à vingt et un. Le début seize garde la fin vingt et un. Les vides sont donc des parties de ce calendrier permis, pas une attente intermédiaire dissimulée sous un autre nom.
Pour un ordre fixé, Nora commence la première carte à zéro puis applique à chaque paire la plus petite séparation autorisée. Retarder un de ces débuts ne peut avancer aucun des suivants ni la fin de la dernière carte. Le calendrier le plus précoce de cet ordre se calcule donc par addition des séparations, puis des deux durées de la dernière carte. Elle applique ce calcul aux vingt-quatre ordres, avec leurs mêmes quatre cartes. Contrairement à la première branche, le coût entre deux cartes utilise maintenant la première durée de la suivante : il dépend du couple orienté qui se rencontre, pas d'une place réservée séparément par une petite durée isolée.
Les six ordres commençant par A donnent, dans l'ordre A B C D, A B D C, A C B D, A C D B, A D B C, A D C B, les fins vingt-deux, vingt-six, vingt-quatre, vingt-six, vingt-huit et vingt-quatre. Les six commençant par B ont pour fins vingt-cinq, vingt-huit, vingt-six, vingt-huit, vingt-neuf et trente. Les six commençant par C donnent vingt-quatre, vingt-sept, vingt-trois, vingt-sept, vingt-trois et vingt-huit ; ceux commençant par D donnent vingt-six, vingt-cinq, vingt-neuf, trente, vingt-cinq et vingt-sept. Dans chacun de ces trois derniers groupes, les lettres restantes sont parcourues dans leur ordre alphabétique. Le plus petit résultat est vingt-deux, obtenu seulement par A, B, C, D.
Nora remet A, B, C, D pour l'interdiction d'attendre entre étapes, avec ses débuts zéro, quatre, onze et seize. Elle laisse A, C, B, D à la commande où l'attente était permise. La comparaison de deux cartes qui soutenait les petits bords avait développé une seconde étape pouvant attendre sa disponibilité ; elle n'avait pas imposé que celle-ci suive immédiatement la première. Retirer cette permission change donc réellement les contraintes du calcul. La règle précédente ne devient pas une preuve sur la nouvelle feuille parce que les durées et les noms des quatre cartes sont restés les mêmes.
Paul conserve enfin les heures des deux postes avec la règle de passage attachée à chacune des feuilles. La fin commune, les fins des cartes et les espaces libres ne sont plus trois façons indifférentes de lire un même nombre. Nora sait quelle commande chaque feuille termine et quelles attentes elle permet. L'activité suivante pourra choisir l'une de ces commandes, mais devra garder ses étapes et ses débuts effectifs lorsqu'elle sera remise aux participants.