Nora prépare sur papier plusieurs demandes pour un service entièrement inventé. Chacune possède un instant où elle devient disponible, une quantité de travail et un instant limite de fin. Paul voudrait les ranger par petites durées. Nora doit lui remettre une autre chose : une organisation où toutes les demandes sont achevées dans leur propre fenêtre. Une fin moyenne favorable ne suffit pas à remplir cette commande.
Timex présente des montres.
Hamilton présente des collections de montres.
Fossil présente une catégorie de montres.
Ces pages attestent cette catégorie seulement. Aucun horaire, précision ou procédé n'est transféré. Les demandes, leurs fenêtres et les règles de travail sont créées pour notre feuille.
Notre poste abstrait réalise une unité de travail par unité de temps, sur une seule demande à la fois. Les dates et les travaux sont entiers. Dans la première règle, une interruption est permise à chaque borne entière et le travail acquis reste acquis. Aucun coût de changement n'est ajouté. Toutes les demandes sont obligatoires et connues dans la feuille ; aucune recette, personne réelle, cuisson ou manipulation alimentaire ne reçoit ces permissions. Une demande peut finir exactement à son instant limite, mais ne peut travailler avant sa disponibilité.
Choisir la prochaine fin exigée plutôt que le prochain petit travail
Une première feuille donne A disponible à zéro, avec trois unités de travail et une fin exigée à trois. B devient disponible à un, demande une unité et doit finir à cinq. Nora commence A de zéro à un. À un, A conserve deux unités et B en demande une. La préférence pour le plus petit travail restant prendrait B de un à deux, puis A jusqu'à quatre. B finirait très tôt, mais A dépasserait sa limite trois. Nora retire cette suite de la commande qui doit terminer les deux demandes à temps.
Elle choisit au contraire de continuer A jusqu'à trois, puis B de trois à quatre. Les deux fenêtres sont respectées. Paul compare les temps depuis l'arrivée jusqu'à la fin : trois pour A et trois pour B, soit trois en moyenne. Dans la proposition refusée, A prenait quatre et B une, soit deux et demie en moyenne. Nora conserve cette différence au lieu de prétendre avoir amélioré tous les indicateurs. Elle accepte la moyenne plus grande pour obtenir zéro dépassement. La petite durée de B n'était pas la date la plus proche qu'il fallait protéger à un.
Nora retient donc, pour la règle donnée, la demande disponible dont la fin exigée est la plus proche. Une demande terminée sort de la comparaison ; une demande suspendue y revient avec son travail restant et sa même date limite. Elle ne trie pas une fois pour toutes les lettres au départ. Dans une autre feuille, A arrive à zéro avec quatre unités et une limite cinq, tandis que B arrive à un avec une unité et une limite deux. À zéro, seule A est disponible. À un, la limite deux de B passe devant cinq : Nora suspend A, traite B jusqu'à deux, puis reprend les trois unités de A jusqu'à cinq. La règle choisit ici une interruption, alors qu'elle l'avait refusée dans la première feuille.
Paul proposait de conserver le même ordre A puis B parce que A avait été choisie la première. Il donnerait A jusqu'à quatre puis B jusqu'à cinq, au-delà de deux pour B. Nora remplace cette décision à l'instant de disponibilité de B. Le changement n'est pas une priorité accordée au nom nouveau : il vient de sa limite deux. Si B portait encore cinq et A trois comme sur l'autre feuille, l'arrivée à un ne justifierait pas ce passage. Nora livre donc les dates avec la suite, afin que les deux états ne reçoivent pas une même explication de l'interruption.
Une substitution de deux morceaux justifie le choix local
Paul demande pourquoi cette préférence peut conserver une organisation conforme, lorsqu'il en existe une sous nos premières règles. Nora considère une organisation complète qui respecte toutes les fins, et le premier créneau où elle diffère de sa règle. Sa règle veut y traiter une unité de J, déjà disponible et de date limite la plus proche. L'autre organisation traite une unité de K. Puisque J n'est pas achevée et que cette organisation la termine, une unité de J se trouve plus tard. Nora échange ces deux unités : J prend le créneau présent et K le créneau que J occupait. Les deux morceaux appartiennent aux mêmes demandes, sans modifier leurs travaux totaux.
Elle vérifie les deux fenêtres de l'échange. J est disponible au créneau présent, donc son avance est permise. K était déjà disponible puisque l'autre organisation la travaillait maintenant ; le placer plus tard ne le fait pas précéder sa disponibilité. Le morceau tardif de J finissait avant ou à la limite de J. Cette limite est au plus celle de K, puisque toutes deux attendaient au premier créneau comparé et J avait été choisie pour sa date. K garde donc une fin permise à cette nouvelle place. Nora a corrigé le premier désaccord sans rendre les créneaux précédents différents, et sans sacrifier une fenêtre future.
Si l'autre organisation laissait le poste vide alors que J était disponible, Nora déplace simplement cette unité tardive de J vers le créneau vide. Aucun travail n'est poussé vers une autre date et sa place ancienne devient libre. Elle peut ensuite recommencer au prochain désaccord. La feuille possède un nombre fini de créneaux jusqu'à sa dernière limite : ces corrections finissent par donner une organisation suivant la règle choisie. Nora peut ainsi conserver la possibilité de tout finir à temps, au lieu d'en faire une conséquence d'un essai réussi sur deux lettres. Cette justification utilise précisément les unités interruptibles et le travail conservé ; elle ne justifie pas encore les branches où un bloc doit rester entier.
Un peu de place sur toute la soirée peut cacher une fenêtre trop pleine
Une feuille nouvelle donne P disponible à zéro, avec une unité et une fin limite huit. Q arrive à deux, demande deux unités et doit finir à quatre. R arrive également à deux, demande une unité et doit finir à quatre. Paul additionne les travaux : quatre unités pour huit unités de calendrier. Il annonce une moitié libre et croit la commande facile. Nora cherche où Q et R peuvent réellement travailler. Aucune de leurs trois unités ne peut commencer avant deux ni finir après quatre. Cette fenêtre ne contient que deux créneaux d'une unité. Trois unités obligatoires y sont donc impossibles, même si le reste de la soirée est vide.
Nora remplit l'échec plutôt que de le laisser sous le mot saturation. P peut finir de zéro à un. Le poste attend de un à deux, puis Q occupe deux à trois et trois à quatre. R conserve son unité à quatre, alors que sa limite est atteinte. Donner R de deux à trois ferait seulement déplacer le problème : Q n'aurait plus qu'un créneau avant quatre pour deux unités. La borne trois unités dans une fenêtre de deux refuse les deux choix et toutes leurs découpes. Elle ne dépend pas de la lettre retenue pour départager Q et R, qui possèdent la même limite.
Paul contrôlait aussi toutes les limites depuis zéro. Avant quatre, les travaux de Q et R totalisent trois, inférieur à quatre ; avant huit, les travaux totaux sont quatre, inférieur à huit. Ces deux contrôles ne repèrent pas le manque. Ils ont compté zéro à deux comme temps disponible pour Q et R, alors que leurs arrivées l'interdisent. Nora ajoute la borne de départ deux à son certificat. Elle ne déclare pas que les quatre unités initiales étaient toutes inutilisables : P peut les employer. Elle dit quelles demandes enferment leur travail entier dans le même petit intervalle, et quelle capacité ce seul intervalle leur offre.
Pour vérifier une fenêtre de a à b, Nora additionne les travaux des demandes dont la disponibilité est au moins a et la limite au plus b. Leur travail entier doit tenir entre ces deux bornes. Une demande disponible avant a ou autorisée à finir après b n'est pas automatiquement ajoutée en entier à cette somme : une partie peut être faite hors de la fenêtre. P, dont la limite est huit, ne grossit donc pas le trois enfermé entre deux et quatre. Paul voulait additionner P parce que son nom figure dans la feuille entière ; Nora conserve le sous-ensemble forcé, celui qui prouve le manque sans fabriquer un besoin local de quatre.
Avancer une disponibilité et reculer une limite donnent deux remises différentes
L'hôte accepte une modification dans la feuille refusée : R sera disponible à un au lieu de deux, avec la même limite quatre. Nora prépare P de zéro à un, R de un à deux, puis Q de deux à quatre. Le travail total est inchangé et aucune fin limite ne recule. La fenêtre deux à quatre ne doit plus contenir R entière, puisqu'elle peut désormais être réalisée avant deux. Nora ne remet pas cette organisation à quelqu'un qui conserve l'arrivée de R à deux. Sa ligne de un à deux est précisément le droit nouveau qu'il faudrait retirer dans cet autre état.
Dans une seconde réparation, l'arrivée de R reste deux, mais sa limite passe à cinq. Nora réalise P de zéro à un, Q de deux à quatre puis R de quatre à cinq. Le trou de un à deux demeure. Le troisième créneau utile a été obtenu après quatre, au lieu d'être obtenu avant deux. L'hôte choisit cette version lorsqu'il ne peut pas rendre R disponible plus tôt et accepte réellement sa fin plus tardive. Nora remet alors la limite cinq, pas la limite quatre avec une note disant que le poste avait pourtant de la place ailleurs. Les deux réparations relâchent des côtés différents de la fenêtre obligatoire.
Paul souhaite connaître le plus petit report nécessaire s'il garde toutes les arrivées et autorise à augmenter les deux limites communes de Q et R d'un même entier. Sans report, la demande locale reste trois pour deux, donc elle échoue. Avec un report d'une unité, les deux limites valent cinq et les trois créneaux de deux à cinq suffisent : Q occupe les deux premiers et R le troisième. Un report entier nul est impossible, un report entier un est atteint. Nora inscrit donc un comme report minimal dans cette demande précise. Elle ne confond pas ce minimum avec le retard déjà constaté dans une suite quelconque ; la borne excluait toute suite à report nul et la nouvelle suite atteint le report proposé.
Une absence du poste se compte dans la fenêtre qu'elle retire
Une nouvelle feuille conserve P d'une unité disponible à zéro et limité à huit. Q et R arrivent à deux, avec deux et une unités, mais leurs limites sont maintenant cinq. Sans fermeture du poste, Q de deux à quatre et R de quatre à cinq conviennent. L'hôte donne ensuite une fermeture de trois à quatre : aucun travail n'y est permis. Paul compte encore les trois unités de calendrier entre deux et cinq. Nora les sépare : deux à trois et quatre à cinq sont utilisables, trois à quatre ne l'est pas. Les deux demandes y exigent trois unités pour seulement deux unités de service. Leur accord est refusé malgré les sept créneaux ouverts avant huit dans la journée entière.
Déplacer la fermeture de trois à quatre vers quatre à cinq ne répare pas cette fenêtre. Paul avait cru que Q serait plus commode à terminer sans interruption ; les deux demandes ont toujours trois unités à loger dans les deux seules unités libres entre deux et cinq. Nora refuse les deux positions pour la même capacité locale, sans leur attribuer le même récit de travail. Elle accepte en revanche une fermeture de cinq à six. P passe de zéro à un, Q de deux à quatre et R de quatre à cinq, puis le poste ferme après leurs fins. La durée de fermeture reste une unité ; sa sortie de la fenêtre obligée est le changement décisif.
L'hôte choisit de garder trois à quatre fermé, mais ouvre exceptionnellement un second poste pendant cette seule unité. Nora donne Q de deux à trois sur le premier, puis sa seconde unité de trois à quatre sur le second ; R utilise le premier de quatre à cinq. Aucune demande ne travaille simultanément sur les deux postes. Le créneau manquant a été rétabli au bon endroit et les deux fins cinq sont respectées. Ouvrir ce second poste de six à sept n'aurait pas aidé Q ni R, déjà exigées avant cinq. Nora inscrit donc la plage exacte du poste supplémentaire au lieu d'annoncer seulement une unité d'aide, dont la position resterait indécidable.
Le coût d'un changement retire une hypothèse de la justification
Reprenons A de quatre unités, disponible à zéro et limitée à cinq, et B d'une unité, disponible à un et limitée à deux. Les cinq unités de travail tenaient exactement dans zéro à cinq lorsque les changements ne coûtaient rien. Nous donnons maintenant une demi-unité de poste occupée sans travail à chaque passage d'une demande à l'autre. Cette valeur est créée, sans geste réel associé. Paul conserve la suite A, B, A et lui ajoute ses transitions : A de zéro à un, changement jusqu'à un et demi, B jusqu'à deux et demi. B manque déjà sa limite deux. L'ancienne justification ne peut ignorer le demi-créneau lorsqu'elle échange deux morceaux.
Nora cherche une impossibilité qui ne dépende pas seulement de cette mauvaise suite. Les deux demandes doivent chacune travailler, et leurs cinq unités doivent toutes finir avant ou à cinq puisque leurs limites sont deux et cinq. Un seul poste change nécessairement de demande au moins une fois, donc il lui faut au moins une demi-unité supplémentaire pendant cet horizon. Cinq et une demie ne tiennent pas dans cinq. Même une organisation avec moins de retours que A, B, A ne peut remplir les deux limites. Nora refuse cette nouvelle commande sous la vitesse et le coût donnés ; elle ne propose pas de réparer gratuitement l'interruption qui avait justement permis la première commande.
Nous donnons une autre branche où le changement redevient gratuit, mais où chaque travail commencé doit être terminé d'un seul tenant. A d'abord finit à quatre et B ensuite à cinq, trop tard pour deux. B d'abord ne commence qu'à un, finit à deux, puis les quatre unités de A conduisent à six, trop tard pour cinq. Ces deux ordres couvrent toutes les possibilités de blocs entiers pour ces deux demandes. Attendre volontairement avant A ne peut que retarder le premier ordre ; attendre avant B ne peut que retarder le second. Nora garde donc l'interruption avec progrès conservé comme permission nécessaire de cette feuille, et retire la promesse que la préférence de date suffirait sous n'importe quel régime de blocs.
Laisser un poste vide peut devenir nécessaire quand les blocs sont entiers
Une petite feuille non interruptible donne D disponible à zéro, avec deux unités et une limite cinq. E arrive à un, demande une unité et doit finir à deux. Paul veut que le poste commence immédiatement D, seule présente à zéro. D occupe zéro à deux et E ne peut commencer qu'à deux, pour finir à trois. Nora refuse cette organisation. Elle choisit de laisser zéro à un vide, traite E de un à deux, puis D de deux à quatre. Toutes les limites passent, même si du travail disponible aurait pu remplir le premier créneau. La place gardée pour E n'était pas un travail effectué avant son arrivée.
Ce trou volontaire ne contredit pas la substitution justifiée dans le modèle interruptible. Dans ce modèle, D aurait pu avancer une unité de zéro à un, laisser E passer puis reprendre. La nouvelle règle interdit précisément ce partage. Nora conserve donc une organisation où l'inaction présente réserve une possibilité future ; elle ne lui attribue pas la règle de remplir chaque créneau disponible. La disponibilité de D et la limite proche de E forment ensemble la décision de laisser le poste vide. Avancer l'arrivée de E à zéro donnerait une autre réparation possible, mais la feuille retenue garde un et son trou de calendrier.
Deux postes retirent encore une condition de la preuve
Une dernière feuille donne deux postes ouverts ensemble. A demande une unité avant un, B deux avant trois et C trois avant trois ; les trois sont disponibles à zéro et peuvent être interrompues. Une même demande ne peut cependant pas occuper les deux postes à la fois. Paul prend les deux premières limites, avec B avant C pour leur égalité : A et B de zéro à un, puis B et C de un à deux, puis C jusqu'à trois. A et B passent, mais C n'a reçu que deux de ses trois unités. La somme des six unités de travail vaut pourtant exactement les six unités de poste disponibles. La manière de les répartir importe encore.
Nora prépare C sur un poste pendant les trois unités, et A puis B sur l'autre, A de zéro à un puis B de un à trois. Les trois demandes finissent à temps. Elle retient C plutôt que B à zéro parmi les deux dates égales, parce que C a besoin de toute sa fenêtre sur un seul poste à la fois. Paul ne peut pas donner deux unités simultanées à C de deux à trois pour corriger sa vieille suite : cette possibilité est expressément interdite. Nora conserve l'organisation remplie et retire l'extension automatique de sa préférence du poste unique vers deux postes. Son échange antérieur avait déplacé deux morceaux d'une seule ligne ; il n'avait pas garanti tous les choix de demandes sur deux lignes parallèles.
La feuille principale remise à l'hôte reste celle d'un poste interruptible sans coût de changement, avec ses disponibilités et ses fins exigées. Les certificats de fenêtres pleines expliquent les refus et les réparations locales. Les branches avec fermeture, blocs entiers, coût ou deuxième poste gardent leurs permissions propres. Nora ne transmet aucun horaire de service réel : elle remet les travaux créés, les créneaux choisis et les changements effectivement acceptés, sans faire d'une moyenne courte une preuve que toutes les demandes sont terminées à temps.