ارائه يك رويكرد ابتكاري جديد در حل مسائل زمان بندي ديركرد زودكرد در حالت تك ماشين

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

Minimizing Early Tardy Scheduling Problems on a Single Machine using a Novel Heuristic Approach Simin PoursheikhAli s poursheikhali@in iut ac ir Date of Submission 4 Feb 2012 Department of Industrial Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Farsi Supervisor Mehdi Bijari bijari@cc iut ac ir Abstract The earliness tardiness E T measure has been the subject of abundant scheduling research efforts due to theincreasing business emphasis on commitment to due dates as a competitive advantage A notable feature ofmodern manufacturing is the extensive use of the Just in Time concept in inventory production managementwhere each job should be completed as close as possible to its due date In such an environment tardiness orearliness is important A few applications of JIT to minimize sub quality or defective products include themanufacturing of plastics glass chemicals and semiconductors In these manufacturing activities raw materialor work in process items may either degrade in quality or become unusable due to either early or late processing This need for on time processing is also encountered in semiconductor manufacturing where some chemicalcoating processes of the wafer surfaces cannot be done either early or late because it may result indegrading the wafer surface In this situation earliness and tardiness are considered as equally undesirable Thus any schedule of a set of jobs should strive to minimize the total earliness and tardiness with tardinessreflecting customer satisfaction while earliness measures inventory performance Since the problem class is NP hard exact methods such as dynamic programming DP and different branch and bound algorithms are developed to obtain the best permutation sequence It is noteworthy that meta heuristicmethods and hybrid procedures have proven much more useful than exact methods in large and complexsituations In this thesis we present a novel two stage heuristic approach to minimize different early tardy schedulingproblems on a single machine Performance is measured by the minimization of different types ofearliness tardiness costs i e sum of maximum earliness and tardiness weighted versions of the total earliness andtardiness Total tardiness is also considered as an important objective function In the first stage of the presentedapproach after generating an initial random sample a job position matrix is constructed Based on this matrixand according to the procedure described in detail in related section the approximate position of each job in asequence is specified The induced knowledge is applied in generating a new sample Another job positionmatrix is reconstructed In order to find the optimal assignment of each job to each position a Hungarianalgorithm is applied to this matrix To improve the solution quality a local search is applied The efficiency of the proposed approach has been demonstrated by numerical results on related benchmarkproblems Computational results reflect the optimal and near optimal solutions on different performancemeasures in a few seconds Further work could consist in enhancing the problem to multi operation scheduling problems such as shopscheduling problems Applying the novel two stage proposed method to different other objective functions suchas weighted version of our problem is also worth pursuing Keywords Single machine scheduling Earliness and Tardiness Heuristic ApproachLocal search

پورشيخعلي، سيمين

ارائه يك رويكرد ابتكاري جديد در حل مسائل زمان بندي ديركرد زودكرد در حالت تك ماشين

جستجوي محلي