Scheduling in m-machine flowshops with flexible operations

In this study, we consider an m machine flowshop which produces n identical parts. Each machine has to make some preassigned operations. Additionally, a pair of adjacent machines are capable of performing an additional operation, besides their preassigned operations. There may be an infinitive capacity buffer or no buffer in between machines. The problem is to decide on which of the flexible machines to perform this operation. For each part, the objective is to minimize the makespan. Such problems are encountered. In some industries, such as the metal cutting industry where highly flexible CNC machines are used extensively. Similar problems are also encountered in assembly lines where cross-tranined operations are working and assembly systems of printed circuit boards (PCB). In order to solve the problem, theoptimization model is developed and the characteristics of the optimal solution are determined. Using these characteristics, some problems can be solved trivially or the problem size can be reduced. However, even the reduced problem requires a long time to solve with the optimization model. Therefore, a dynamic programming algorithm is developed which uses the characteristics of the optimal solution. The pseudopolynomial time dynamic programming algorithm also requires a long solution time for some problems depending on problem parameters. As a consequence a heuristic procedure is developed to produce high quality solutions in reasonable times. The performance of the heuristic is tested through a computational study. The developed procedure constitute the first step for the solution of m-machine flowshops with more general flexibility systems.