A polynomial algorithm for an integer quadratic non-separable transportation problem |
| |
Authors: | Dorit S Hochbaum Ron Shamir J George Shanthikumar |
| |
Institution: | (1) Department of Industrial Engineering and Operations Research and Walter A. Haas School of Business, University of California, 94720 Berkeley, CA, USA;(2) Department of Computer Science, School of Mathematics, Sacker Faculty of Exact Sciences, Tel Aviv University, 69978 Ramat Aviv, Israel |
| |
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.Supported in part by the National Science Foundation under grant ECS-85-01988, and by the Office of Naval Research under grant N00014-88-K-0377.Supported in part by Allon Fellowship, by Air Force grants 89-0512 and 90-0008 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center—NSF-STC88-09648. Part of the research of this author was performed in DIMACS Center, Rutgers University.Supported in part by Air Force grant 84-0205. |
| |
Keywords: | Integer programming quadratic non-separable programming scheduling transportation proximity |
本文献已被 SpringerLink 等数据库收录! |
|