A Note On The Complexity Of Openshop Scheduling Problems
From MaRDI portal
Publication:3142313
DOI10.1080/03155986.1991.11732176zbMath0778.90027OpenAlexW95437694MaRDI QIDQ3142313
Kazimierz Zaras, Wiesław X. Kubiak, Chelliah Skriskandarajah
Publication date: 15 November 1993
Published in: INFOR: Information Systems and Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/03155986.1991.11732176
NP-hardmaximum latenesstotal weighted tardinessopenshop schedulingnumber of late jobspreemptive schedulesfinish timemean flow time in no-wait openshop
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items
Minimizing the weighted number of tardy jobs on multiple machines: a review ⋮ On the complexity of preemptive openshop scheduling problems ⋮ On complexity of minimizing weighted number of late jobs in unit time open shops ⋮ Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop ⋮ A branch \(\&\) bound algorithm for the open-shop problem ⋮ Open shop scheduling with maximal machines ⋮ Open shop problems with unit time operations ⋮ On minimizing the weighted number of late jobs in unit execution time open-shops. ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises ⋮ A multi-level genetic algorithm for a multi-stage space allocation problem ⋮ Minimizing the weighted number of late jobs in UET open shops ⋮ The generalized shifting bottleneck procedure ⋮ Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop ⋮ Scheduling unit time open shops to minimize the weighted number of late jobs ⋮ Open shops with jobs overlap
