**Balancing Machining Lines: a Two-phase Heuristic**

**Mohamed ESSAFI**

Ecole Nationale Supérieure des Mines de Saint-Etienne, Centre for Industrial Engineering and Computer Science

158 Cours Fauriel, 42023, Saint-Etienne, France

**Xavier DELORME**

Ecole Nationale Supérieure des Mines de Saint-Etienne, Centre for Industrial Engineering and Computer Science

158 Cours Fauriel, 42023, Saint-Etienne, France

**Alexandre DOLGUI**

Ecole Nationale Supérieure des Mines de Saint-Etienne, Centre for Industrial Engineering and Computer Science

158 Cours Fauriel, 42023, Saint-Etienne, France

**Abstract**: This paper considers balancing machining lines with parallel machines and sequence-dependent setup times. The goal is to minimize the number of machines for a given cycle time. Such lines are paced, i.e. parts are moved from one station to the next with a given cadence (defined by the line cycle time). At least one machine is installed at each station. Parallel machines are to be used when the corresponding station is overloaded, i.e. the total time of all operations assigned to the station exceeds the line cycle time. Moreover, station workload depends on the sequence in which the operations are executed because the setup times related to the changes and displacements of tools, rotations of the part, etc. In this paper, a heuristic method is proposed for the resolution of this problem. An industrial example is presented and numerical results are reported.

**Keywords**: Machining lines, parallel machines, sequence-dependent setup times, heuristic method, optimization.

**>>Full text **

**CITE THIS PAPER AS**:

Mohamed ESSAFI, Xavier DELORME, Alexandre DOLGUI, **Balancing Machining Lines: a Two-phase Heuristic**, *Studies in Informatics and Control*, ISSN 1220-1766, vol. 19 (3), pp. 243-252, 2010.

**1. Introduction**

Machining lines are widely used in automotive and other industries. They are expensive with heavy investments in their installation and implementation. This investment influences to a great extent the cost of the finished products. Therefore, machining line manufacturers are increasingly interested in the optimization of the line design process. The objective is to optimize some criteria such as the total investment cost, total number of workstations, cost of operations (tool, men power, energy, etc.), or the cycle time. Note that the profitability of the line depends directly on the expense of its design and so should be minimized. In this manner, optimization has become a crucial issue for the machining line design.

In this paper, we deal with the machining line balancing problem which appears at the preliminary design stage. We consider the serial-parallel lines composed of CNC (Computer Numerical Control) machines. There are parallel machines at each station and setup times between operations at each machine (sequence dependent setup-times). The main objective of the line balancing problem is to minimize the total number of machines for a given cycle time. We propose a two-phase heuristic method for the resolution of this problem.

This work is developed in co-operation with an industrial partner (PCI-SCEMM). PCI proposes solutions for the machining of complex parts such as cylinder heads. A peculiarity of this type of line is the necessity to put several machines in parallel at each station to respect a given cycle time. An additional characteristic of these lines is that there are sequence-dependent setup times at each station. To our knowledge, such a problem has not been studied in the literature.

The machining line is a special case of assembly lines [15]. A machining line is equipped with a set of machines by which different operations are executed. Each operation is characterized by: an operational time; a set of operations which must be assigned before (precedence constraints); a set of operations which must be executed on the same workstation (inclusion constraints); a set of operations which cannot be executed on the same workstation (exclusion constraints). The specificity of the considered problem deals with two main factors. The first is the necessity to consider unproductive times between the operations (setup times) varying according to the sequence in which the operations are assigned. The second factor is the possibility (and even the necessity) to parallelize the flow at each station using several parallel machines. The utilization of parallel machines creates an additional difficulty to balance the load, but it is necessary in the case of a station with the processing time higher than cycle time.

The paper is composed of six sections. In Section 2 a state of the art for the assembly line balancing problems is presented. Particular attention is given to those problems with parallel machines or sequence-dependent setup times. In Section 3, a complete definition of the problem as well as the notations used is given.

A heuristic method for approximate resolution of this problem is then proposed in Section 4. Section 5 deals with computational experiments and, finally Section 6 provides concluding remarks and perspectives of this work.

**References**:

- Amen, M.,
**Heuristic Methods for Cost-oriented Assembly Line Balancing: a Comparison on Solution Quality and Computing Time**, International Journal of Production Economics, vol. 69, 2001, pp. 255-264. - Andrés, C., C. Miralles, R. Pastor,
**Balancing and Scheduling Tasks in Assembly Lines with Sequence-dependent Setup Times**, European Journal of Operational Research, vol. 187, 2008, pp. 1212-1223. - Arcus, A. L., COMSOAL:
**A Computer Method of Sequencing Operations for Assembly Lines**, International Journal of Production Research, vol. 4, 1966, pp. 259-277. - Askin, R. G., M. Zhou,
**A Parallel Station Heuristic for the Mixed-model Production Line Balancing Problem**, International Journal of Production Research, vol. 35, nr. 11, 1997, pp. 3095-3105. - Bard, J. F.,
**Assembly Line Balancing with Parallel Workstations and Dead Time**, International Journal of Production Research, vol. 27, nr. 6, 1989, pp. 1005-1018. - Baybars, I.,
**A Survey of Exact Algorithms for the Simple Assembly Line Balancing Problem**, Management Science, vol. 32, nr. 8, 1986, pp. 909-932. - Belmokhtar, S., A. Dolgui, N. Guschinsky, G. Levin,
**An Integer Programming Model for Logical Layout Design of Modular Machining Lines**, Computers and Industrial Engineering, vol. 51, nr. 3, 2006, pp. 502-518. - Bhattachajee, T. K., S. Sahu,
**Complexity of Single Model Assembly Line Balancing Problems**, Engineering Costs and Production Economics, vol. 18, 1990, pp. 203-214. - Boyson, N., M. Fliedner, A. Scholl,
**A Classification of Assembly Line Balancing Problems**, European Journal of Operational Research, vol. 183, 2007, pp. 674-693. - Bukchin, J., J. Rubinovitz,
**A Weighted Approach for Assembly Line Design with Station Paralleling and Equipment Selection**, IIE Transactions, vol. 35, 2002, pp. 73-85. - Buxey, G. M.,
**Assembly Line Balancing with Multiple Stations**, Management Science, vol. 20, 1974, pp. 1010-1021. - Dolgui, A., B. Finel, N. Guschinsky, G. Levin, F. Vernadat,
**An Heuristic Approach for Transfer Lines Balancing**, Journal of Intelligent Manufacturing, vol. 16, nr. 2, 2005, pp. 159-171. - Dolgui, A., B. Finel, N. Guschinsky, G. Levin, F. Vernadat,
**MIP Approach to Balancing Transfer Lines with Blocks of Parallel Operations**, IIE Transactions, vol. 38, 2006, pp. 869-882. - Dolgui, A., N. Guschinsky, G. Levin,
**A Special Case of Transfer Lines Balancing by Graph Approach**, European Journal of Operational Research, vol. 168, nr. 3, 2006, pp. 732-746. - Dolgui, A., J. M. Proth,
**Les systèmes de production modernes**, Hermes, 2006. - Helgeson, W. P., D. P. Birnie,
**Assembly Line Balancing Using the Ranked Positional Weight Technique**, Journal of Industrial Engineering, vol. 12, 1961, pp. 394-398. - McMullen, P. R., G. V. Frazier,
**Using Simulated Annealing to Solve a Multiobjective Assembly Line Balancing Problem with Parallel Workstations**, International Journal of Production Research, vol. 39, nr. 10, 1998, pp. 2717-2741. - Moodi, C. L., H. H. Young,
**A Heuristic Method for Assembly Line Balancing for Assumption of Constant or Variable Elements Time**, Journal of Industrial Engineering, vol. 16, 1965, pp. 23-29. - Pinto, P. A., D. G. Dannenbring, B. M. Khumawala,
**A Branch and Bound Algorithm for Assembly Line Balancing with Paralleling**, International Journal of Production Research, vol. 13, nr. 2, 1975, pp. 183-196. - Rekiek, B., A. Dolgui, A. Dechambre, A. Bratcu,
**State of Art of Assembly Lines Design Optimization**, Annual Reviews in Control, vol. 26, nr. 2, 2002, pp. 163-174. - Wadhwa, S., Y. Ducq, M. Ali, A. Prakash,
**Performance Analysis of a Flexible Manufacturing System under Planning and Control Strategies**, Studies in Informatics and Control, vol. 17, nr. 3, 2008, pp. 273-284. - Salveson, M. E.,
**The Assembly Line Balancing Problem**, Journal of Industrial Engineering, vol. 6(4), 1955. - Scholl, A.,
**Balancing and Sequencing Assembly Lines**, Physica-Verlag Heidelberg, 1999. - Scholl, A., N. Boysen, M. Fliedner,
**The Sequence-dependent Assembly Line Balancing Problem**, Operation Research Spectrum, vol. 30, nr. 3, 2008, pp. 579-609. - Tangour, F., P. Borne,
**Presentation of Some Metaheuristics for the Optimization of Complex Systems**, Studies in Informatics and Control, vol. 17, nr. 2, 2008, pp. 169-180. - Wilhelm, W. E.,
**A Column-generation Approach for the Assembly System Design Problem with Tool Changes**, The International Journal of Flexible Manufacturing Systems, vol. 11, 1999, pp. 177-205.