On polynomial solvability of the high multiplicity total weighted tardiness problem

DOI10.1016/0166-218X(93)90034-LzbMath0779.90041OpenAlexW1975401191MaRDI QIDQ1208472

Frieda Granot, Jadranka Skorin-Kapov

Publication date: 16 May 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90034-l

zbMATH Keywords

single machinetotal weighted tardinessinteger quadratic nonseparable transportation

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Deterministic scheduling theory in operations research (90B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (6)

A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization ⋮ Using quadratic programming to solve high multiplicity scheduling problems on parallel machines ⋮ Multiplicity and complexity issues in contemporary production scheduling ⋮ Exact and approximate algorithms for high-multiplicity parallel machine scheduling ⋮ A framework for the complexity of high-multiplicity scheduling problems ⋮ An evaluation of group scheduling heuristics in a flow-line manufacturing cell

Cites Work

• Unnamed Item
• Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm
• Strongly polynomial algorithm for a class of combinatorial LCPs
• A polynomial algorithm for an integer quadratic non-separable transportation problem
• On simultaneous approximation in quadratic integer programming
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Convex separable optimization is not much harder than linear optimization

This page was built for publication: On polynomial solvability of the high multiplicity total weighted tardiness problem