On the application of insertion techniques for job shop problems with setup times

Abstract

Des heuristiques constructives sont basees souvent sur des regles de priorite. Neanmoins, les publications les plus recentes ont montre que des algorithmes d'insertion qui inserent pas a pas des operations dans les plans partiels deja existants sont plus efficaces. Dans notre publication nous considerons differents problemes de « job shop scheduling » avec des temps de preparation. Pour chaque ordre sont donnees une route technologique et la date de mise a disposition. Les ordres sont partages en groupes. Un temps de preparation s rj independant de la suite est necessaire pour la machine j au cas ou un ordre pour le r-ieme groupe est execute apres un ordre d'un autre groupe. Nous considerons des types differents de la mise a disposition d'un ordre, plus precisement Item- et Batch-disponibilite. Comme fonction de but seront utilises aussi bien des criteres reguliers que non-reguliers. Pour des problemes de ce genre nous utilisons des techniques d'insertion combinees avec la recherche « Beam ». En particulier nous considerons des ordres differents d'insertion des demandes (resp. des operations). Une variante avec des insertions paralleles pour plusieurs operations est consideree egalement. Les algorithmes deduits sont testes pour un grand nombre de problemes et compares avec d'autres algorithmes de priorite.