6611

6162

كارشناسي ارشد

مهندسي صنايع

اصفهان: دانشگاه صنعتي اصفهان، دانشكده صنايع و سيستم ها

1390

ده، 111ص.: مصور، جدول، نمودار

ص.ع. به فارسي و انگليسي

قاسم مصلحي

علي شاهنده

30/1/91

مهدي بيجار، حميد مير محمدي

1396/10/12

كتابنامه

صنايع و سيستم ها

مهندسي صنايع و سيستم ها

ID6162

به فارسي و انگليسي: قابل رويت در نسخه ديجيتالي

Minimizing the Total Completion Time for the Blocking Flow Shop Scheduling Problem Danial Khorasanian d khorasanian@in iut ac ir Ghasem Moslehi Supervisor moslehi@cc iut ac ir Department of Industrial and Systems Engineering Isfahan University of Technology Isfahan 84156 83111 IranDegree M Sc Language PersianDate 2012 02 04AbstractIn the general flow shop model it is assumed that the buffers have unlimited capacity However inmany real flow shop environments the buffers have zero capacity that the related problem isknown as the blocking flow shop scheduling problem BFSP In recent years the BFSP hasattracted much attention among researchers But most of the studies are done for makespan criteriaand studies about the other criteria are scarce In this study we developed some exact and inexactmethods for solving the BFSP with total completion time criteria To the best of our knowledge noexact method has been presented for the considered problem so far So first we proposed twomixed binary integer programming models one based on departure time of the jobs from eachmachine and another based on idle and blocking times of the jobs on each machine After this forpresenting a more powerful exact method for the considered problem we suggested a branch andbound algorithm The suggested lower bounds have been developed based on the consideredproblem characteristics and its graph for a specific sequence Also the proposed procedures enjoynovel ideas and increase the branch and bound strength very much The proposed branch andbound algorithm succeeded in solving 17 instances of the first two groups of Taillard benchmarkinstances considering 3600 second time limit After developing the mentioned exact methods weproposed an improved iterated greedy IG algorithm for obtaining efficient solutions for the largesized problems This algorithm showed much more efficiency than the only last proposedmetaheuristic Finally we tried to present some new rules for the two machine case of theconsidered problem So first we showed how to obtain the optimal solution of two special cases ofthis problem Then we proposed a branch and bound algorithm for solving the mentioned problem For this algorithm we developed a heuristic using IG algorithm idea for obtaining an initial upperbound We also developed one new efficient lower bound and three procedures for fathoming thenodes The suggested branch and bound succeeded in solving 75 of the problems up to 30 jobs considering 3600 time limit Keywords Blocking flow shop scheduling problem Total completion time Mixed binary integerprogramming model Branch and bound algorithm Iterated greedy algorithm Taillard benchmarkproblems

قاسم مصلحي

علي شاهنده

مهدي بيجار، حميد مير محمدي