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

[thumbnail of 3011800000585.pdf] PDF

Download (456kB)


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)
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Kerem Bülbül
Date Deposited: 14 Dec 2006 02:00
Last Modified: 26 Apr 2022 08:03
URI: https://research.sabanciuniv.edu/id/eprint/208

Actions (login required)

View Item
View Item