Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 0816.90088
Sundararaghavan, P.S.; Kunnathur, A.S.
Single machine scheduling with start time dependent processing times: Some solvable cases. (English)
[J] Eur. J. Oper. Res. 78, No.3, 394-403 (1994). ISSN 0377-2217

Summary: A new type of single machine scheduling problem, in which the processing time is a binary function of a common start time due date is defined. The jobs have processing time penalties for starting after the due date, and the objective is to minimize the sum of the weighted completion times. The general case addressed here is for jobs with common pre-duedate processing time, general post-duedate processing time penalties, and general weights. A switching algorithm is proposed for this case and we conjecture that it is optimal. A 0-1 quadratic programming formulation of this problem is presented. Solvable cases, one with two different weights, another with two different penalties and another with structured weights and penalties have been identified and polynomial time optimal algorithms have been proposed for them.

MSC 2000:: *90B35 Scheduling theory
90C20 Quadratic programming
90C09 Boolean programming

Keywords: single machine scheduling; processing time penalties; due date; polynomial time optimal algorithms

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]