A S I M U L A T E D A N N E A L I N G A L G O R I T H M F O R S E Q U E N C E-D E P E N D E N T P R O B L E M S I N V O L V E D I N F L E X I B L E F L O W S H O P G R O U P S C H E D U L I N G
Author(s):
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:
Language:
Persian
Published:
Industrial Engineering & Management Sharif, Volume:27 Issue: 1, 2011
Page:
75
magiran.com/p928789
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
دسترسی سراسری کاربران دانشگاه پیام نور!
اعضای هیئت علمی و دانشجویان دانشگاه پیام نور در سراسر کشور، در صورت ثبت نام با ایمیل دانشگاهی، تا پایان فروردین ماه 1403 به مقالات سایت دسترسی خواهند داشت!
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!