5238

4908

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

صنايع

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

1388

نه،88ص.: مصور،جدول

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

قاسم مصلحي

علي پناهنده

11/3/89

مهدي بيجاري

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

ID4908

به فارسي و انگليسي: قابل رويت در نسخه ديجيتالي

9 Minizing Number of tardy Jobs in Single Machine With Piecewise Linear Deteriorating Abbasali Jafari Nodoshan aa jafari@in iut ac ir Date of Submission 2010 04 17 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 Nowadays scheduling problems have wide application in many production systems and services In many of them processing time are constant and predetermined This consumption is true in some cases but because machines and tools Depreciate and their efficiency reduce during time this consumption cannot be true in all cases In addition in some industries like steel industry job s Delay for process result in longer processing time These kinds of jobs are introduced as deteriorating jobs so a job is deteriorating whenever its processing time is not constant and is dependent to scheduled jobs In the other words a job which is process later needs more time to process Job processing time may depend on three factors job s start time its position or the sum of basic process time for scheduled job In this thesis single and multiple machines scheduling with deteriorating consumption is studied A general classification of these problems is presented and literature review is studied Single machine scheduling problem with piecewise linear deteriorating consumption and minimizing number of tardy jobs as objective function in which job s processing times is a non decreasing function based on the job starting time All jobs have different deteriorating rate Because the same studies haven t seen yet in the literature the problem complexity is examined and demonstrated that it is an NP hard problem So for solving this problem an exact approach based on branch and bound algorithm which considers some theory and lemma three lower bound and dominance rules is presented A heuristic algorithm is also presented with O n2 and is use as upper bound for the problem Computational results for 1840 problems show that problems with 28 jobs can be solved in all series and in some series this number is higher In general the branch and bound algorithm can solve 85 4 of examples optimally which shows the efficiency of the algorithm In addition the average of optimal answer to heuristic answer ratio with the number no tardy jobs as objective function is less than 1 08 and this number is less than the result of algorithm proposed in researches with the objective of minimizing number of tardy jobs Because of high efficiency of the heuristic algorithm problems with higher job size are solved and results are presented

قاسم مصلحي

علي پناهنده

مهدي بيجاري