A note on the complexity of openshop scheduling problems. (English) Zbl 0778.90027

Kubiak, W.; Sriskandarajah, C.; Zaras, K.

INFOR 29, No. 4, 284-294 (1991).

Summary: We 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(n \log n)\) time algorithm for minimizing the total weighted number of late jobs in no-wait openshop is provided.

MSC:

90B35	Deterministic scheduling theory in operations research
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

finish time; total weighted tardiness; maximum lateness; openshop scheduling; mean flow time in no-wait openshop; number of late jobs; preemptive schedules; NP-hard