Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs |
| |
Authors: | C-C He C-C Wu W-C Lee |
| |
Affiliation: | 1.Feng Chia University,Taichung,Taiwan |
| |
Abstract: | In many real situations, it is found that if certain maintenance procedures fail to be completed prior to a pre-specified deterioration date, then the jobs will require extra time for successful completion. In this paper, a single-machine total completion time problem with step-deteriorating jobs is considered. A branch-and-bound method incorporated with several dominance properties and a lower bound is developed to derive the optimal solution for this problem. In addition, a weight-combination search algorithm is proposed to search for a near-optimal solution. Computational results indicate that the branch-and-bound algorithm can solve most of the problems with up to 24 jobs in a reasonable amount of time. Moreover, the proposed heuristic algorithm is accurate with mean deviations from the optimum value of less than 0.3%. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|