Mean flow time minimization in reentrant job shops with a hub
成果类型：
Article
署名作者：
Kubiak, W; Lou, SXC; Wang, YM
署名单位：
California State University System; California State University San Marcos; Bank of Montreal; University of Toronto
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.44.5.764
发表日期：
1996
页码：
764-776
关键词：
摘要：
This paper considers a reentrant job shop with one hub machine which a job enters K limes. Between any two consecutive entries into the hub: the job is processed on other machines. The objective is to minimize the total Bow 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 ro solve the problem. The approximation algorithm finds an optimal clustered schedule. In clustered schedules, jobs are scheduled in disjoint clusters; they resemble hatch 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.