Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

Polynomial-time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

0.00 Avg rating0 Votes
Article ID: iaor201112784
Volume: 58
Issue: 8
Start Page Number: 763
End Page Number: 770
Publication Date: Dec 2011
Journal: Naval Research Logistics (NRL)
Authors: , ,
Keywords: scheduling, combinatorial optimization, game theory
Abstract:

In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 - ϵ for any ϵ > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed.

Reviews

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