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

Yunpeng Pan (yunpeng.pangmail.com)

Abstract: Linear programming (LP)-based relaxations have proven to be useful in enumerative solution procedures for 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

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization

Category 3: Integer Programming (0-1 Programming )

Citation: working paper. submitted for publication.

Download: [PDF]

Entry Submitted: 08/04/2006
Entry Accepted: 08/04/2006
Entry Last Modified: 08/10/2006

Modify/Update this entry