» Download Article

Authors
Essafi, Mohamed; Delorme, Xavier; Dolgui, Alexandre

Identifier
10.3182/20090603-3-RU-2001.00125

Index Terms
Line Design and Balancing; Machining and Assembly Systems; Heuristic and Metaheuristics

Abstract
This paper deals with an industrial transfer line balancing problem (TLBP) involving specific constraints. The studied lines are paced and serial, i.e. a part to be machined passes through a sequence of stations. At least one CNC (Computer Numerical Controller) machine is installed at each station. As usual with transfer lines, this problem is subject to precedence constraints as well as exclusion and inclusion constraints. Moreover, the station workload depends on the sequence in which the operations are assigned to the station because of set-up times related to the change and displacement of tools, rotation of the part, etc. In addition, accessibility constraints have to be considered, and different types of CNC machines with different characteristics can be used depending on the operations to perform. The objective is to assign a given set of operations, required for part machining, as well as a set of machines to a sequence of stations while minimizing the total cost of the line.We propose here a heuristic based on the GRASP (Greedy Randomized Adaptive Search Procedures) metaheuristic to consider large size industrial cases.

References

REFERENCES

M. Amen. Heuristic methods for cost-oriented assembly 
line balancing: A comparison on solution quality and 
computing time. International Journal of Production 
Economics, 69:255-264, 2001.

C. Andres, C. Miralles, and R. Pastor. Balancing 
and scheduling tasks in assembly lines with sequence-
dependent setup times. European Journal of Operational 
Research, 187:1212-1223, 2008.

A.L. Arcus. COMSOAL: a COmputer Method of Sequencing 
Operations for Assembly Lines. International
Journal of Production Research, 4:259-277, 1966.

R.G. Askin and M. Zhou. A parallel station heuristic 
for the mixed-model production line balancing problem. 
International Journal of Production Research, 35(11): 
3095-3105, 1997.

J.F. Bard. Assembly line balancing with parallel 
workstations and dead time. International Journal 
of Production Research, 27(6):1005-1018, 1989.

I. Baybars. A survey of exact algorithms for the simple 
assembly line balancing problem. Management Science, 
32(8):909-932, 1986.

S. Belmokhtar, A. Dolgui, N. Guschinsky, and G. Levin.
An integer programming model for logical layout design
of modular machining lines. Computers and Industrial
Engineering, 51(3):502-518, 2006.

T.K. Bhattachajee and S. Sahu. Complexity of single
model assembly line balancing problems. Engineering
Costs and Production Economics, 18:203-214, 1990.

N. Boysen, M. Fliedner, and A. Scholl. Assembly line
balancing: which model to use when? International
Journal of Production Economics, 111:509-528, 2008.

J. Bukchin and A. Rubinovitz. A weighted approach
for assembly line design with station paralleling and
equipment selection. IIE Transactions, 35:73-85, 2002.

G.M. Buxey. Assembly line balancing with multiple
stations. Management Science, 20:1010-1021, 1974.

X. Delorme, A. Dolgui, M. Essafi, L. Linxe, and D. Poyard.
Automatic machining lines: Design and optimization.
In S.Y. Nof, editor, Handbook of Automation. Springer,
2008. (to appear).

A. Dolgui, B. Finel, N. Guschinsky, G. Levin, and F. Ver-
nadat. Mip approach to balancing transfer lines with
blocks of parallel operations. IIE Transactions, 38:869-
882, 2006a.

A. Dolgui, N. Guschinsky, and G. Levin. On problem of op-
timal design of transfer lines with parallel and sequential
operations. In J.M. Fuertes, editor, Proceedings of the
7th IEEE International Conference on Emerging Tech-
nologies and Factory Automation (ETFA'99), volume 1,
pages 329-334, Barcelona, Spain, October 18-21 1999.

A. Dolgui, N. Guschinsky, and G. Levin. A special case
of transfer lines balancing by graph approach. European
Journal of Operational Research, 168(3):732-746, 2006b.

A. Dolgui and I. Ihnatsenka. Branch and bound algo-
rithm for a transfer line design problem: Stations with
sequentially activated multi-spindle heads. European
Journal of Operational Research, 2008. available online,
doi:10.1016/j.ejor.2008.03.028, (in Press).

A. Dolgui, (Ed.). Feature cluster on the balancing of
assembly and transfer lines. European Journal of Op-
erational Research, 168(3):663-951, 2006.

M. Essafi, X. Delorme, and A. Dolgui. A heuristic method
for balancing machining lines with paralleling of stations
and sequence-dependent setup times. In Proceeding of
the International Workshop LT2007, Sousse, Tunisia,
18-20 November 2007, pages 349-354, 2007.

M. Essafi, X. Delorme, A. Dolgui, and O. Guschinskaya.
Mip approach for balancing flexible transfert lines with
complex industrial constraints. Research Report 2008-
500-4, Ecole des Mines de Saint-Etienne, 2008. 

T.A. Feo and M.G.C. Resende. A probabilistic heuristic
for a computationally dificult set covering problem.
Operations Research Letters, 8:67-71, 1989.

B. Finel, A. Dolgui, and F. Vernadat. A random search
and backtracking procedure for transfer line balancing.
International Journal of Computer Integrated Manufac-
turing, 21(4):376-387, 2008.

O. Guschinskaya, A. Dolgui, N. Guschinsky, and G. Levin.
A heuristic multi-start decomposition approach for op-
timal design of serial machining lines. International
Journal of Operational Research, 189:902-913, 2008.

W.P. Helgeson and D.P. Birnie. Assembly line balancing
using the ranked positional weight technic. Journal of
Industrial Engineering, 12:394-398, 1961.

P.A. Pinto, D.G. Dannenbring, and B.M. Khumawala. A
branch and bound algorithm for assembly line balancing
with paralleling. International Journal of Production
Research, 13(2):183-196, 1975.

B. Rekiek, A. Dolgui, A. Delchambre, and A. Bratcu. State
of art of optimization methods for assembly line design.
Annual Reviews in Control, 26:163-174, 2002.

M.G.C Resende and C.C. Ribeiro. Greedy Randomized
Adaptive Search Procedures: advances and applications.
In J.Y. Potvin and M. Gendriau, editors, Handbook
of Metaheuristics, 2nd Edition. Springer, 2008. (to
appear).

M.E. Salveson. The assembly line balancing problem.
Journal of Industrial Engineering, 6(4):18-25, 1955.

A. Scholl. Balancing and Sequencing of Assembly Line.
Physica-Verlag, Heidelberg, 1999.

A. Scholl, N. Boysen, and M. Fliedner. The sequence-
dependent assembly line balancing problem. OR Spectrum, 
2007. (to appear).

J. Szadkowski. Critical path concept for multi-tool cut-
ting processes optimization. In Manufacturing Systems
Modeling, Management and Control: Proceedings of the
IFAC Workshop, Vienna, Austria, pages 393-398. Else-
vier, 1997.

W.E. Wilhelm. A column-generation approach for the
assembly system design problem with tool changes. In-
ternational Journal of Flexible Manufacturing Systems,
11:177-205, 1999.