A COLUMN GENERATION APPROACH TO JOB GROUPING FOR FLEXIBLE MANUFACTURING SYSTEMS

A flexible manufacturing system consists of a number of NC-machines, l inked by automated material handling devices, that perform the various operations required to manufacture parts. Each operation requires dif ferent tools. These tools are stored in a limited capacity tool magazi ne attached to each machine. When it becomes necessary to add or remov e tools from the tool magazine, the machine may have to be shut down f or a setup. In this paper, we study a model which aims at minimizing t he number of setups, We assume that N jobs must be processed on a mach ine. Each job requires a certain set of tools, which have to be presen t in the tool magazine of the machine when the job is executed. The ma gazine has a total capacity of C tools. We say that a group (subset, b atch) of jobs is feasible if, together, these jobs do not require more than C tools. The job grouping problem is to partition the jobs into a minimum number of feasible groups. The problem can be formulated as a set covering problem. We solve the linear relaxation of this formula tion in order to obtain tight lower bounds. Since the number of variab les is potentially huge, we use a column generation approach. The colu mn generation subproblem turns out to be NP-hard; we solve it by enume ration. We also describe some fast and simple heuristics for the job g rouping problem. The result of our computational experiments is that t he lower bound is extremely strong. The quality of the heuristic solut ions is in general very good too. We also investigate a more general m ultiple-machine model in which each tool may occupy several slots in t he tool magazines.