Reference : A column generation approach to job grouping for flexible manufacturing systems
Scientific journals : Article
Business & economic sciences : Production, distribution & supply chain management
Business & economic sciences : Quantitative methods in economics & management
Engineering, computing & technology : Computer science
A column generation approach to job grouping for flexible manufacturing systems
Crama, Yves mailto [Université de Liège > HEC Liège : UER > Recherche opérationnelle et gestion de la production >]
Oerlemans, Alwin G. []
European Journal of Operational Research
Elsevier Science
Yes (verified by ORBi)
The Netherlands
[en] Flexible manufacturing systems ; Manufacturing industries ; Heuristics ; Integer programming
[en] A flexible manufacturing system consists of a number of NC-machines, linked by automated material handling devices, that perform the various operations required to manufacture parts. Each operation requires different tools. These tools are stored in a limited capacity tool magazine attached to each machine. When it becomes necessary to add or remove tools from the tool magazine, the machine may have to be shut down for a setup. In this paper, we study a model which aims at minimizing the number of setups. We assume that N jobs must be processed on a machine. Each job requires a certain set of tools, which have to be present in the tool magazine of the machine when the job is executed. The magazine has a total capacity of C tools. We say that a group (subset, batch) 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 formulation in order to obtain tight lower bounds. Since the number of variables is potentially huge, we use a column generation approach. The column generation subproblem turns out to be NP-hard; we solve it by enumeration. We also describe some fast and simple heuristics for the job grouping problem. The result of our computational experiments is that the lower bound is extremely strong. The quality of the heuristic solutions is in general very good too. We also investigate a more general multiple-machine model in which each tool may occupy several slots in the tool magazines.

File(s) associated to this reference

Fulltext file(s):

Restricted access
Colmun generation job grouping EJOR 1994.pdfPublisher postprint1.86 MBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.