Dual relaxations of the time-indexed ILP formulation for min–sum scheduling problems

Yunpeng Pan () and Zhe Liang ()
Additional contact information
Yunpeng Pan: South Dakota State University
Zhe Liang: Tongji University

Annals of Operations Research, 2017, vol. 249, issue 1, No 12, 197-213

Abstract: Abstract Linear programming (LP)-based relaxations have proven to be useful in enumerative solution procedures for $$\mathbf {NP}$$ NP -hard min–sum scheduling problems. We take a dual viewpoint of the time-indexed integer linear programming (ILP) formulation for these problems. Previously proposed Lagrangian relaxation methods and a time decomposition method are interpreted and synthesized under this view. Our new results aim to find optimal or near-optimal dual solutions to the LP relaxation of the time-indexed formulation, as recent advancements made in solving this ILP problem indicate the utility of dual information. Specifically, we develop a procedure to compute optimal dual solutions using the solution information from Dantzig–Wolfe decomposition and column generation methods, whose solutions are generally nonbasic. As a byproduct, we also obtain, in some sense, a crossover method that produces optimal basic primal solutions. Furthermore, the dual view naturally leads us to propose a new polynomial-sized relaxation that is applicable to both integer and real-valued problems. The obtained dual solutions are incorporated in branch-and-bound for solving the total weighted tardiness scheduling problem, and their efficacy is evaluated and compared through computational experiments involving test problems from OR-Library.

Keywords: Min–sum scheduling; Time-indexed formulation; Duality; Polynomial size (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-014-1776-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:249:y:2017:i:1:d:10.1007_s10479-014-1776-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-014-1776-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().