Operations Research · 1996 · 69 citations · 9 references
ManagementIndustrial EngineeringOperations ManagementFacility LayoutProduction PlanningSchedulingBatch SchedulingJob SchedulingJob SequencingJob Shop SchedulingMachine SchedulingScheduling TheoryBottleneck DetectionSchedule PlanningShortest Path HeuristicsShortest Path ProblemsWorst-case Bounds
This paper considers a reentrant job shop with one hub machine which a job enters K times. Between any two consecutive entries into the hub, the job is processed on other machines. The objective is to minimize the total flow time. Under two key assumptions, the bottleneck assumption and the hereditary order (HO) assumption on the processing times of the entries, it is proved that there is an optimal schedule with the shortest processing time (SPT) job order and a dynamic programming algorithm is derived to find such a schedule. An approximation algorithm based on the shortest path algorithm and the SPT job order is also proposed to solve the problem. The approximation algorithm finds an optimal clustered schedule. In clustered schedules, jobs are scheduled in disjoint clusters; they resemble batch processing and seem to be of practical importance. Worst-case bounds for clustered schedules are proved with the HO assumption relaxed. Two special cases with the restriction that there are only two entries to the hub machine are further analyzed to offer more insight into the structure of optimal solutions.
9
The Complexity of Flowshop and Jobshop Scheduling
M. R. Garey, David Johnson, Ravi Sethi · Mathematics of Operations Research · 1976 · 2.6K citations
On the Complexity of Scheduling with Batch Setup Times
Clyde Monma, Chris N. Potts · Operations Research · 1989 · 292 citations
Scheduling of re‐entrant flow shops
Stephen C. Graves, Harlan C. Meal, Daniel Stefek et al. · Journal of Operations Management · 1983 · 188 citations
Engineering, Industrial Engineering, Manufacturing Engineering +9