Multiple bottleneck assignment problem

✍ Scribed by Y.P. Aneja; A.P. Punnen

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 109 KB
• Volume: 112
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(97)00392-5

✦ Synopsis

We consider the multiple bottleneck assignment problem which subsumes the well known min-sum and bottleneck assignment problems. The problem arises in the context of ¯exible manufacturing systems, where the objective is to maximize the throughput of a production system with several ¯ow shops, running in parallel, to produce a product. The problem is known to be strongly NP-hard. We propose a new algorithm for obtaining sharp lower bounds to the optimal objective value. Computational experiments are conducted to show the improvement over existing methods.