A comparative study of schedule-generation procedures for the reentrant shops scheduling problem

Most production scheduling-related research assumes that a job visits certain machines at most once. A new type of manufacturing system, the reentrant shop, has recently become prominent. The fundamental characteristic of a reentrant shop is that jobs may visit a certain machine more than once. This paper studies the problem of scheduling the reentrant job-shop and reentrant flow-shop with the objectives of minimizing the makespan and mean flow time of jobs. Optimization models are first presented, followed by the heuristic procedures based on active and non-delay schedules. New priority rules to accomodate the reentry feature are proposed. Both the new rules and some selected rules of earlier research are incorporated in the schedule generation algorithms to produce active and non-delay schedules. Simulation studies are conducted to compare the performance of active and non-delay schedules, and that of the priority rules in finding heuristic solutions for the problems.