An Exact Approach to Minimizing the Sum of Maximum Earliness and Tardiness with Unequal Release Times
This paper addresses the problem of minimizing the sum of maximum earliness and tardiness on a single machine with unequal release times and no unforced idle time.A branch and bound algorithm with forward approach is developed as an exact method.In the algorithm,modified dispatching rules based on different release times were proposed as the upper bound while a procedure considering preemption assumption is used for obtaining a good lower bound.Also,dominance rules based on adjacent pairwise interchanges as well as a property called “neutrality are used to fathom the nodes.In order to evaluate the efficiency of the proposed algorithm,4860 instances were randomly generated varying from 7 to 1000 jobs.We showed that the branch and bound algorithm was capable of optimally solving 94.1％ of the instances,showing its efficiency in solving all problem sizes.
Single machine Earliness-Tardiness Release times No unforced idle time Branch-and-bound
Mehdi Mahnam Ghasem Moslehi
Department of Industrial and Systems EngineeringIsfahan University of TechnologyIsfahan,IRAN Department of Industrial and Systems Engineering Isfahan University of Technology Isfahan,IRAN
国际会议
北京
英文
2008-10-12（万方平台首次上网日期，不代表论文的发表时间）