الگوریتم بهینه سازی کلونی مورچه برای هماهنگی نصب در سیستم تولید دو مرحله ای

This paper is concerned with the coordination of setup times in a two-stage production system. The problem is derived from a furniture plant, where there are two consecutive departments including cutting and painting departments. Items with the same levels of both attributes are grouped into a single batch in advance. A sequence-dependent setup time is required in a stage when a new batch has a different level of attribute from the previous one. The objective is to minimize the total setup time. In this paper, we first propose a simple dispatching rule called the Least Flexibility with Setups (LFS) rule. The LFS rule can yield a solution better than an existing genetic algorithm while using much less computation time. Using the LFS rule as both the initial solution method and the heuristic desirability, an Ant Colony Optimization (ACO) algorithm is developed to further improve the solution. Computational experiments show that the proposed ACO algorithm is quite effective in finding the near-optimal solution.

Although the literature on supply chain management is extensive, the coordinated scheduling within supply chain models has received much less attention [1] and [2]. In this paper, we add to the limited literature on supply chain scheduling by considering a scheduling problem that arises in the setup coordination between two and three consecutive stages of a supply chain. The setup coordination problem was first proposed by Agnetis et al. [3]. As depicted in Fig. 1, the problem arises from the manufacturing of a kitchen furniture plant [3], where there are two consecutive departments including cutting and painting departments. In this production system, each attribute has many different levels, e.g., the color attribute may have black, white, yellow, blue, and red different colors. Items with the same levels of both attributes are grouped into a single batch in advance. A setup occurs when a new batch has a level of an attribute different from the previous batch. Since no buffer is available between two consecutive departments, these departments have to follow the same batch sequence. Hence, we need only to determine a permutation of batches.Agnetis et al. [3] considered the problem with two objectives. One is minimizing the total number of setups (MINSUM) in the two departments, and the other is minimizing the maximum number of setups (MINMAX) in either department. It was assumed that all the setup times are equal and sequence independent, i.e., unitary setup time. This implies that in the painting department the setup changed from blue to white has the same time as that changed from white to blue. Each of the two objectives has been proved to be NP-hard by Agnetis et al. [3]. In the literature, metaheuristics have been applied to many manufacturing systems [4]. In particular, several heuristics have been proposed for the problem. For the MINSUM problem, Agnetis et al. [3] and Meloni [5] proposed a constructive heuristic and a metaheuristic for the problem, respectively. Both solution approaches perform satisfactorily on a set of real cases and a large sample of experimental data. Detti et al. [6] transformed the MINSUM problem into an edge-domination problem related to the Hamiltonian completion number of line graphs. They developed an iterated local search (ILS) algorithm, which outperforms the heuristic of Agnetis et al. [3]. Considering both MINSUM and MINMAX simultaneously as a multi-objective problem, most studies applied metaheuristics to find a good approximation of the Pareto-optimal front. Mansouri [7] proposed a multi-objective genetic algorithm (MOGA), and shortly after Mansouri [8] presented a better multi-objective simulated annealing (MOSA). Also, Meloni et al. [9] compared three approaches based on different combinations of multi-objective evolutionary algorithms and local-search heuristics. Recently, Detti et al. [10] developed a graph-based ILS algorithm in which two greedy heuristics are used to obtain the initial solution. The computational results show that the ILS algorithm combining with the initial solution can obtain the effectiveness with respect to solution quality and computation time. With regard to applications of ACO in supply chain, Liao and Chang [11] first used ACO in forecasting future demands and determining the optimal inventory policy values in a supply chain network. In all the above mentioned papers, a unitary setup time is assumed. However, an explicit consideration of sequence-dependent setup time is usually required in many practical manufacturing environments, including the furniture manufacturing. As an illustration in the painting department, the setup time changed from blue to white is usually different from that changed from white to blue. Naso et al. [12] developed and compared three GAs for solving the problems related to three cost structures for setup operations, including the case of sequence-dependent setup times. In this paper, we address the MINSUM problem with sequence-dependent setup times and propose an Ant Colony Optimization (ACO) algorithm, which will be compared with the GA developed by Naso et al. [12]. The remainder of this paper is organized as follows. In Section 2, we give a formal definition of the problem. Section 3 describes the GA developed by Naso et al. [12]. Section 4 provides a detailed description of the proposed dispatching rule and ACO algorithm. Results of computational experiments to evaluate the performance of the proposed solution method are reported in Section 5. Finally, the concluding remarks and further works are given in Section 6.

This paper has investigated the setup coordination problem in a two-stage production system where the setup times are sequence dependent. The objective is to minimize the total setup time in the two stages. First, we have proposed an LFS dispatching rule, which combines the flexibility index and the setup times into a single index. Then, an ACO algorithm is developed to obtain a near-optimal solution. ACO is chosen as the solution approach because the problem is equivalent to an asymmetric TSP. The developed ACO algorithm has several features that make it effective for the problem. These features are summarized as follows: 1. A new dispatching rule: The new LFS dispatching rule is used as both the initial solution method and the heuristic desirability in the algorithm. 2. New τ0 and global updating rule: To avoid premature convergence, we modify the parameter setting of τ0 and the global updating rule in the algorithm. 3. Local improvement method: We employ the Random Job Insertion Local Search (RJILS) as the local improvement method. 4. Minimum pheromone: We introduce a minimum pheromone value τt(i, j) = (1/5)τ0 to avoid the solution falling into a local optimum that results from the pheromone evaporating to zero. To evaluate the LFS rule and the ACO algorithm, they have been compared with an existing genetic algorithm and two new ACO algorithms for solving TSP. Computational results show that the LFS rule is quite useful and the ACO algorithm performs significantly better than the genetic algorithm and the two ACO algorithms. There are some possible directions for future research. First, due to the usefulness of the LFS dispatching rule, it is worthwhile to further investigate the dispatching rule for the problem and the related problems. Second, it is interesting to see how other metaheuristics such as Tabu Search (TS) and Particle Swarm Optimization (PSO) perform for this problem. Finally, future work can be extended to consider a three-stage production system with sequence-dependent setup times.