Mean Flow Time Minimization in Reentrant Job Shops with a Hub
Wieslaw Kubiak, Sheldon X. C. Lou, Yingmeng Wang
Operations Research · 1996 · Volume 44 · Issue 5
Abstract
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.
Keywords
production/scheduling, hub reentrant job shops and SPT rule, dynamic programming, deterministic, analysis of algorithms suboptimal algorithms and worst-case analysis
Enable JavaScript for citation tools and additional paper interactions.