بررسي مسئله تك ماشين با تابع هدف كمينه كردن بيشينه كردن تاخير و فروض زوال تكه اي و ورود غير هم زمان كارها

چكيده انگليسي :

89Minimizing the Maximum Lateness in Single Machine Scheduling Problem with Ready Time and Deteriorating Jobs Maryam Ghasemzadeh m ghasemzadeh@in iut ac ir Date of Submission 2010 04 20 Department Industrial and system Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor Ghasem moslehi moslehi@cc iut ac irAbstractNowadays scheduling problems have a lot of applications in productive systems At the most schedulingproblems processing time of jobs is supposed to be fixing It might be true in some cases but under someconditions delay in doing jobs leads into increasing the processing time and as a result deterioration In thisresearch single machine scheduling problems with considering the assumption of piecewise deteriorating jobs ready time with considering tow cases of existence of idle insert and inexistence of it has been studied First ageneral classification of these problems is presented and at the framework of this classification literature ofsingle machine scheduling problem with assumption of deteriorating jobs is reviewed Single machine scheduling problems with consideration of piecewise deterioration ready time and assumption ofidle insert for machine and the objective function of minimizing the maximum lateness has been studied Because no previous study on the problem has been done at first complexity of the problem was determined andshown that is a NP Hard problem We have extended a heuristic algorithm for the problem Also a branch andbound with up and down limit and some efficient dominance principles is presented Computational results for1620 instances of the problem show that the branch and bound procedure was able to find the optimal solutionof the 87 53 of the instances This shows the efficiency of the algorithm Because the definition ofdeterioration for this problem covers a lot of possible definitions for deterioration we have run our algorithmson two special cases of the problem with applying changes in number of defined criterions Computationalresults for of branch and bound algorithm for these cases shows that this algorithm works good to solve variouscases of the problem At the continuation because in a lot of cases consideration of idle insert for the machine is not possible singlemachine scheduling problem with piecewise deterioration ready time and inexistence on idle insert for themachine and the objective function of minimizing maximum lateness has been studied Because it doesn t existany previous study for this problem too like previous problem complexity of the problem has been calculatedand shown that it is a NP Hard problem too Because of some specifications that inexistence of idle insertapplied to the problem division of the problem to smaller problems got possible with definition of block Forthis problem we have extended a heuristic algorithm too Also a branch and bound algorithm with up and downlimits and efficient dominance principles is proposed Computational results for 1440 problem instances showthat branch and bought algorithm could solve 85 28 of the instances optimally Keywords Scheduling Single machine Deterioration Branch and Bound Idle insert

قاسم زاده، مريم

بررسي مسئله تك ماشين با تابع هدف كمينه كردن بيشينه كردن تاخير و فروض زوال تكه اي و ورود غير هم زمان كارها

زمان بندي , شاخه و كران , بيكاري عمدي