Scheduling flowline manufacturing cells with inter-cellular moves: non-permutation schedules and material flows in the cell scheduling problem

A major goal of the concept of cellular manufacturing is to form independent cells. However, the formation of entirely independent cells is rarely found in practice, where inter-cellular transports of jobs are often accepted to a certain level. The resulting scheduling task in flowline manufacturing cells is referred to as cell scheduling problem. Usually it is modelled and solved analogously to the group scheduling problem, which arises within a single cell with multiple part families. In this study, we point out several characteristics that specify the distinctiveness of cell scheduling. Furthermore, a new cell-based objective, namely total cell makespan, is introduced. As no appropriate benchmark instances are available so far, new test problems are developed, that integrate the derived characteristics. In an extensive computational study known constructive heuristics as well as simulated annealing algorithms to generate permutation and non-permutation schedules are tested. It is revealed that especially the type of material flows between cells has an immense impact on the algorithms' performance. The findings support a better problem understanding and point out the necessity of developing new heuristics especially for certain types of the cell scheduling problem.