POLYNOMIAL TIME ALGORITHMS FOR SPECIAL OPEN SHOP PROBLEMS WITH PRECEDENCE CONSTRAINTS AND UNIT PROCESSING TIMES

摘要

Le but de cet article est de proposer des algorithmes polynomiaux pour deux problèmes d'ordonnancement de type open shop à deux machines avec contraintes de précédence et temps opératoires unitaires. Le premier algorithme qui permet d'optimiser la durée totale a une meilleure complexité que le meilleur algorithme connu de la littérature lorsque le nombre de contraintes est proportionnel au nombre de jobs. Le deuxième algorithme, qui est basé sur le premier, permet de résoudre un problème ouvert qui est celui de la minimisation de la durée moyenne d'achèvement des jobs quand les contraintes de précédences forment une anti-arborescence.%In this paper we consider different open shop problems with unit processing times. For the problem with two machines and arbitrary precedence constraints among the jobs, we give a polynomial time algorithm for the minimization of the makespan with a better worst case complexity than a previous algorithm known from the literature if the number of arcs is of linear order. The complexity of the open shop problem with unit processing limes and intree constraints among the jobs was open up to now if the sum of completion times of the jobs has to be minimized. By means of the first result we give a polynomial time algorithm for this problem with two machines.