Journal of Applied Mathematics
Volume 2012 (2012), Article ID 395947, 9 pages
http://dx.doi.org/10.1155/2012/395947
Research Article

Optimal Results and Numerical Simulations for Flow Shop Scheduling Problems

Tao Ren,1 Yuandong Diao,2 and Xiaochuan Luo3

1Software College, Northeastern University, Shenyang 110004, China
2Personnel Department, Shenyang University of Chemical Technology, Shenyang 110142, China
3State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110004, China

Received 20 May 2011; Revised 26 October 2011; Accepted 4 January 2012

Academic Editor: Yuri Sotskov

Copyright © 2012 Tao Ren et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

This paper considers the m-machine flow shop problem with two objectives: makespan with release dates and total quadratic completion time, respectively. For F 𝑚 | 𝑟 𝑗 | C 𝑚 𝑎 𝑥 , we prove the asymptotic optimality for any dense scheduling when the problem scale is large enough. For F 𝑚 ‖ Σ C 2 𝑗 , improvement strategy with local search is presented to promote the performance of the classical SPT heuristic. At the end of the paper, simulations show the effectiveness of the improvement strategy.