Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 1043.90027
Cheng, T. C. Edwin; Ding, Qing; Kovalyov, Mikhail Y.; Bachman, Aleksander; Janiak, Adam
Scheduling jobs with piecewise linear decreasing processing times. (English)
[J] Nav. Res. Logist. 50, No. 6, 531-554 (2003). ISSN 0894-069X; ISSN 1520-6750/e

Summary: We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP-hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP-hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems.

MSC 2000:: *90B35 Scheduling theory

Keywords: machine scheduling; start time dependent processing times; computational complexity

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]