Finding minimum flow time cyclic schedules for non-identical, multistage jobs

Finding a minimum flow time cyclic schedule for a single, multistage job with a serial, re-entrant routing is known to be NP-hard. This paper addresses the problem of scheduling multiple, non-identical jobs in a cyclic fashion, where the job routings may be arbitrary partial orders as well as re-entrant. Given a fixed cycle length, our goal is to minimize a weighted sum of the job flow times. We present a general schedule construction algorithm for implementing a cyclic version of priority dispatch rules that accepts any user-defined tie-breaking function and naturally yields a feasible cyclic schedule. We also describe a pair of easily solvable subproblems that may be used to tighten existing cyclic schedules, as well as an iterative schedule improvement algorithm based on a technique called compression. A numerical study suggests that our schedule construction algorithm, called Cyclic PDR, outperforms its traditional noncyclic priority dispatch rule counterpart, as well as a previously proposed single-pass algorithm. The Cyclic PDR algorithm is shown to be particularly effective when used in conjunction with a least work remaining tie-breaking function. Taken together, our schedule construction and improvement techniques provide an effective solution approach for producing minimum flow time cyclic schedules.