Nested partition-optimization algorithm for flow shop scheduling

A nested partition-algorithm and its application to the flow shop scheduling problem are addressed in this paper. In this application, the flow shop scheduling problem is considered as a partition tree. The algorithm performs an iterative process in which it partitions the feasible region and searches for the subset where the optimal solution is located. In the iteration, a heuristic algorithm and a neighborhood-search are employed to select a sample-point for estimating the promising index for each subset. Finally, computational experiments indicate that the algorithm outperforms the constructive heuristic algorithm and neighborhood-search in the performance of searching.