Flow shop scheduling with earliness, tardiness and intermediate inventory holding costs

Bülbül, Kerem and Kaminsky, Philip and Yano, Candace (2004) Flow shop scheduling with earliness, tardiness and intermediate inventory holding costs. Naval research logistics, 51 (3). pp. 407-445. ISSN 0894-069X

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1002/nav.20000


We consider the problem of scheduling customer orders in a flow shop with the objective of minimizing the sum of tardiness, earliness (finished goods inventory holding) and intermediate (work-in-process) inventory holding costs. We formulate this problem as an integer program, and based on approximate solutions to two di erent, but closely related, Dantzig-Wolfe reformulations, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig-Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two di erent lower bounds on the optimal integer solution, together with intuitive approaches for obtaining near-optimal feasible integer solutions. To the best of our knowledge, this is the first paper that applies column generation to a scheduling problem with di erent types of strongly NP-hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, yield good lower bounds, and generate near-optimal feasible integer solutions for problem instances with many machines and a realistically large number of jobs.

Item Type:Article
Uncontrolled Keywords:flow shop scheduling; earliness; tardiness; work-in-process inventory costs; column generation; Dantzig-Wolfe reformulation; Lagrangian relaxation
Subjects:T Technology > T Technology (General)
ID Code:208
Deposited By:Kerem Bülbül
Deposited On:14 Dec 2006 02:00
Last Modified:27 Apr 2009 15:03

Repository Staff Only: item control page