زمان بندي تك ماشين با محدوديت دسترسي

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

Single Machine Scheduling with Availability Constraint Ehsan Molaee e molaee@in iut ac ir Department of Industrial Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Farsi Ghasem Moslehi moslehi@cc iut ac ir Supervisor Abstract Todays Scheduling problrms have wide applications in many production and service systems Most scheduling problems are based on the assumption that machine works continuously during the planning horizon This assumption is not true in many production environments because the machine may not be available during one or more periods such as during maintenance operations In this thesis single machin scheduling problems with availability constraint have been considered At first a general division of these problems are explained and based on this framework the literature on deterministic single machine scheduling problems with one and multiple fixed non availability periods is reviewd First the single machine scheduling problem with one fixed unavailability period and non resumable jobs with the aim of minimizing the number of tardy jobs is studied By proving a number of theorems a heuristic procedure is developed to solve the problem A branch and bound approach is also presented which includes efficient upper and lower bounds and dominance rules Computational results for 2400 problem instances show that the branch and bound approach is capable of optimally solving 97 4 of the instances bearing witness to the efficiency of the proposed procedure The proposed heuristic procedure is then evaluated for the problems with large sizes and it is observed that this procedure has a good performance to silve these problems Results also indicate that the proposed approaches are more efficient when compared to other methods Next the single machine scheduling problem with one fixed unavailability period non resumable jobs with the aim of minimizing maximum earliness is considered Because no previous study has been reported on the problem in the literature complexity of the problem is first studied and this problem is proved to be NP hard an exact branch and bound approach is proposed for the problem By proving a number of theorems and lemmas a lower bound and some efficient dominance rules are developed A heuristic algorithm with O nlogn is presented which additionally used to calculate the upper bound Computational results for 2400 instances show that the branch and bound procedure is capable of optimally solving 98 79 of the instances Finally the single machine scheduling with a fixed non availability period non resumable jobs and bicriteria target function of maximum earliness and number of tardy jobs is studied Mathematical model of the problem is proposed and complexity of the problem is studied A set of lower and upper bounds for both certerions of the problem is then stated A branch and bound procedure along with efficient dominance rules and lower and upper bounds is also proposed in which the lower and upper bounds of criterions are used In order to evaluate the branch and bound approach a total of 1440 instances are solved by this procedure and their results are analyzed These results show that the branch and bound approach is capable of optimally solving 97 22 of instances Key Words scheduling single machine availability constraint branch and bound pdfMachine A pdf writer that produces quality PDF files with ease Produce quality PDF files in seconds and preserve the integrity of your original documents Compatible across nearly all Windows platforms simply open the document you want to convert click print select the Broadgun pdfMachine printer and that s it Get yours now

ملائي، احسان

زمان بندي تك ماشين با محدوديت دسترسي

شاخه وكران