Genetic Algorithm for the Permutation Flow-shop Scheduling Problem with Linear Models of Operations
Résumé
The paper deals with a permutation flow-shop problem where processing times of jobs on some machines are linear, decreasing functions with respect to the amount of continuously-divisible, non renewable, locally and totally constrained resources (e.g. energy, catalyzer, raw materials). The purpose is to find a processing order of jobs (the same on each machine) and a resource allocation that minimize the length of the time required to complete all jobs, i.e. makespan. Since the problem is strongly NP-hard, some heuristic algorithms of a genetic type were applied to solve it. These algorithms strongly employees some substantial problem properties which were proved. The results of some computational experiment are also included. || Le papier s'intéresse à un problème de "flow-shop" de permutation où les temps d'exécution des opération sur certaines machines sont des fonctions linéaires décroissantes de la quantité de ressources infiniment divisibles et consommables, quantité limitée