Technical Note—A Solvable Cyclic Scheduling Problem with Serial Precedence Structure

Abstract

Jobs arrive at a facility in a periodic way, each requiring the same set of tasks with a serial precedence structure. Only a fixed number of tasks can be performed in any period. The number of periods is also given so that jobs not completed in the final period are continued in the first. The problem of minimizing total delay is shown to be solvable analytically. The model is motivated by the application of scheduling courses to quarters to minimize student delay in an academic program.