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

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

Single Machine Scheduling with a Flexible Maintenance Fatemeh Ganji f Ganji@in iut ac ir Department of Industrial Engineering Isfahan University of Technology Isfahan 84156 83111 IranDegree M Sc Language FarsiGhasem Moslehi moslehi@cc iut ac ir Supervisor Abstract Today Scheduling problems have wide applications in many production and service systems Mostscheduling problems are based on the assumption that machine works continuously during the planninghorizon Unavailability periods often appear in industry due to a machine breakdown stochastic orpreventive maintenance deterministic during the scheduling period Therefore a more realistic schedulingmodel should take into account associated machine maintenance activities This assumption is not true inmany production environments because the machine may not be available during one or more periods such asduring maintenance operations In this study assumed that the machine has a single unavailability intervaland the starting time of this interval is a decision variable This problem considered a case in which themachine should be stopped for maintenance or resetting at a fixed time during the scheduling period Theyassumed that the maintenance period was specified in advance and time of maintenance did not fall outsidethe maintenance period In this thesis single machine scheduling problems with flexible maintenance havebeen considered At first a general division of these problems are explained and based on this framework theliterature on deterministic single machine scheduling problems with one and multiple fixed and flexible non availability periods is reviewed First the single machine scheduling problem with one flexible maintenanceperiod and non resumable jobs with the aim of minimizing maximum earliness is studied The proposedproblem is NP hard while the minimum slack time MST rule are optimal for the maximum earlinessproblem By proving a number of theorems a heuristic procedure is developed to solve the problem Abranch and bound approach is also presented which includes efficient upper and lower bounds anddominance rules Computational results for 3840 problem instances show that the branch and boundapproach is capable of optimally solving 99 47 of the instances bearing witness to the efficiency of theproposed procedure It is observed that the heuristic procedure has a good performance to solve theseproblems Next the single machine scheduling problem with one flexible maintenance period non resumablejobs with the aim of minimizing the number of tardy jobs is considered The proposed problem is NP hardwhile the earliest due date EDD rule are optimal for the number of tardy jobs problem Because no previousstudy has been reported on the problem in the literature has been showed that the complexity of the problemis NP hard An exact branch and bound approach is proposed for the problem By proving a number oftheorems and lemmas a lower bound and some efficient dominance rules are developed Moore andHodjson s algorithm is developed for this problem and used to calculate the upper bound Computationalresults for 3840 instances show that the branch and bound procedure is capable of optimally solving 99 34 of the instances Key Wordsscheduling single machine availability constraint branch and bound

گنجي، فاطمه

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

شاخه و كران