A Heuristic Approach for Car Sequencing Problem Including Assembly Ratio and Color Constraints

A Heuristic Approach for Car Sequencing Problem Including Assembly Ratio and Color Constraints

Emek Gamze Köksoy Atiker, Fatma Betül Yeni, Peiman A. Sarvari, Emre Çevikcan
DOI: 10.4018/978-1-5225-2944-6.ch004
(Individual Chapters)
No Current Special Offers


A car factory contains three main workshops; body shop, paint shop and assembly shop. Each of these three workshops has their set of constraints which have to be met in a production day by arranging the vehicles. The car sequencing problem is used to create a production sequence that meets these constraints. Car sequencing problem first handled in the literature by optimization of assembly constraints including ratio constraints. After that, color constraints are integrated to assembly constraints. At this chapter, the scenario in which high priority ratio constraints are primary, color constraints are secondary is tackled and a heuristic approach is proposed. For optimization of ratio constraints, an initial algorithm based on the greedy algorithm is used. The developed algorithm is coded and used on data set which is proposed by Renault at the ROADEF'2005 challenge. According to results, it is achieved the range of results which is achieved by ROADEF finalists.
Chapter Preview

Car Sequencing Problem

A standard car factory consists of three main production workshops; a body shop where the body is built up by forming sheets, a paint shop where corrosion resistance of the body is increased, and the body is painted and an assembly shop, where different components of the vehicles are installed. Figure 1 depicts the stages of the production line.

Figure 1.

Stages of the production line


The car sequencing problem is about deciding the best sequence which makes the production process in these three workshops easier (Estellon et al., 2007). Each production workshop has its constraints, and all these constraints can conflict with each other. Due to these constraints challenge in the problem, only assembly shops took into consideration in the earlier studies.

While the constraints of the body shop and assembly shop are quite similar each other, the constraints of paint shop are different (Prandstetter & Raidl, 2008). Some of the constraints that are defined for body and assembly shops are given below (Prandstetter, 2005):

  • There must be found component c at maximum l cars in a sliding window of m vehicles.

  • There must be exactly l cars which have component c in every subsequence with length m.

  • None of the vehicles with component c1 should be followed by vehicles with component c2.

  • The vehicle with component c must be followed by at least lmin cars are without component c.

Key Terms in this Chapter

Sequencing Problem: Selection of an appropriate order in which a number of jobs/operations can be assigned to a finite number of service facilities to optimize the outputs in term of time, cost or profit.

Roadef Challenge: It is organized by the French Society of Operational Research and aims to share the latest developments in the industry.

Heuristic: A heuristic is a mental shortcut that allows people to solve problems and make judgments quickly and efficiently.

Ratio Constraints: In a standard car sequencing problem, the vehicles which require complex operations have to be sequenced with an adequate distance. This is provided with p/q ratio constraints.

Complete Chapter List

Search this Book: