International Journal of Innovative
Computing, Information and Control
Volume 7, Number 11, November 2011c
ICIC International ⃝2011
ISSN 1349-4198
pp. 6453–6471

AN INTEGRATED COLUMN GENERATION AND LAGRANGIANRELAXATION FOR SOLVING FLOWSHOP PROBLEMSTO MINIMIZE THE TOTAL WEIGHTED TARDINESS
Tatsushi Nishi, Yukinori Isoya and Masahiro Inuiguchi
Division of Mathematical Science for Social Systems
Graduate School of Engineering Science
Osaka University
1-3 Machikaneyama-cho, Toyonaka City Osaka 560-8531, Japan{ nishi; inuiguti }@sys.es.osaka-u.ac.jp; isoya@inulab.sys.es.osaka-u.ac.jp

Received September 2010; revised January 2011
Abstract. In this paper, we address a new integration of column generation and Lagrangian relaxation for solving flowshop scheduling problems to minimize the total weighted
tardiness. In the proposed method, the initial columns are generated by using near-optimal
dual variables for linear programming relaxation of Dantzig-Wolfe decomposition derived
by the Lagrangian relaxation method. The column generation is executed just after thegeneration of base columns generated by near-optimal Lagrange multipliers. Computational results demonstrate that the integration of column generation and Lagrangianrelaxation can drastically speed up the conventional column generation.
Keywords: Scheduling, Column generation, Lagrangian relaxation, Flowshop scheduling

1. Introduction. Scheduling has become an essential component in recent societies tomeet versatile needs [15, 21, 22]. Column generation is an eﬀective computing technique
to obtain a tight lower bound for large scale combinatorial optimization problems. The
application of the algorithm appears in wide variety of areas such as railway crew scheduling [17], vehicle routing problem [1, 10], ship scheduling [4], patients scheduling in hospital[19] and time tabling problems [27]. It is also benefical to use the algorithm in the branch
and price [6] for the exact algorithms. This is due to the fact that a tight lower bound canbe obtained from Dantzig-Wolfe reformulation by column generation. Recently, columngeneration has been successfully applied to production scheduling problems: parallel machine scheduling to minimize the total weighted completion time [8, 31], parallel machinescheduling to minimize earliness and tardiness [9] and flowshop scheduling to minimize
the total weighted completion time [16].
It has been well known that the convergence for column generation is extremely slow
for large scale problems due to the degeneration in solving the restricted master linear
programming problems [20]. This phenomenon is called the tailing-oﬀ eﬀect in the columngeneration. Several improvements for the convergence of column generation have beenstudied. The oscillation of linear programming dual variables is controlled by the trust
region method [20]. The dual cuts are used in stabilizing column generation [3]. The
integration of column generation and Lagrangian relaxation (LR) is a promising way to
reduce computational eﬀorts for column generation. A combined column generation andLagrangian relaxation is studied for a single machine scheduling problem with the common
due date [30]. They report an improvement of the convergence of column generation byusing the lower bound obtained by LR as the criterion of convergence [30]. The reduction
6453