Planification des travaux avec un problème de goulot d'étranglement

Étant donné travaux , chaque travail nécessite temps pour se terminer. $n$ $J_1,J_2,...,J_n$ $T_i > 0, T_i \in N$

Chaque travail doit être prétraité et post-traité par une seule machine M qui ne peut gérer qu'un seul travail à la fois et les deux phases nécessitent 1 unité de temps. Après avoir été prétraité, le travail est envoyé à une machine avec une puissance illimitée (qui peut gérer en parallèle un nombre illimité de travaux) et il sera prêt dans le temps , puis il doit être envoyé ( immédiatement ) à nouveau à la machine M pour post-traitement. $J_i$ $T_i$

entrez la description de l'image ici

Le problème de décision associé est:

Saisie: les temps de traitement de jobs, un entier Question: pouvons-nous traiter tous les jobs dans le temps utilisant le modèle de "goulot d'étranglement" ci-dessus? $T_i >0, T_i \in \mathbb{N}$ $N$ $K\geq 2N$
$\leq K$

Ce problème a-t-il un nom?
Quelle est sa complexité? (est-il dans ou est-il -complet?) $\sf{P}$ $\sf{NP}$

MISE À JOUR 29 mars:
Comme l'a correctement noté M.Cafaro dans sa réponse, le problème est similaire au problème de temps de fin minimal sans contrainte (UMFT) (voir le chapitre 17 du Manuel des algorithmes de planification ) qui est -hard (prouvé dans W. Kern et W. Nawijn, "Scheduling multi-operation jobs with time lags on a single machine", Université de Twente, 1993). Comme je peux le voir, il y a quelques différences car dans mon modèle: $\sf{NP}$

le temps de pré / post-traitement est constant (1 unité de temps)
dès que le travail est terminé, il doit être immédiatement post-traité (le modèle UMFT permet des retards)

Je n'ai pas trouvé la preuve Kern & Nawijn en ligne, donc je ne sais toujours pas si les restrictions ci-dessus changent la difficulté du problème.

Enfin, vous pouvez penser l'ensemble du processus comme un robot de cuisson unique avec un grand four; le robot peut préparer différents types d'aliments un par un (tous nécessitent le même temps de préparation), les mettre au four, et dès qu'ils sont cuits il doit les retirer du four et ajouter des ingrédients froids ... le " problème du robot cuisinier " :-)

complexity-theory reference-request scheduling Vor
la source

Agréable. J'ai le sentiment que le goulot d'étranglement devrait simplifier les choses.

Raphael

La contrainte est toujours vérifiée, car les coûts de pré et post-traitement sont tous deux de 1 unité de temps et vous avez jobs. Êtes-vous sûr que la contrainte est correcte?

k \geq 2 n

$k \geq 2 n$

n

$n$

Massimo Cafaro

Désolé, je ne savais pas ce que je voulais dire dans le commentaire précédent. Est-ce que est explicitement donné en entrée comme une "échéance" ou demandez-vous un algorithme pour minimiser ?

k

$k$

k

$k$

Massimo Cafaro

@MassimoCafaro: est donné en entrée (pour faire du problème d'optimisation un problème de décision). Comme vous l'avez remarqué, j'ai écrit parce que si la réponse est trivialement NON. Mais c'est peut-être déroutant et je devrais le supprimer.

k

$k$

k \geq 2 n

$k \geq 2n$

k < 2 n

$k < 2n$

Vor

Votre question est avérée NP-complète dans "Minimiser la durée de vie dans un atelier à deux machines avec des retards et des opérations unitaires-temps est NP-difficile" de W. Yu, H. Hoogeveen et JK Lenstra (2004), qui disent également que Kern et Nawijn ne l'ont pas résolu. Je cite: "Le statut de complexité du cas spécial avec des tâches de temps de traitement d'unité a été ouvert pour des retards minimaux et exacts. Le statut de complexité de celui avec des retards minimaux est posé comme une question ouverte par Kern et Nawijn (1991)."

Peter Shor

Réponses:

La question est éprouvée NP-hard dans «Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard» de W. Yu, H. Hoogeveen et JK Lenstra (2004). Ceci est prouvé dans la section 9 du document:

Théorème 24. Le problème de la minimisation de la durée de fabrication sur une seule machine avec deux opérations de temps unitaire par tâche avec des retards intermédiaires arbitraires est fortement NP-difficile.

Le modèle exact étudié ici est que le travail consiste en deux opérations qui prennent un temps unitaire séparé par un certain temps de retard . Le problème est fortement NP-complet à la fois lorsque la valeur exacte du retard est spécifiée pour chaque travail, et lorsqu'un certain délai minimum est spécifié pour chaque travail. $i$ $T_i$ $T_i$

Peter Shor
la source

Cela ressemble au soi-disant modèle de planification maître-esclave introduit par Sahni . En particulier, votre problème relève des systèmes maître-esclave à maître unique. Vous pouvez distinguer plusieurs cas:

1) Si vous n'ajoutez aucune contrainte supplémentaire à l'ordre d'exécution des travaux (comme dans votre cas), le problème est appelé problème de temps de fin minimum sans contrainte (UMFT) et il a été démontré qu'il est NP-difficile;

2) Mêmes ordres de prétraitement et de post-traitement: il est possible de concevoir un algorithme pour construire un ordre préservant le calendrier de temps de fin minimum (OPMFT); $O(n \log n)$

Par conséquent, dans le cas 1, votre problème est dur, alors qu'il est dans dans le cas 2. $NP$ $P$

D'autres problèmes connexes sont:

3) Post-traitement d'ordre inverse: Pour toute permutation de prétraitement donnée, , il est possible de construire un programme d'ordre inverse, appelé programme d'ordre inverse canonique (CROS). Étant donné une permutation de prétraitement , le CROS correspondant est unique. Il est facile d’établir que chaque horaire d’ordre inverse de l’heure de fin minimale (ROMFT) est un CROS. $σ$ $σ$

4) contrainte de non-attente en cours:

a) [MFTNW] Minimiser le temps de fin soumis à la contrainte no-wait-in-process; b) [OP-MFTNW] Ceci est la version préservant l'ordre de MFTNW. Autrement dit, minimiser le temps de finition soumis aux contraintes de non-attente en cours et de conservation des commandes; c) [RO-MFTNW] Minimiser le temps de fin soumis aux contraintes de non-attente en cours et d'ordre inverse.

Les problèmes et sont NP-difficiles, tandis que admet une solution temporelle polynomiale. $a$ $b$ $c$

Détails supplémentaires dans Handbook of Scheduling , chapitre 17.

Massimo Cafaro
la source

Merci, c'est pareil (je n'ai pas le livre mais j'ai trouvé ce papier ). Je vais le lire attentivement plus tard, juste une question après avoir lu son introduction, il semble qu'il utilise esclaves (après prétraitement), mais dans mon modèle il y a un nombre illimité d'esclaves; est-ce correct?. Je vais lire la preuve de la dureté NP de l'UMFT et voir si elle utilise l'hypothèse que le nombre d'esclaves est limité.

n

$n$

Vor

Sahni a montré que vous pouvez toujours utiliser exactement esclaves: "Les processeurs disponibles sont divisés en deux catégories: maître et esclave. Si indique le nombre de tâches, alors aucun programme ne peut utiliser plus de esclaves. Par conséquent, nous pouvons supposer qu'il sont exactement esclaves. " Votre problème se traduit donc facilement par ce paramètre: vous jetez simplement et n'utilisez pas les esclaves supplémentaires disponibles dans la machine avec un nombre illimité d'esclaves.

n

$n$

n

$n$

n

$n$

n

$n$

Massimo Cafaro

Il me semble que la preuve de dureté NP de Sahni utilise de manière critique le fait que les temps de pré-traitement et de post-traitement peuvent être arbitraires. Le problème du PO a tous ces temps égaux à 1. La preuve fonctionne-t-elle dans ce cas?

Peter Shor

Vor, le document auquel vous vous référez n'est qu'un extrait avec de nombreuses parties manquantes du chapitre 17 du livre. Cependant, la partie manquante vous empêchera de bien comprendre (notation manquante, etc.).

Massimo Cafaro

Peter, je ne suis pas sûr et je dois vérifier la preuve; si elle nécessite juste un temps de pré-post-traitement> 0, elle devrait inclure le problème de l'OP lors de l'examen du problème de temps de fin minimum sans contrainte. Par le même raisonnement, cela devrait conduire à la place à l' algorithme de temps polynomial pour l'ordre préservant le problème du temps de fin minimum.

O (n \log n)

$O(n \log n)$

Massimo Cafaro