Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 1211.90092
Wang, Ji-Bo; Sun, Lin-Hui; Sun, Lin-Yan
Single-machine total completion time scheduling with a time-dependent deterioration. (English)
[J] Appl. Math. Modelling 35, No. 3, 1506-1511 (2011). ISSN 0307-904X

Summary: We consider the single-machine scheduling problems with a time-dependent deterioration. By the time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. The objective is to minimize the total completion time. We develop a mixed integer programming formulation for the problem. The complexity status of this problem remains open. Hence, we use the smallest normal processing time (SPT) first rule as a heuristic algorithm for the general cases and analyze its worst-case error bound. Two heuristic algorithms utilize the V-shaped property are also proposed to solve the problem. Computational results are presented to evaluate the performance of the proposed algorithms.

MSC 2000:: *90B35 Scheduling theory

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

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]