Groupe d’études et de recherche en analyse des décisions


Solving Practical Instances of the Generalized Flow Shop


We propose a method for producing a feasible schedule for an assembly line of the Generalized Flow Shop type, i.e., jobs must be processed on a set of machines for which there are precedence constraints. These jobs are not necessarily processed by every machine in the set. This particular study is based on experience with an assembly line on which products for telecommunication networks are manufactured. Two majors problems have been considered in the definition of the objective function: the backlog of jobs at some machines and the under-utilization of other machines. The objective is to minimize the weighted sum of the waiting times of the jobs. The weights associated with the jobs correspond to their production priorities, as set by the shop manager. We model the shop using dynamic programming and we heuristically solve the scheduling problem by partially searching the state space. This approach could be used to solve practical instances of the problem.

, 14 pages