A decomposition scheduling method for operating flexible manufacturing systems

A ‘decomposition scheduling method’ is proposed for operating a flexible manufacturing system with small buffer capacity. It is made clear that the optimum schedule obtained by using an optimum scheduling algorithm, i.e. the Johnson or Jackson rule to minimize makespan for a 2-machine FMS, requires too large an amount of buffer capacity to realize. In the decomposition scheduling method, a set of unscheduled jobs are decomposed into several sets of jobs and the optimum subschedules are derived independently for each set of jobs. A near-optimum schedule is obtained by connecting these sub-schedules arbitrarily. The schedule obtained through the decomposition scheduling method gives a high degree of approximation in the system utilization and dramatically reduces the buffer capacity.