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.