A note on the complexity of the concurrent open shop problem

A note on the complexity of the concurrent open shop problem

0.00 Avg rating0 Votes
Article ID: iaor20081242
Country: United Kingdom
Volume: 9
Issue: 4
Start Page Number: 389
End Page Number: 396
Publication Date: Aug 2006
Journal: Journal of Scheduling
Authors:
Abstract:

The concurrent open shop problem is a relaxation of the well known open job shop problem, where the components of a job can be processed in parallel by dedicated, component specific machines. Recently, the problem has attracted the attention of a number of researchers. In particular, Leung et al. show, contrary to the assertion by Wagneur and Sriskandarajah, that the problem of minimizing the average job completion time is not necessarily strongly NP-hard. Their finding has thus once again opened up the question of the problem's complexity. This paper re-establishes that, even for two machines, the problem is NP-hard in the strong sense.

Reviews

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