Optimization and Machine Learning

4Solving the Mixed-model Assembly Line Balancing Problem by using a Hybrid Reactive Greedy Randomized Adaptive Search Procedure

Belkharroubi LAKHDAR and Khadidja YAHYAOUI

University of Mascara, Algeria

In order to meet customer demand for different products at any one time, many industries use special mixed-model assembly lines where different product models are assembled in an inter-mixed sequence. In designing these types of lines, a critical problem – the mixed-model assembly line balancing problem – must be solved, in order to minimize the number of workstations (type-1) or the cycle time (type-2). This chapter addresses the type-2 mixed-model assembly line balancing problem with deterministic task times. To solve this problem, an enhancement of the greedy randomized adaptive search procedure (GRASP) is proposed; it is known as the reactive GRASP. This reactive version is based on the variation of the value of the restricted candidate list parameter alpha, in contrast to the basic version which is based on the fixed value. The variation of the value of the alpha helps the algorithm to find better solutions that cannot be found with a fixed value. Furthermore, the basic GRASP is limited by not drawing fully on previous iterations; using information from previous solutions can influence the construction phase. The proposed reactive GRASP is hybridized with the ranked positional weight heuristic to construct initial solutions; the neighborhood search procedure is then applied ...