كمينه سازي مجموع بيشينه هاي زودكردوديركرددرمسئله زمان بندي تك ماشين با درنظرگرفتن ورود غيرهمزمان

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

AbstractNowadays globalization and its impact on the growing competitive markets importanceof customer satisfaction and efficient resource allocation have promoted customer oriented systems in companies One such approach is the Just In Time JIT productionsystem that has increasingly attracted attention in recent decades The JIT philosophy isto produce only the right items in the right quantities at the right times This concept hasinduced a new type of machine scheduling problems in which both earliness andtardiness are penalized Minimizing the sum of maximum earliness and tardiness is arecently proposed criterion which the present study aims to investigate it detail This study first addresses the problem of minimizing the sum of maximum earlinessand tardiness on a single machine with equal release times as the base problem Aneffective heuristic method has been developed for this problem Furthermore a branchand bound algorithm with backward approach was developed which draws upon efficientlower and upper bounds new dominance rules based on adjacent pairwise interchanges and a property called neutrality A set of 1280 instances with job sizes vary from smallto large were randomly generated All 100 of the instances were solved in less than700 seconds showing the high efficiency of our proposed algorithm which is animprovement over the methods reported in the literature Second the problem was considered with unequal release times as a realisticassumption and based on actual manufacturing environments The 3 partition problemwas taken to determine the complexity of the problem and it was shown to be NP hardin the strongly sense Then the problem was considered for the two scenarios of withand without idle inserts In the first scenario a branch and bound algorithm with forward approach isdeveloped as an exact method In the algorithm modified dispatching rules based ondifferent release times were proposed as upper bound while a procedure consideringpreemption assumption is used for obtaining a good lower bound Also dominance rulesbased on no unforced idle time and the theorems of the base problem are used to fathomthe nodes In order to evaluate the efficiency of proposed algorithm 4860 instances wererandomly generated varying from 7 to 1000 jobs We showed that the branch and boundalgorithm was capable of optimally solving 94 1 of the instances showing its efficiencyin solving all problem sizes In the second scenario a polynomial time algorithm was proposed to obtain the bestvalues of idle insert in a known sequence Then the sequencing and scheduling problemwas studied and a mixed integer linear programming model was developed It was shownthat the model did not work due to the high complexity of the problem Therefore efficient lower and upper bounds were used to propose a branch and bound scheme instead as an exact method In this problem dominance rules of the base problem couldnot be employed So three new dominance rules based on problem assumptions weredeveloped which enhanced the algorithm efficiency Given the complexity of theproblem this algorithm was capable of solving problems with up to 20 jobs Large sizesproblems were solved by two evolutionary meta heuristic algorithm genetic algorithmand particle swarm optimization Computational results in 3420 randomly generatedinstances showed that the proposed genetic algorithm improved the solutions in terms ofboth quality and time efficiency and that it would be capable of solving the problem inlarge sizes

مهنام، مهدي

كمينه سازي مجموع بيشينه هاي زودكردوديركرددرمسئله زمان بندي تك ماشين با درنظرگرفتن ورود غيرهمزمان

الگوريتم شاخه وكران