A note on the complexity of openshop scheduling problems

A note on the complexity of openshop scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor1992529
Country: Canada
Volume: 29
Issue: 4
Start Page Number: 284
End Page Number: 294
Publication Date: Nov 1991
Journal: INFOR
Authors: , ,
Keywords: combinatorial analysis
Abstract:

The authors investigate the complexity of openshop scheduling problems. A number of variations of the shop with different objective functions have been surveyed. The problem of minimizing mean flow time in no-wait openshop as well as the problem of minimizing the number of late jobs for preemptive schedules are shown to be NP-hard. An O(nlogn) time algorithm for minimizing the total weighted number of late jobs in no-wait openshop is provided.

Reviews

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