Definition and evaluation of the difficulty of the Car Sequencing Problem

Julien Maheut

https://orcid.org/0000-0002-5796-9053

Spain

EDEM Escuela de Empresarios

Profesor Agregado

Submitted: 2016-03-22

|

Accepted: 2016-05-20

|

Published: 2016-05-30

DOI: https://doi.org/10.4995/wpom.v7i1.5173
Funding Data

Downloads

Keywords:

Car Sequencing Problem, Sequencing Rule, Dificulty

Supporting agencies:

This research was not funded

Abstract:

The Car Sequencing Problem is a relevant topic both in the literature and in practice. Typically, the objective is to propose exact or heuristic procedures that calculate, in a reduced computational time, a solution that minimizes the number of violated sequencing rules. However, reaching a solution that does not violate any sequencing rule is not always possible because although sequencing rules should be defined to smooth the workload, the evolution of the production mix or some other characteristics can influence the quality of the solutions. In this paper, a first definition of a sequencing rule difficulty is proposed and a statistical study is performed, which allow us to determine the impact of the number of rules, as well as to evaluate how difficult an instance is.
Show more Show less

References:

Benoist, T. (2008). Soft car sequencing with colors: Lower bounds and optimality proofs. European Journal of Operational Research, 191(3), 957–971. http://doi.org/http://dx.doi.org/10.1016/j.ejor.2007.04.035

Bergen, M. E., Van Beek, P., & Carchrae, T. (2001). Constraint-based vehicle assembly line sequencing. In Advances in Artificial Intelligence (pp. 88–99). Springer.

Bolat, A., & Yano, C. A. (1992). Scheduling algorithms to minimize utility work at a single station on a paced assembly line. Production Planning & Control, 3(4), 393–405.

Boysen, N., Fliedner, M., & Scholl, A. (2009). Sequencing mixed-model assembly lines: Survey, classification and model critique. European Journal of Operational Research, 192(2), 349–373. http://doi.org/http://dx.doi.org/10.1016/j.ejor.2007.09.013

Briant, O., Naddef, D., & Mounié, G. (2008). Greedy approach and multi-criteria simulated annealing for the car sequencing problem. European Journal of Operational Research, 191(3), 993–1003. http://doi.org/http://dx.doi.org/10.1016/j.ejor.2007.04.052

Drexl, A., & Kimms, A. (2001). Sequencing JIT mixed-model assembly lines under station-load and part-usage constraints. Management Science, 47(3), 480–491.

Drexl, A., Kimms, A., & Matthießen, L. (2006). Algorithms for the car sequencing and the level scheduling problem. Journal of Scheduling, 9(2), 153–176.

Fisher, M. L., & Ittner, C. D. (1999). The impact of product variety on automobile assembly operations: Empirical evidence and simulation analysis. Management Science, 45(6), 771–786.

Fliedner, M., & Boysen, N. (2008). Solving the car sequencing problem via branch & bound. European Journal of Operational Research, 191(3), 1023–1042.

Gent, I. P. (1998). Two results on car-sequencing problems. Research Reports of the APES Group, APES-02-1998, Available from Http://www.dcs.stand.ac.uk/~ Apes/apesreports.html.

Gent, I. P., & Walsh, T. (1999). CSPLib: a benchmark library for constraints. In Principles and Practice of Constraint Programming–CP’99 (pp. 480–481). Springer.

Golle, U., Boysen, N., & Rothlauf, F. (2010). Analysis and design of sequencing rules for car sequencing. European Journal of Operational Research, 206(3), 579–585.

Gottlieb, J., Puchta, M., & Solnon, C. (2003). A study of greedy, local search, and ant colony optimization approaches for car sequencing problems. In Applications of evolutionary computing (pp. 246–257). Springer.

Gravel, M., Gagne, C., & Price, W. L. (2005). Review and comparison of three methods for the solution of the car sequencing problem. Journal of the Operational Research Society, 56(11), 1287–1295.

Kis, T. (2004). On the complexity of the car sequencing problem. Operations Research Letters, 32(4), 331–335.

Maheut, J., & Garcia-Sabater, J. P. (2015). Reglas de secuenciación en el problema de secuenciación en línea de montaje con mezcla de modelos. WPOM-Working Papers on Operations Management, 6(2), 39. http://doi.org/10.4995/wpom.v6i2.3525

Parrello, B. D., Kabat, W. C., & Wos, L. (1986). Job-shop scheduling using automated reasoning: A case study of the car-sequencing problem. Journal of Automated Reasoning, 2(1), 1–42.

Puchta, M., & Gottlieb, J. (2002). Solving car sequencing problems by local optimization. In Applications of Evolutionary Computing (pp. 132–142). Springer.

Smith, B. M. (1996). Succeed-first or fail-first: A case study in variable and value ordering.

Solnon, C. (2000). Solving permutation constraint satisfaction problems with artificial ants. In ECAI (Vol. 2000, pp. 118–122).

Solnon, C., Cung, V. D., Nguyen, A., & Artigues, C. (2008). The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem. European Journal of Operational Research, 191(3), 912–927. http://doi.org/http://dx.doi.org/10.1016/j.ejor.2007.04.033

Valero Herrero, M., & Molina Morte, P. (2012). CSP Dinámico: Un algoritmo dinámico para la resecuenciación en un almacén de líneas en paralelo. Working Papers on Operations Management, 4(1).

Show more Show less