Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1196.90047
He, C-C; Wu, C-C; Lee, W-C
Branch-and-bound and weight-combination search algorithms for the total completion time problem with step-deteriorating jobs. (English)
[J] J. Oper. Res. Soc. 60, No. 12, 1759-1766 (2009). ISSN 0160-5682

Summary: 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\%.

MSC 2000:: *90B35 Scheduling theory
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords: scheduling; single-machine; step-deteriorating jobs; total completion time

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]