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

¹ Institute of Engineering Cybernetics of the Byelorussian Academy of Sciences, Surganov St. 6, 220012 Minsk, Belarus
² University of Southampton, Highfield, SO17 IBJ, United Kingdom
³ Otto-von-Guericke-Universität Magdeburg, PSF 4120, 39016 Magdeburg, Germany

Received: June 1996

Abstract

Constructive heuristics for shop scheduling problems are often based on priority (or dispatching) rules. However, recent work has demonstrated that insertion algorithms that step by step insert operations or jobs into partial schedules usually clearly outperform priority rules. In this paper, we consider various job shop scheduling problems with setup times. For each job a specific technological route and a release date are given. Moreover, the jobs are partitioned into groups. A sequence independent setup time S_rj is required on machine j when a job of the r-th group is processed after a job of another group. We consider different types of job availability, namely item and batch availability. As objective function we use both regular and nonregular criteria. For such problems we apply insertion techniques combined with beam search. Especially we consider different insertion orders of the operations or jobs. A refined variant of the insertion algorithm is presented, where several operations are inserted in parallel. The proposed variants have been tested on a large collection of test problems and compared with other constructive algorithms based on priority rules.

Résumé

Des heuristiques constructives sont basées souvent sur des règles de priorité. Néanmoins, les publications les plus récentes ont montré que des algorithmes d'insertion qui insèrent pas à pas des opérations dans les plans partiels déjà existants sont plus efficaces. Dans notre publication nous considérons différents problèmes de “job shop scheduling"avec des temps de préparation. Pour chaque ordre sont données une route technologique et la date de mise à disposition. Les ordres sont partagés en groupes. Un temps de préparation S_rj indépendant de la suite est nécessaire pour la machine j au cas où un ordre pour le r-ième groupe est exécuté après un ordre d'un autre groupe. Nous considérons des types différents de la mise à disposition d'un ordre, plus précisément Item- et Batch-disponibilité. Comme fonction de but seront utilisés aussi bien des critères réguliers que non-réguliers. Pour des problèmes de ce genre nous utilisons des techniques d'insertion combinées avec la recherche “Beam”. En particulier nous considérons des ordres différents d'insertion des demandes (resp. des opérations). Une variante avec des insertions parallèles pour plusieurs opérations est considérée également. Les algorithmes déduits sont testés pour un grand nombre de problèmes et comparés avec d'autre algorithmes de priorité.