Minimizing the sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time |
| |
Authors: | N Nekoiemehr G Moslehi |
| |
Institution: | 1.Isfahan University of Technology,Isfahan,Iran |
| |
Abstract: | This paper considers the problem of scheduling a given number of jobs on a single machine to minimize the sum of maximum earliness and maximum tardiness when sequence-dependent setup times exist (1∣ST sd ∣ETmax). In this paper, an optimal branch-and-bound algorithm is developed that involves the implementation of lower and upper bounding procedures as well as three dominance rules. For solving problems containing large numbers of jobs, a polynomial time-bounded heuristic algorithm is also proposed. Computational experiments demonstrate the effectiveness of the bounding and dominance rules in achieving optimal solutions in more than 97% of the instances. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|