Document Type : Article
Authors
1
Dept. of Industrial Engineering \nMazandaran Uni&
2
Dept. of Industrial Engineering Sharif Univers&zwnj
Abstract
Group scheduling within the context of sequence dependent setup times in a flexible flow shop, with minimizing the makespan as the objective (FFm$|$fmls, S$_{plr}$$|$C$_{max}$), is considered in this research. A mixed integer linear programming model is developed for the research problem. Since the proposed research problem is proved to be NP-hard, two different metaheuristic approaches, based on simulated annealing (SA), are eveloped to solve the problem heuristically. The search space of the algorithm is increased by permitting the searching process to repeat at each temperature, N times, where N is the length epoch. Several stopping criteria are used to increase the searching speed of the proposed SA-based heuristic. Intense mutation is also applied to prevent the search becoming trapped in local optimum. In intense mutation, the positions of two random groups at each stage are exchanged. Since generating the initial solution in the area of a flexible flow shop has its own omplexities, four different initial solution (IS) finding mechanisms, with varying levels of computational difficulty, are also developed to aid the search algorithms in identifying an IS.In this research, we use two approaches to generate initial and neighboring schedules. In the first approach, the sequence of groups and jobs at the first stage are determined, to show an initial solution. The job sequences from stage two to the last stage are determined according to the FIFO rule, so that groups are ordered according to their first job completion time at the previous stage. In other words, a group whose first job is completed sooner at one stage will be processed sooner at the next stage. Allocation of groups to identical parallel machines is determined according to a greedy algorithm. Based on this algorithm, the group is assigned to a machine at each stage when the process of jobs of the group is completed sooner than other machines at the stage. In the second approach, to show an initial solution, the assigned groups to each machine at each stage, and the sequence of groups and jobs on each machine at the first stage, are determined. Then, the sequence of groups, as well as the jobs belonging to that group at other stages, is determined, according to the FIFO rule. The assignment of groups to the parallel machines of a stage, in stages two to m, is determined, according to the greedy algorithm. In order to find the best neighboring solution, a two-level, SA based metaheuristic algorithm is proposed. At the first level, the neighborhood for the group sequence is obtained by performing an outside perturbation on the group sequence. Outside perturbation on the group sequence is performed by three neighborhood mechanisms, namely: the shift move (SM), the pairwise interchange (PI) and transfer to another machine (TAM). At the second level, the neighborhood for the job sequence is obtained by performing the inside perturbation on the job sequence. For inside perturbation, the partial pairwise interchange mechanism is used.%looseness=1 For evaluating the performance of the proposed algorithms, the makespan value and the elapsed time to solve the test problems are considered as two response variables; representing the effectiveness and efficiency of the algorithms. Based on obtained results using makespan, the proposed SA algorithm, in which the sequence of groups and jobs at the first stage provides the initial solution, with an initial solution random generating mechanism, is recommended for all sizes. For the elapsed time, the SA algorithm, in which the sequence of groups and jobs at the first stage is used as an initial solution with an initial solution random generating mechanism, provides a better result than the other proposed algorithms. The performance of the metaheuristic algorithm is compared with the only available metaheuristic algorithm in literature, i.e., the Tabu search, to evaluate the quality of the proposed algorithm. The results show that the proposed SA algorithm in this research has a superior performance to the Tabu search, based on a paired t-test comparison.
Keywords
)