بررسي مسائل زمان بندي تك ماشين با محدوديت دسترسي انعطاف پذير دوره اي دو حالته

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

Considering the Single Machine Scheduling Problems with Bimodal Flexible and Periodic Availability Constraints Omolbanin Mashkani o mashkani@in iut ac ir Date of Submission 3 March 2012 Departent of Industerial Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor Ghasem Moslehi moslehi@cc iut ac irAbstract In most of the scheduling researches it is assumed that machines are available continuously But in thereal world the available times of machines is restricted by some reasons like breakdowns planning horizonoverlaps tool change and maintenance activities Scheduling problems with availability constraint areclassified in three group of fixed flexible and variable Start time finish time and the duration of unavailability period are previously known in problems with fixedavailability constraint On the other hand in the case of problems with flexible availability constraint theduration of unavailability period is previously known but its start time is a decision variable In someproblems of this group a fixed time interval is considered for availability constraint while in others themaximum continuous working time of the machine is determined Also in problems with variable availabilityconstraint the duration of unavailability period depends on machine and operator s conditions In researcheson variable availability constraint the amount of deterioration effect on processing times determines starttime and duration of machine stopping time In the literature single machine scheduling problem with fixedavailability constraint is considered in many cases But single machine scheduling problem with flexibleavailability constraint is considered less than fixed type In this study we focused on a novel definition of availability constraint called bimodal flexible and periodicmaintenance activities In this definition in each period the maximum continuous working time of a machinecould have two values and so duration time of maintenance could have two values First a classification ofscheduling problems with availability constraint is provided and then the literature review of deterministicscheduling problems with one or more fixed flexible and variable constraints are investigated according tothat classification In the rest of this study the single machine scheduling problem with bimodal flexible and periodicmaintenance activities is investigated to minimize total completion times The problem is proved to be NP Hard A heuristic algorithm called BLCB with O n logn time complexity and a back tracking branch andbound algorithm with a lower bound and dominance properties is developed The solution of heuristicalgorithm is used as an upper bound in branch and bound algorithm Computational results on 1680 probleminstances shows that the branch and bound algorithm can solve 98 39 percent of problems with up to 22 jobsand the average error of the heuristic algorithm is equal to 1 05 percent In the next section of this study single machine scheduling problem with bimodal flexible and periodicmaintenance activities is investigated to minimize the number of tardy jobs Like the previous section thisproblem is also proved to be NP Hard and a heuristic algorithm called H2 with O n logn time complexityproposed Then a back tracking branch and bound algorithm concluding some lower bounds dominanceproperties and the solution of H2 as upper bound is proposed and tested Computational results on 1680problem instances shows that the branch and bound algorithm can solve 94 76 percent of problems with up to20 jobs and the average error of heuristic algorithm is equal to 2 percent KeywordsScheduling Branch and Bound Availability Constraint Flexible Bimodal

مشكاني، ام البنين

بررسي مسائل زمان بندي تك ماشين با محدوديت دسترسي انعطاف پذير دوره اي دو حالته

شاخه و كران