Algorithms for common due-date assignment and sequencing on a single machine with sequence-dependent setup times |
| |
Authors: | J-G Kim D-H Lee |
| |
Institution: | 1.Hanyang University,Seoul,South Korea |
| |
Abstract: | This paper focuses on the single machine sequencing and common due-date assignment problem for the objective of minimizing the sum of the penalties associated with earliness, tardiness and due-date assignment. Unlike the previous research articles on this class of scheduling problem, we consider sequence-dependent setup times that make the problem much more difficult. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of both the optimal and heuristic algorithms, in computational experiments on randomly generated test instances, are reported. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|