Scheduling Cyclic Production on Several Identical Machines

This paper considers problems that arise in scheduling cyclic production of different parts on several identical machines where the cycle times are of the form kⁱw, with i varying only with each part. First we derive a simple necessary and sufficient condition for scheduling one machine when the production times of all jobs are identical. Then we describe three conditions, any one of which ensures that if a feasible schedule on M machines exists, then a schedule also exists in which each part always executes on the same machine. These conditions can be used to motivate heuristics to address the scheduling problem.