Fast Algorithm for Solving Extended Flexible Job-Shop Scheduling via Hierarchical Clustering

This paper proposes an extended flexible job-shop scheduling problem (EFJSP) and formulates the problem as an integer linear programming (ILP) with near-fewest decision variables and constraints. In order to deal with the explosion of computational complexity when the scale of EFJSP involved is large, we also propose a hierarchical clustering algorithm based on k-means method and an approximation-r algorithm to accelerate the solving process of EFJSP. Numerical results further demonstrate the validity of these two acceleration algorithms.