Flexible job-shop scheduling with overlapping machine sets

In practice, the complexity of the flexible job-shop scheduling problem is quite large, i.e., it is often impossible to find the optimal solution in a reasonable time. But for small problems the optimal solution can be found in a very short time. In our study, a simulation-based segmentation procedure divides the problem into several small subproblems, and then a branch and bound method is used to solve the subproblems one after another. The solutions of the subproblems make up the solution of the whole problem. A method to determine the size of the subproblem is provided. The heuristic for the branching is developed from the machine overlapping features. The experimental results show that the approach performs better than some decision rules.