Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 1077.90025
Jeng, A.A.K.; Lin, B.M.T.
Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs. (English)
[J] Comput. Oper. Res. 32, No. 3, 521-536 (2005). ISSN 0305-0548

Summary: we study a scheduling problem of minimizing the total completion time on a single machine where the processing time of a job is a step function of its starting time and a due date that is common to all jobs. This problem has been shown to be NP-hard in the literature. To derive optimal solutions from a practical aspect, we develop a lower bound and two elimination rules to design branch-and-bound algorithms. Through computational experiments, we show that the proposed properties are effective in curtailing unnecessary explorations during the solution-finding process, and that the synergy of these properties can solve problems with up to 100 jobs in a few seconds.

MSC 2000:: *90B35 Scheduling theory
68M20 Performance evaluation of computer systems, etc.
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords: Single-machine scheduling; Step deterioration; Total completion time; Branch-and-bound algorithm

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article 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]