ترکیب بهینه سازی کلونی مورچه ها از طریق الگوریتم ژنتیک برای مونتاژ مخلوط مدل مساله موازنه خط با زمان راه اندازی وابسته به توالی بین وظایف

This paper presents a new hybrid algorithm, which executes ant colony optimization in combination with genetic algorithm (ACO-GA), for type I mixed-model assembly line balancing problem (MMALBP-I) with some particular features of real world problems such as parallel workstations, zoning constraints and sequence dependent setup times between tasks. The proposed ACO-GA algorithm aims at enhancing the performance of ant colony optimization by incorporating genetic algorithm as a local search strategy for MMALBP-I with setups. In the proposed hybrid algorithm ACO is conducted to provide diversification, while GA is conducted to provide intensification. The proposed algorithm is tested on 20 representatives MMALBP-I extended by adding low, medium and high variability of setup times. The results are compared with pure ACO pure GA and hGA in terms of solution quality and computational times. Computational results indicate that the proposed ACO-GA algorithm has superior performance.

Current markets are characterized as consumer-centric resulted in a growing trend for higher product variability. As a result of this, high-mix/low-volume manufacturing strategies substitute for low-mix/high-volume manufacturing strategies. Single-model assembly lines, which are the most suited production systems for low variety demand scenarios, are not able to respond the requirements of this new type of manufacturing strategies anymore. Therefore, manufacturers prefer producing one model with different features or several models on a single assembly line (mixed model assembly line, which was handled by Thomopoulos [1] for the first time in the literature) in order to avoid the high cost to build and maintain an assembly line for each model. Mainly two types of balancing problems arise for mixed-model assembly lines like traditional single-model assembly lines: design of a new assembly line for which the demand can be easily forecasted (Type-I) and redesign of an existing assembly line (Type-II) when changes in the assembly process or in the product range occurs. The MMALBP-I (resp. MMALBP-II) consists in assignment of tasks to workstations such that the precedence relations of each models are satisfied and the number of workstations (resp. the cycle time) is minimized for a given predefined cycle time (resp. predefined number of workstations) and given M models, the set of tasks associated with each model, the performance times of the tasks, and the set of precedence relations which specify the permissible orderings of the tasks for each model (Gokcen and Erel [2]). Both versions of the problem are NP-hard (Bukchin and Rabinowitch [3]). In this paper we propose a new hybrid algorithm, a combination of ant colony optimization (ACO) and genetic algorithm (GA), for MMALBP-I, which has some particular features of the real-world assembly line balancing problems such as parallel workstations, zoning constraints, and sequence dependent setup times between tasks. For most of the industrial assembly lines, it is assumed that the setups are negligible, because their times are very low compared to operation times. Moreover, setups are considered independently as they are executed just before or after the tasks, hence, their times are added to task times (Andrés et al. [4]). As a results of this situation, it is not required to determine task performing sequences in a workstation, however, task performing sequence is an essential issue in order to minimize the workstation global time, in case of sequence dependent setup times. On the other hand, considering sequence dependent setup times between tasks becomes more important when cycle time is low, since setup times may represent a high percentage of it. Most of the published papers on assembly line balancing problem with sequence dependent setup times have focused extensively on single model lines as distinct from the current study. Andrés et al.’s [4] were the first paper (see the corrigendum to this paper provided by Pastor et al. [5]) which considered the sequence-dependent setup times between tasks in the simple version of assembly line balancing problems (ALBPs), which they referred to as general assembly line balancing problem with setups (GALBPS). They formulated the GALBPS-I and provided some heuristics and a GRASP algorithm to solve the innovative problem. However, their emphasis was solely on the type I of GALBPS and unlike their model which is adaptable to GALBPS-II. After this study, Martino and Pastor [6] developed heuristic procedures based on priority rules to solve GALBPS-I; however, these approaches, which are not specifically designed for solving GALBPS-II, cannot provide high quality solutions in high-size tests. A similar sequence-dependent tasks time increments was introduced by Scholl et al. [7] which is defined as “whenever a task h is performed after another task i has been finished, its standard time th is incremented by a value. This sequence-dependent increment measures the prolongation of task h forced by the interference with the status of already having processed task i”. The problem of balancing two-sided assembly lines with setups (TALBPS) was considered by Özcan and Toklu [8]. A mixed integer program (MIP) was proposed to model and solve the problem. The proposed MIP minimizes the number of mated-stations (i.e., the line length) as the primary objective and it minimizes the number of stations (i.e., the number of operators) as a secondary objective for a given cycle time. A heuristic approach (2-COMSOAL/S) for especially solving large-size problems based on COMSOAL (computer method of sequencing operations for assembly lines) method was also presented. Seyed-Alagheband et al. [9] addressed SALBP-II where the simple version is enriched by considering sequence-dependent setup times between tasks (GALBPS-II). They proposed a mathematical model and a novel simulated annealing (SA) algorithm to solve it. To the best of our knowledge, this is the first attempt aims at solving MMALBP with setups. In the relevant literature several approaches have been presented to cope with MMALBP-I. These approaches can be divided into three groups: mathematical programming, heuristics/meta-heuristics and hybrid approaches. Besides assembly line balancing problems, hybrid algorithms were used for solving several combinatorial optimization problems and usually developed by integrating meta-heuristics with problem specific heuristic algorithms or meta-heuristics with meta-heuristics. On the other hand, hybrid algorithms have showed their ability to provide local optima of high quality. For more comprehensive reviews on hybrid meta-heuristics the reader can refer to the papers of Preux and Talbi [10], Talbi [11], Raidl [12] and Blum et al. [13]. In this paper, we attempt to hybridize ACO [14], [15], [16], [17], [18] and [19] with GA [20] and [21] in parallel (operation parallelization), which belongs to the class of parallel hybrid meta-heuristics (Crainic and Toulouse [22]). These algorithms are sufficiently complex to provide powerful adaptive search approaches, and usually can be embedded with other approaches to speed up the search performance (Lee et al. [23]). The rationale why we attempt to hybridize ACO with GA is to exploit the complementary character of different optimization strategies, that is, hybrids are believed to benefit from synergy (Blum et al. [13]). Viz., our proposed hybrid algorithm integrates the positive feedback mechanism and the satisfactory performance of ACO with the faster speed of GA. Thus, the proposed hybrid ACO-GA algorithm attempt to overcome the slower speed of ACO and the poor searching capability of GA, especially for large sized problems, by embedding GA into ACO as a local search. Furthermore, ACO-GA utilizes the synergy of GA as an improvement procedure and ACO as a constructive procedure. The rest of the study is organized as follows. A literature survey on MMALBP-I and the definition of MMALBP-I with sequence dependent setup times between tasks are given in Section 2. The proposed hybrid ACO-GA algorithm is defined in Section 3. Comparative study is given in Section 4. Finally, the discussions and conclusions are presented in Section 5.

In this paper, we aimed at hybridizing ACO with GA in order to improve search ability of ACO for solving mixed-model assembly line balancing problem with sequence dependent setup times between tasks. In the proposed hybrid ACO-GA algorithm, GA embedded into ACO. In order to evaluate the real performance of the proposed hybrid ACO-GA algorithm, a set of 20 mixed-model assembly line balancing problems with parallel workstations and zoning constraints was tested. As to the scope of this paper, this set of benchmark problems was differentiated by adding sequence sependent setup times between tasks with low, medium and high variabilities. Due to the lack of optimal solutions for the benchmark set with setups, a procedure for determining lower bounds for the problem on hand was derived, for evaluating the proposed hybrid ACO-GA algorithm in terms of number of workstations. The performance of the proposed hybrid ACO-GA algorithm was also compared with the performances of pure ACO, pure GA and hGA. Computational results indicates that ACO-GA can improve search performance and outperforms ACO, GA and hGA. Future researches will focus on applying the proposed hybrid ACO-GA algorithm to different types of assembly line balancing problems or the application of ACO-GA to different combinatorial optimization problems.