9998

9228

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

صنايع

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

1393

يازده، 80ص.: مصور، جدول، نمودار

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

قاسم مصلحي

94/2/20

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

1396/09/27

كتابنامه

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

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

ID9228

Approximation Approaches for Minimizing Total Weighted Completion Time with Flexible Availability Constraint Behnam Mahdinia b khondabi@in iut ac ir Date of submission 16 December 2014 Department of Industrial and Systems Engineering Isfahan University of Technology 84156 83111 Isfahan Iran Degree M Sc Language PersianSupervisor Ghasem Moslehi moslehi@cc iut ac irAbstractIn this study a single machine scheduling problem with one flexible availability constraint has been studied In real world situations the machine is not continuously available and the unavailability arises from suchissues as breakdowns tool changes or maintenance activities In most of previous studies the start and finishtimes of availability constraint are considered to be fixed This study assumes that this constraint is placed ina time window In other words the earliest possible start time and the latest possible finish time ofavailability constraint are specified Since solve of most optimization problems optimally in real sizes andreasonable time is almost impossible researchers usually resort to simpler suboptimal but efficientapproaches Approximation approaches are a class of suboptimal approaches which already provideinformation about the quality of their solution An approximation algorithm is an algorithm that its resultingsolution is at most by a constant factor away from optimal solution Approximation schemes are also a familyof approximation algorithms that the maximum error of their solution is a part of their input parameters Tobe more precise by an approximation scheme a solution with desired maximum error can be achieved In thisstudy objective functions of minimizing total un weighted completion time and total weighted completiontime are investigated and for these problems approximation algorithms and approximation schemes arepresented For the objective of minimizing total completion time an approximation algorithm based on the shortestprocessing time rule is presented and it is shown that its worst case error bound is equal to and tight Aswell as for solving this problem optimally two pseudo polynomial dynamic programming algorithms areintroduced The first algorithm considers all possible values for the start time window of availabilityconstraint and for each value solves the problem with fixed availability constraint But in the secondalgorithm the problem is solved directly Then by structuring these two dynamic programming algorithms two fully polynomial time approximation schemes are presented for this problem Also for the objective ofminimizing total weighted completion time an approximation algorithm with tight worst case error bound of2 is introduced In addition one of the two previous dynamic programming algorithms is generalized for thisobjective function and is transformed to a fully polynomial time approximation scheme Keywords scheduling single machine flexible availability constraint approximation algorithm fullypolynomial time approximation scheme

قاسم مصلحي

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