On a asymptotic optimality of algorithms for the flow shop problem with release dates

On a asymptotic optimality of algorithms for the flow shop problem with release dates

0.00 Avg rating0 Votes
Article ID: iaor20063358
Country: United States
Volume: 52
Issue: 3
Start Page Number: 232
End Page Number: 242
Publication Date: Apr 2005
Journal: Naval Research Logistics
Authors: , ,
Keywords: heuristics
Abstract:

We consider the nonpermutation flow shop problem with release dates, with the objective of minimizing the sum of the weighted completion times on the final machine. Since the problem is NP-hard, we focus on the analysis of the performance of several approximation algorithms, all of which are related to the classical Weighted Shortest Processing Time Among Available Jobs heuristic. In particular, we perform a probabilistic analysis and prove that two online heuristics and one offline heuristic are asymptotically optimal.

Reviews

Required fields are marked *. Your email address will not be published.