Mean Flow Time Minimization in Reentrant Job Shops with a Hub

Wieslaw Kubiak, Sheldon X. C. Lou and Yingmeng Wang
Additional contact information
Wieslaw Kubiak: Memorial University of Newfoundland, St. John's, Newfoundland, Canada
Sheldon X. C. Lou: California State University San Marcos, San Marcos, California
Yingmeng Wang: University of Toronto, Toronto, Ontario, Canada

Operations Research, 1996, vol. 44, issue 5, 764-776

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 (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.44.5.764 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:44:y:1996:i:5:p:764-776

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().