Application of Graph Theory for Production Orders Sequencing in Mixed-Model Production Systems

Abstract:

In this paper, problem of sequencing of production orders in mixed-model assembly systems is being analysed. The sequencing in such system is mostly addressed as a CSP problem (Car Sequencing Problem) and due to the fact that no optimal method of solution has yet been found it belongs to the NP-hard problems [1,2]. The NP-hardness of the problem has been proven in [3]. The problem connected with proper sequencing arises from the fact that nowadays it’s the clients who have the biggest influence on the sellers offer. The possibility to customize almost each and every product complicates the production management, as instead of having 10 different products, the number of them may grow up to few hundreds [4]. The problem may be especially observed in automotive industry, however recently it may be also met in household appliances industry, as mass customization can be also observed on that market. Each product may differ in labor-effectiveness, and due to the fact of carrying the assembly in linear assembly systems, each unevenness, each transgression of takt time on a single work-station may lead to the line stoppage.

• Periodical: Applied Mechanics and Materials (Volumes 809-810)
• Pages: 1343-1347
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.809-810.1343
• Online since: November 2015
• Authors: Marcin Zemczak*, Bożena Skołud, Damian Krenczyk
• Keywords: Graph Theory, Mixed-Model Production, Scheduling, Sequencing

References

[1] I. P. Gent, Two results on car sequencing problem, APES Research Report 02-1998, Department of computer science, University of Strathclyde, Glasgow, Scotland, (1998).

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

DOI: 10.1016/j.orl.2003.09.003

[3] B. Estellon, F. Gardi, Car sequencing is NP-hard: a short proof, Journal of the Operational Research Society. 64 (2013), 1503–1504.

DOI: 10.1057/jors.2011.165

[4] M. Zemczak, D. Krenczyk, Formulation of a sequencing problem in a mixed-model production system, Journal of Machine Engineering, 12, 3 (2012) 45-51.

[5] W. Grzechca, Methodology for cost oriented assembly line balancing problems, Total Logistic Management, 4 (2011) 57-67.

[6] M. Zemczak, Computer aided simulation of a mixed-model production system, Selected Engineering Problems. 3 (2012) 213-218.

[7] C. Solnon, V. D. Cung, A. Nguyen, C. Artigues, 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 (2008) 912 – 927.

DOI: 10.1016/j.ejor.2007.04.033

[8] E, Grandys, Study of changes in the production process based in graph theory, in: Y. Zhang (Ed. ), New frontiers in graph theory, InTech, 2012, pp.471-492.

DOI: 10.5772/37079