Abstract
In this paper, a manufacturing process for a single-server permutation Flow Shop Scheduling Problem with sequence dependant, disjoint setups and makespan minimization is considered. The full problem is divided into two levels, and the lower level, aimed at finding an optimal order of setups for a given fixed order of jobs, is tackled. The mathematical model of the problem is presented along with a solution representation. Several problem properties pertaining to the problem solution space are formulated. The connection between the number of feasible solutions and the Catalan numbers is demonstrated and a Dynamic Programming-based algorithm for counting feasible solution is proposed. An elimination property is proved, which allows one to disregard up 99.99% of the solution space for instances with 10 jobs and 4 machines. A refinement procedure allowing us to improve the solution in the time required to evaluate it is shown. To illustrate how the properties can be used, two solving methods were proposed: a Mixed-Integer Linear Programming formulation and Tabu Search metaheuristic. The proposed methods were then tested in a computer experiment using a set instance based on Taillard’s benchmark; the results demonstrated their effectiveness even under a short time limit, proving that they could be used to build algorithms for the full problem.