Job shop scheduling using Lagrangean relaxation

ABSTRACT

This paper presents an optimization methodology based on lagrangean relaxation to solve the problem of scheduling jobs with due date. Each job consists of a distinct number of operations to be processed in a specified order. We obtain an efficient near—optimal algorithm with guaranteed bounds for the non—preemptive job shop scheduling problem. The method is investigated for scheduling jobs on possibly different sets of identical parallel machines for different operations of a job. By relaxing the coupling capacity constraints with nonnegative Lagrange multipliers and forming the langrangean, we decompose the problem according to jobs, which may be solved independently. The multipliers are adjusted at each step by a subgradient procedure. A list—scheduling heuristic then derives a feasible schedule from this solution.

RÉSUMÉ

Ce papier présente une méthode d'optimisation basée sur la relaxation lagrangienne pour résoudre le problème d'ordonnancement d'atelier avec date de livraison. Chaque job consiste en un nombre donné d'opérations à effectuer dans un ordre fixe. Nous obtenons un algorithme efficace presque optimal avec des bornes garanties pour le problème d'atelier non-préemptif. La méthode est essayée sur les problèmes avec des machines identiques en parallèles susceptibles d'effectuer différentes opérations d'un job. En relaxant les contraintes de capacité avec des multiplieurs de Lagrange positif et en utilisant le lagrangien, nous décomposons le problème par jobs, chaque sous-problème pouvant être résolu indépendamment. Les multiplicateurs sont calculés à chaque étape par une méthode de sous-gradient. Ensuite, une heuristique permet d'obtenir un ordonnancement à partir de l'optimum du lagrangien.

KEY WORDS:

• job shop scheduling
• lagrangean relaxation

MOTS-CLÉS:

• ordonnancement d'ateliers
• relaxation lagrangienne