Scheduling of jobs with cross families in two stage manufacturing systems

This paper studies scheduling of n jobs in a two stage manufacturing system to minimize makespan when each stage has its own job families and families in each stage require sequence independent setups. In a manufacturing system that each stage has its own family; jobs belonging to different families in one stage may belong to the same family in another stage, and we call it cross families. To the best of our knowledge, there is no study on cross families in scheduling literature. Our problem is NP-hard for arbitrary number of families, and therefore we study the problem with fixed number of families. We first analyze some properties of the optimal schedule and show that Johnson sequence is optimal for jobs belonging to the same family on both machines. We develop an efficient branch and bound algorithm with complexity of O(nc), where c is a constant and a hybrid genetic algorithm for large scale problems, using the properties of the optimal schedule. Finally, we present computational experiment to demonstrate the effectiveness of our algorithms.