Scheduling multi-operation jobs in partially overlapping systems

This paper deals with the important and difficult scheduling problem of flexible manufacturing systems (FMS) with multi-operation parts and machines with partially overlapping capabilities. The scheduling problem of partially overlapping systems is shown to be a general form of many classical scheduling problem models and can be applied to several application domains such as distributed computing systems, machinery systems and/or robots. The quality of a schedule in this paper is measured by the minimization of part transfers and the makespan. Our approach adopts a divide-and-conquer strategy. First the problem is separated into three sub-problems based on the characteristics of the model. Then, implicit enumeration and heuristics algorithms are developed for the sub-problems. Experimental results show that the proposed solutions perform ‘well’ for a set of open shop benchmark problems and practically solve the partially overlapping scheduling problems at various sizes.