ISSN:
1436-4646
Keywords:
Integer programming
;
quadratic non-separable programming
;
scheduling
;
transportation
;
proximity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We study the problem of minimizing the total weighted tardiness when scheduling unti-length jobs on a single machine, in the presence of large sets of identical jobs. Previously known algorithms, which do not exploit the set structure, are at best pseudo-polynomial, and may be prohibitively inefficient when the set sizes are large. We give a polynomial algorithm for the problem, whose number of operations is independent of the set sizes. The problem is reformulated as an integer program with a quadratic, non-separable objective and transportation constraints. Employing methods of real analysis, we prove a tight proximity result between the integer solution to that problem and a fractional solution of a related problem. The related problem is shown to be polynomially solvable, and a rounding algorithm applied to its solution gives the optimal integer solution to the original problem.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01581207
Permalink