Throughput maximization in flowshops producing identical parts having flexible operations

In this study, two problems are considered. The first one is a 3-machine flowshop producing $n$ identical parts with a flexible operation. All machines in the system, performs a fixed operation on the parts and have the capability to produce an additional operation called the flexible operation. Flexible operation of each part must be assigned only one machine. The second problem is an $m$-machine flowshop with $(m-1)$ flexible operations. There is a flexible operation between each of two consecutive machines. In both problems, the objective is to determine the assignment of the flexible operations of all parts in order to maximize the throughput rate. We formulated the problems as Mixed Integer Programs. However as the problem size increases, the required CPU time to solve the models increases drastically. Therefore we developed heuristic algorithms for both problems, we also developed a dynamic algorithm for the first problem which can find the optimal solution more quickly than the mathematical model. To test the performances of heuristic algorithms, comprehensive computational studies are made. We coded mathematical models using GAMS interface with CPLEX 12 Solver and we coded the heuristic algorithms in C++ programming language. The results are analyzed, with respect to required CPU times and the percent gaps with the optimal solution.