Branch and Bound Method with Heuristic Algorithm for a Special Flexible Flow Shop Scheduling Problem


Article Preview

This paper deals with an optimal method for solving a 2-stage flexible flow shop scheduling problem with group constraint, batch released dates. This problem is known to be NP-hard. In this paper, first of all, we construct a mathematical model for the problem. Then, we develop a branch and bound method with heuristic algorithm for the optimal solution of the problem. During the initialization, we use a heuristic algorithm H’ as the initial solution. We propose two branching algorithms in the branching procedure and two algorithms for the lower bound. We also propose a set of instances for this type of problem. The results are shown that our branch and bound method is effective for small and medium-sized problem but large-sized problem.



Advanced Materials Research (Volumes 139-141)

Edited by:

Liangchi Zhang, Chunliang Zhang and Tielin Shi




Z. T. Li et al., "Branch and Bound Method with Heuristic Algorithm for a Special Flexible Flow Shop Scheduling Problem", Advanced Materials Research, Vols. 139-141, pp. 1530-1534, 2010

Online since:

October 2010




[1] Lenstra J.K., Rinnooy Kan A.H.G., Brucker P. Complexity of machine scheduling problems.

[2] Wang Hui, Lu Xiwen. Approximation Algorithms for Two-stage Flexible Flow Shop Scheduling Subject to Release Dates. OR TRANSACTIONS, VOL 11 (2007) no. 3, pp.86-94.

[3] Pedro Leite Rocha, Martín Gómez Ravetti, Geraldo Robson Mateus, Panos M. Pardalos. Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Computers & Operations Research, 35(2008).


[4] Mohamed Haouari, Lotfi Hidri, Anis Gharbi. Operation scheduling of a two-stage hybrid flow shop. Math. Meth. Oper. Res, 64 (2006), pp.107-124.


[5] D.L. Santos, J.L. Hunsucker, D.E. Deal. Global lower bounds for flow shops with multiple processors. European Journal of Operational Research, 80 (1995), pp.112-120.


[6] Zhantao Li, Qingxin Chen, Ning Mao. A Heuristic Scheduling Algorithm for FF2 Problem whit Group Constraint, Batch Released Dates. The 9th International Conference on Frontiers of Design and Manufacturing, July 17~19, 2010, Changsha, China.

Fetching data from Crossref.
This may take some time to load.