In the paper a variant of cyclic production with setups and two-machine cell is considered. One of the stages of the problem solving consists of assigning each operation to the machine on which it will be carried out. The total number of such assignments is exponential. We propose a polynomial time algorithm finding the optimal operations to machines assignment.

In this paper, a non-permutation variant of the Flow Shop Scheduling Problem with Time Couplings and makespan minimization is considered. Time couplings are defined as machine minimum and maximum idle time allowed. The problem is inspired by the concreting process encountered in industry. The mathematical model of the problem and solution graph representation are presented. Several problem properties are formulated, including the time complexity of the goal function computation and block elimination property. Three solving methods, an exact Branch and Bound algorithm, the Tabu Search metaheuristic, and a baseline Genetic Algorithm metaheuristic, are proposed. Experiments using Taillard-based problem instances are performed. Results show that, for the Tabu Search method, the neighborhood based on the proposed block property outperforms other neighborhoods and the Genetic Algorithm under the same time limit. Moreover, the Tabu Search method provided high quality solutions, with the gap to the optimal solution for the smaller instances not exceeding 2.3%.

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.