Cyclic Schedules for Job Shops with Identical Jobs

We consider the problem of finding cyclic schedules for a job shop in which all jobs are identical. Specifically, we assume that a single product is produced on a finite number of machines. Each part is manufactured by performing a given set of operations in a pre-determined sequence. Each operation can be performed on exactly one machine.

Key structural properties of cyclic schedules are studied. A search algorithm based on these properties is proposed, and preliminary computational tests of the algorithm are reported.